×

Scheduling with constrained processor allocation for interval orders. (English) Zbl 0779.90042

Summary: We consider a generalization of the precedence constrained scheduling problem of a set of unit execution time (UET) jobs on a set of processors or machines. Each job is associated a subset \(P(j)\) of the processors, and a job can only be executed on one of the processors in \(P(j)\). First, we show that this problem is NP-complete for interval orders. Next, the problem can be solved in polynomial time for interval orders, if the deadline is constant. Last, we give a heuristic for the scheduling problem restricted to interval orders with approximation ratio \(O(\log(| P|))\).

MSC:

90B35 Deterministic scheduling theory in operations research
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Chang, R. S.; Lee, R. C.T., On a scheduling problem where a job can be executed only by a limited number of processors, Computers Ops Res., 15, 471-478 (1988) · Zbl 0646.90045
[2] Kellerer, H.; Woeginger, G. J., UET-scheduling with constrained processor allocation, Computers Ops Res., 19, 1-8 (1992) · Zbl 0751.90038
[3] Ullman, J. D., NP-complete scheduling problems, J. Comput. Syst. Sci., 10, 384-393 (1975) · Zbl 0313.68054
[4] Hu, T. C., Parallel sequencing and assembly line problems, Ops Res., 9, 841-848 (1961)
[5] Papadimitriou, C. H.; Yannakakis, M., Scheduling interval-ordered tasks, SIAM J. Comput., 8, 405-409 (1979) · Zbl 0421.68040
[6] Goyal, D. K., (Scheduling processor bound systems. Technical report (1976), Washington State University, Pullman), CS-76-036
[7] Bernstein, D.; Rodeh, M.; Gertner, I., On the complexity of scheduling problems for parallel pipelined machines, IEEE Trans. Computers, 38, 1308-1313 (1989) · Zbl 1395.90144
[8] Jansen, K., (Analyse of scheduling problems with typed task systems. Technical report (1992), University of Trier: University of Trier Germany), 389, and to appear in Disc. appl. math..
[9] Lenstra, J. K.; Kan, A. H.G. Rinnooy, Complexity of scheduling under precedence constraints, Ops Res., 26, 22-35 (1978) · Zbl 0371.90060
[10] Chen, Y. L.; Chin, Y. H., Scheduling unit-time jobs on processors with different capabilities, Computers Ops Res., 16, 409-417 (1989) · Zbl 0674.90051
[11] Garey, M. R.; Johnson, D. S., (Computers and Intractability: A Guide to the Theory of NP-Completeness (1979), Freeman: Freeman New York) · Zbl 0411.68039
[12] Johnson, D. S., Approximation algorithms for combinatorial problems, J. Comput. Syst. Sci., 9, 256-278 (1974) · Zbl 0296.65036
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.