×

Complexity of scheduling multiprocessor tasks with prespecified processors allocations. (English) Zbl 0938.68671


MSC:

68Q25 Analysis of algorithms and problem complexity
68M20 Performance evaluation, queueing, and scheduling in the context of computer systems
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Bianco, L.; Dell’Olmo, P.; Speranza, M. G., On scheduling independent tasks with dedicated resources. Program and Abstracts, 14th International Symposium Mathematical Programming, Amsterdam (1991)
[2] Blazewicz, J.; Dell’Olmo, P.; Drozdowski, M.; Speranza, M. G., Scheduling multiprocessor tasks on three dedicated processors, Inform. Process. Lett., 41, 275-280 (1992) · Zbl 0776.68023
[3] Blazewicz, J.; Drabowski, M.; Weglarz, J., Scheduling multiprocessor tasks to minimize schedule length, IEEE Trans. Comput., 35, 389-393 (1986) · Zbl 0604.68040
[4] Blazewicz, J.; Lenstra, J. K.; Rinnooy Kan, A. H.G., Scheduling subject to resource constraints: classification and complexity, Discrete Appl. Math., 5, 11-24 (1983) · Zbl 0516.68037
[5] Bozoki, G.; Richard, J. P., A branch-and-bound algorithm for the continuous-process task shop scheduling problem, AIIE Trans., 2, 246-252 (1970)
[6] 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
[7] Graham, R. L.; Lawler, E. L.; Lenstra, J. K.; Rinnooy Kan, A. H.G., Optimization and approximation in deterministic sequencing and scheduling: a survey, Ann. Discrete Math., 5, 287-326 (1979) · Zbl 0411.90044
[8] Krawczyk, H.; Kubale, M., An approximation algorithm for diagnostic test scheduling in multiprocessor systems, IEEE Trans. Comput., 34, 869-872 (1985)
[9] Kubale, M., The complexity of scheduling independent two-processor tasks on dedicated processors, Inform. Process. Lett., 24, 141-147 (1987) · Zbl 0653.68015
[10] Lenstra, H. W., Integer programming with a fixed number of variables, Math. Oper. Res., 8, 538-548 (1983) · Zbl 0524.90067
[11] Lenstra, J. K.; Rinnooy Kan, A. H.G.; Brucker, P., Complexity of machine scheduling problems, Ann. Discrete Math., 1, 343-362 (1977) · Zbl 0301.90025
[12] Martello, S.; Toth, P., Knapsack Problems: Algorithms and Computer Implementations (1990), Wiley: Wiley Chichester · Zbl 0708.68002
[13] Veltman, B.; Lageweg, B. J.; Lenstra, J. K., Multiprocessor scheduling with communication delays, Parallel Comput., 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.