Parallel machine scheduling of machine-dependent jobs with unit-length. (English) Zbl 1045.90029

Summary: We study the parallel machine scheduling problem with unit-length jobs in which each job \(j\) is only allowed to be processed on a specified subset \(\mathcal M_j\) of machines. For the problem \(P| p_j=1,\mathcal M_j| C_{\max}\) where the subset family \(\{ \mathcal M_j \}\) is nested, M. Pinedo [Scheduling: Theory, Algorithms, and Systems, Prentice-Hall, Englewood Cliffs, NJ (1995)] established an least flexible job first algorithm. We further present polynomial algorithms for the problem with general subset family \(\{ \mathcal M_j \}\). As a generalization of the problem for nested family, we consider the problem for convex subset family \(\{ \mathcal M_j \}\) and present an efficient algorithm for solving it.


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


[1] Bhatia, R.; Khuller, S.; Naor, J., The loading time scheduling problem, Journal of Algorithms, 36, 1-33 (2000) · Zbl 0959.68008
[2] Centeno, G.; Armacost, R. L., Parallel machine scheduling with release time and machine eligibility restrictions, Computers and Industrial Engineering, 33, 273-276 (1997)
[3] Chen, B.; Potts, C. N.; Woeginger, G. J., A review of machine scheduling: Complexity, algorithms and approximability, (Du, D. Z.; Pardalos, P. M., Handbook of Combinatorial Optimization (1998), Kluwer Academic Publishers: Kluwer Academic Publishers Dordrecht), 21-169 · Zbl 0944.90022
[4] Cheng, T. C.E.; Sin, C. C.S., A state-of-the-art review of parallel-machine scheduling research, European Journal of Operational Research, 47, 271-292 (1990) · Zbl 0707.90053
[5] Golumbic, M. C., Algorithmic Graph Theory and Perfect Graphs (1980), Academic Press: Academic Press New York · Zbl 0541.05054
[6] Lawler, E. L., Combinatorial Optimization: Networks and Matroids (1976), Holt, Rinehart & Winston: Holt, Rinehart & Winston New York · Zbl 0358.68059
[7] Mokotoff, E., Parallel machine scheduling problems: A survey, Asia-Pacific Journal of Operational Research, 18, 193-242 (2001) · Zbl 1042.90564
[8] Papadimitriou, C. H.; Steiglitz, K., Combinatorial Optimization: Algorithms and Complexity (1982), Prentice-Hall: Prentice-Hall Englewood Cliffs, NJ · Zbl 0503.90060
[9] Pinedo, M., Scheduling: Theory, Algorithms, and Systems (1995), Prentice-Hall: Prentice-Hall Englewood Cliffs, NJ · Zbl 1145.90393
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.