×

Scheduling multiprocessor tasks with chain constraints. (English) Zbl 0949.68505

Summary: This paper is concerned with a new model in deterministic scheduling theory, where certain tasks may require more than one processor at a time. This model is motivated by several applications of multimicroprocessor systems and it has received much attention in the last years. In the paper it is assumed that each task can be processed on any processor subset of a given task dependent size. Tasks are nonpreemptable and there are precedence constraints among them. It is proved that the problem of minimizing schedule length is NP-hard for three processors even if all the tasks have unit processing times and precedence constraints form a set of chains. Thus, it is unlikely to be solvable in polynomial time. On the other hand, two low order polynomial-time algorithms are given for the \(m\) processor case if processor requirements of the tasks in each chain are either uniform or monotonically decreasing (increasing).

MSC:

68M20 Performance evaluation, queueing, and scheduling in the context of computer systems
90B35 Deterministic scheduling theory in operations research
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Aho, A. V.; Hopcroft, J. E.; Ulmann, J. D., The Design and Analysis of Computer Algorithms (1974), Addison-Wesley: Addison-Wesley Reading, MA
[2] Błaż, J.; Drabowski, M.; Wȩglarz, J., Scheduling independent 2-processor tasks to minimize schedule length, Information Processing Letters, 18, 267-273 (1984) · Zbl 0544.68032
[3] Błażewicz, J.; Drozdowski, M.; Wȩglarz, J., Scheduling multiprocessor tasks to minimize schedule length, IEEE Transactions on Computers, 35, 389-393 (1986) · Zbl 0604.68040
[4] Błażewicz, J.; Drozdowski, M.; Schmidt, G.; de Werra, D., Scheduling independent two processor tasks on a uniform duo-processor system, Discrete Applied Mathematics, 28, 11-20 (1990) · Zbl 0715.90069
[5] Błażewicz, J.; Drozdowski, M.; Schmidt, G.; de Werra, D., Scheduling independent multiprocessor tasks on a uniform \(k\)-processor system, Parallel Computing, 20, 15-28 (1994) · Zbl 0799.68032
[6] Błażewicz, J.; Ecker, K.; Schmidt, G.; Wȩglarz, J., Scheduling in Computer and Manufacturing Systems (1993), Springer-Verlag: Springer-Verlag Berlin · Zbl 0767.90033
[7] Błażewicz, J.; Lenstra, J. K.; Rinnooy Kan, A. H.G., Scheduling subject to resource constraints: Classification and complexity, Discrete Applied Mathematics, 5, 11-24 (1983) · Zbl 0516.68037
[8] (Coffman, E. G., Computer & Job Scheduling Theory (1976), Wiley: Wiley New York) · Zbl 0359.90031
[9] Coffman, E. G.; Graham, R. L., Optimal scheduling for two-processor systems, Acta Informatica, 1, 200-213 (1972) · Zbl 0248.68023
[10] Du, J.; Leung, J. Y.-T., Complexity of scheduling parallel task systems, SIAM Journal on Discrete Mathematics, 2, 473-487 (1989) · Zbl 0676.90029
[11] French, S., Sequencing and Scheduling: An Introduction to the Mathematics of the Job-Shop (1982), Horwood: Horwood Chichester · Zbl 0479.90037
[12] Garey, M. R.; Johnson, D. S., Computers and Intractability: A Guide to the Theory of NP-completeness (1979), Freeman: Freeman San Francisco, CA · Zbl 0411.68039
[13] Graham, R. L.; Lalwer, E. L.; Lenstra, J. K.; Rinnooy Kan, A. H.G., Optimization and Approximation in deterministic sequencing and scheduling theory: A survey, Annals of Discrete Mathematics, 287-326 (1979) · Zbl 0411.90044
[14] Hu, T. C., Parallel sequencing and assembly line problems, Operations Research, 9, 841-848 (1961)
[15] Lenstra, J. K., Sequencing by enumerative methods, (Mathematical Centre Tracts, 69 (1976), Mathematisch Centrum: Mathematisch Centrum Amsterdam) · Zbl 0407.90025
[16] Liu, Z.; Sanlaville, E., Preemptive scheduling with variable profile, precedence constraints and due dates, Discrete Applied Mathematics, 58, 253-280 (1995) · Zbl 0833.90071
[17] Lloyd, E. L., Concurrent task systems, Operations Research, 29, 189-201 (1981) · Zbl 0463.68053
[18] McNaughton, R., Scheduling with deadlines and loss functions, Management Science, 12, 1-12 (1959) · Zbl 1047.90504
[19] Rinnooy Kan, A. H.G., Machine Scheduling Problems: Classification, Complexity and Computations (1976), Nijhoff: Nijhoff The Hague · Zbl 0366.90092
[20] Veltman, B., Multiprocessor scheduling with communication delays, (Ph.D. Thesis (1993), University of Eindhoven) · Zbl 0711.68017
[21] Veltman, B.; Lageweg, B. J.; Lenstra, J. K., Multiprocessor scheduling with communication delays, Parallel Computing, 16, 173-182 (1990) · Zbl 0711.68017
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.