zbMATH — the first resource for mathematics

Scheduling $$UET$$-tasks on a star network: complexity and approximation. (English) Zbl 1217.68039
Summary: In this article we investigate complexity and approximation on a processor network where the communication delay depends on the distance between the processors performing tasks. We then prove that there is no polynomial-time heuristic with a performance guarantee smaller than $${\frac{6}{5}}$$ (respectively $${\frac{14}{13}}$$) for minimization of the makespan (respectively the total job completion time) on a processor network represented by a star. Moreover, we design an efficient polynomial-time approximation algorithm with a worst-case ratio of four. We also prove that a polynomial-time algorithm exists for a schedule with a length of at most four. Lastly, we generalize all previous results on complexity and approximation.

MSC:
 68M20 Performance evaluation, queueing, and scheduling in the context of computer systems 68Q17 Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) 68W25 Approximation algorithms
Full Text:
References:
 [1] Bła\.zewicz J, Ecker K, Schmidt G, Weglarz J (1993) Scheduling in computer and manufacturing systems. Springer, Berlin · Zbl 0767.90033 [2] Bła\.zewicz J, Ecker K, Pesch E, Schmidt G, Weglarz J (2007) Handbook on scheduling. Springer, Berlin [3] Bampis E, Giannakos A, König JC (1996) On the complexity of scheduling with large communication delays. Eur J Oper Res 94: 252–260 · Zbl 0947.90573 [4] Banino C, Beaumont O, Carter L, Ferrante J, Legrand A, Robert Y (2004) Scheduling strategies for master-slave tasking on heterogeneous processor platforms. IEEE Transaction Parallel Distributed Systems (4) · Zbl 1048.68533 [5] Bellman RE (1958) On a routing problem. Quarterly of Applied Mathematics 16(1): 87–90 · Zbl 0081.14403 [6] Boudet V, Cohen Y, Giroudeau R, Konig JC (2006) Complexity results for scheduling problem with non trivial topology of processors. Technical Report 06050, LIRMM, Submitted to RAIRO-RO [7] Brent R (1974) The parallel evaluation of general arithmetic expression. J ACM 21(2): 201–206 · Zbl 0276.68010 [8] Chen B, Potts CN, Woeginger GJ (1998) Handbook of combinatorial optimization (volume 3), a review of machine scheduling: Complexity, algorithms and approximability. Kluwer Academic Publishers, Dordrecht [9] Chrétienne P, Picouleau C (1995) Scheduling theory and its applications. Wiley, Scheduling with communication delays: a survey, chap 4 [10] Garey MR, Johnson DS (1979) Computers and intractability, a guide to the theory of $${$$\backslash$$mathcal{NP}}$$ -completeness. Freeman, San Francisco [11] Giroudeau R, König JC, Moulaï FK, Palaysi J (2008) Complexity and approximation for the precedence constrained scheduling problem with large communication delays. Theor Comput Sci 401((1–3): 107–119 · Zbl 1143.90012 [12] Giroudeau R (2007) Multiprocessor scheduling: theory and applications chapter 4. ARS Publishing [13] Graham R (1966) Bounds for certain multiprocessing anomalies. Bell System Tech J 45: 1563–1581 · Zbl 0168.40703 [14] Graham RL (1976) Bounds on the performance of scheduling algorithms, computer and job-shop scheduling theory. John Wiley Ltd, E.G. Coffman Edition., London [15] Graham RL, Lawler EL, Lenstra JK, Rinnooy Kan AHG (1979) Optimization and approximation in deterministic sequencing and scheduling theory: a survey. Ann Discrete Math 5: 287–326 · Zbl 0411.90044 [16] Hoogeveen H, Schuurman P, Woeginger GJ (1998) Non-approximability results for scheduling problems with minsum criteria. In: Bixby RE, Boyd EA, Ríos-Mercado RZIPCO VI, Lecture Notes in Computer Science, No.1412. Springer, Berlin, pp 353–366 [17] Hoogeveen JA, Lenstra JK, Veltman B (1994) Three, four, five, six, or the complexity of scheduling with communication delays. Oper Res Lett 16(3): 129–137 · Zbl 0816.90083 [18] Hwang J-J, Chow YC, Anger FD, Lee C-Y (1989) Scheduling precedence graphs in systems with interprocessor communication times. SIAM J Comput 18: 244–257 · Zbl 0677.68026 [19] Lahlou C (1996) Scheduling with unit processing and communication times on a ring network: approximation results. In: Proceedings of Europar. Springer, pp 539–542 [20] Lenstra JK, Rinnooy Kan AHG (1978) Complexity of scheduling under precedence constraints. Oper Res 26 · Zbl 0371.90060 [21] Lenstra JK, Rinnooy Kan AHG, Brucker P (1977) Complexity of machine scheduling problems. Ann Oper Res 1: 343–362 [22] Munier A, Hanen C (1996) An approximation algorithm for scheduling unitary tasks on m processors with communication delays. Private commun · Zbl 0967.68021 [23] Munier A, König JC (1997) A heuristic for a scheduling problem with communication delays. Oper Res 45(1): 145–148 · Zbl 0892.90104 [24] Papadimitriou CH, Yannakakis M (1990) Towards an architecture-independent analysis of parallel algorithms. SIAM J Comp 19(2): 322–328 · Zbl 0692.68032 [25] Picouleau C (1994) UET–UCT schedules on arbitrary networks. Technical report, LITP, Blaise Pascal, Université Paris VI [26] Pinedo M (1995) Scheduling : theory, Algorithms, and Systems. Prentice Hall, Englewood Cliffs · Zbl 1145.90393 [27] Rayward-Smith VJ (1987) UET scheduling with unit interprocessor communication delays. Discrete Appl Math 18: 55–71 · Zbl 0634.90031 [28] Saad R (1995) Scheduling with communication delays. JCMCC 18: 214–224 · Zbl 0833.68019 [29] Ullman JD (1975) $${$$\backslash$$mathcal{NP}}$$ -complete scheduling problems. J Comput System Sci 10: 384–393 · Zbl 0313.68054 [30] Veltman B (1993) Multiprocessor scheduling with communication delays. PhD thesis, CWI-Amsterdam, Holland · Zbl 0900.68044
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.