Abstract
This paper considers scheduling of parallel tasks in a multiprogrammed, multiprocessorsystem. The problem of preemptive scheduling of n tasks on m processors to minimizemakespan is studied. Task j starts and finishes with sequential parts head j and tail j , respectively.Between these two, j runs its parallel part parallel j . The sequential parts have to beexecuted by one processor at a time. The parallel part can be executed by more than oneprocessor at a time. It is shown that this problem is NP‐hard in the strong sense even if thereare fewer tasks than processors. A linear program is presented to find an optimal schedulefor a given sequence of completion times of heads and start times of tails. If the optimalschedule for tasks longer than the mth longest task is given, an efficient, polynomial‐timemerging algorithm is proposed to obtain an optimal schedule for all n tasks. The algorithmbuilds an optimal schedule with at most m ‐ 1 tasks running their parallel parts on morethan one processor at a time, the remaining tasks run their parallel parts as if they weresequential. Therefore, there always exist optimal schedules with only a few tasks exploitingthe parallel processing capability of a parallel system. Finally, polynomially solvable casesare discussed, and the worst‐case performance of three heuristics for the problem is analyzed.
Similar content being viewed by others
References
L. Bianco, J. Błażewicz, P. Dell'Olmo and M. Drozdowski, Scheduling preemptive multiprocessor tasks on dedicated processors, Performance Evaluation 20(1994)361-371.
J. Błażewicz, P. Dell'Olmo, M. Drozdowski and M.G. Speranza, Scheduling multiprocessor tasks on three dedicated processors, Inf. Proc. Letters 41(1992)275-280, Corrigendum Inf. Proc. Letters 49(1994)269-270.
J. Błażewicz, M. Drabowski and J. Włglarz, Scheduling multiprocessor tasks to minimize schedule length, IEEE Trans. Comput. C-35(1986)389-393.
J.L. Bruno and P.J. Downey, Probabilistic bounds on the performance of list scheduling, SIAM J. on Computing 15(1986)409-417.
E.G. Coffman, Jr., Computer and Job-shop Scheduling Theory, Wiley, 1976.
D. Dolev and M. Warmuth, Profile scheduling of opposing forests and level orders, SIAM J. on Algebraic and Discrete Methods 6(1985)665-687.
J. Du and J.Y-T. Leung, Complexity of scheduling parallel task systems, SIAM J. on Discrete Mathematics 2(1989)473-487.
M.R. Garey and D.S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W.H. Freeman, San Francisco, 1979.
M.R. Garey, D.S. Johnson, R.E. Tarjan and M. Yannakakis, Scheduling opposing forests, SIAM J. on Algebraic and Discrete Methods 4(1983)72-93.
D. Ghosal, G. Serazzi and S. Tripathi, The processor working set and its use in scheduling multiprocessor systems, IEEE Transactions on Software Engineering 17(1991)443-453.
R.L. Graham, E.L. Lawler, J.K. Lenstra and A.H.G. Rinnooy Kan, Optimization and approximation in deterministic sequencing and scheduling: A survey, Ann. Discrete Math. 5(1979)287-326.
J.L. Gustafson, R.E. Benner, M.P. Sears and T.D. Sullivan, A radar simulation for a 1024-processor hypercube, in: Proceedings of Supercomputing 1989, ACM Press, New York, 1989, pp. 96-105.
M. Kubale, The complexity of scheduling independent two-processor tasks on dedicated processors, Inf. Proc. Letters 24(1987)141-147.
E.L. Lloyd, Concurrent task systems, Oper. Res. 29(1981)189-201.
R. McNaughton, Scheduling with deadlines and loss functions, Management Science 6(1959)1-12.
R.R. Muntz and E.G. Coffman, Jr., Preemptive scheduling of real-time tasks on multiprocessor systems, Journal of ACM 17(1970)324-338.
K.C. Sevcik, Application scheduling and processor allocation in multiprogrammed parallel processing systems, Performance Evaluation 19(1994)107-140.
J.D. Ullman, NP-complete scheduling problems, J. Comput. Syst. Sci. 10(1975)384-393.
B. Veltman, B.J. Lageweg and J.K. Lenstra, Multiprocessor scheduling with communication delays, Parallel Computing 16(1990)173-182.
Rights and permissions
About this article
Cite this article
Drozdowski, M., Kubiak, W. Scheduling parallel tasks withsequential heads and tails. Annals of Operations Research 90, 221–246 (1999). https://doi.org/10.1023/A:1018964732122
Issue Date:
DOI: https://doi.org/10.1023/A:1018964732122