×

Parallel machine scheduling with nested job assignment restrictions. (English) Zbl 1182.90048

Summary: We derive a polynomial time approximation scheme for a special case of makespan minimization on unrelated machines.

MSC:

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

References:

[1] Lawler, E. L.; Lenstra, J. K.; Rinnooy Kan, A. H.G.; Shmoys, D. B., Sequencing and scheduling: Algorithms and complexity, (Graves, S. C.; Rinnooy Kan, A. H.G.; Zipkin, P. H., Logistics of Production and Inventory. Logistics of Production and Inventory, Handbooks in Operations Research and Management Science, vol. 4 (1993), North-Holland: North-Holland Amsterdam), 445-522
[2] Lenstra, J. K.; Shmoys, D. B.; Tardos, E., Approximation algorithms for scheduling unrelated parallel machines, Mathematical Programming, 46, 259-271 (1990) · Zbl 0715.90063
[3] T. Ebenlendr, M. Krcal, J. Sgall, Graph balancing: A special case of scheduling unrelated parallel machines, in: Proceedings of the 19th ACM-SIAM Symposium on Discrete algorithms, SODA’2008, 2008, pp. 483-490; T. Ebenlendr, M. Krcal, J. Sgall, Graph balancing: A special case of scheduling unrelated parallel machines, in: Proceedings of the 19th ACM-SIAM Symposium on Discrete algorithms, SODA’2008, 2008, pp. 483-490 · Zbl 1192.90070
[4] Schuurman, P.; Woeginger, G. J., Polynomial time approximation algorithms for machine scheduling: Ten open problems, Journal of Scheduling, 2, 203-213 (1999) · Zbl 0938.90032
[5] Hwang, H. C.; Chang, S. Y.; Lee, K., Parallel machine scheduling under a grade of service provision, Computers and Operations Research, 31, 2055-2061 (2004) · Zbl 1074.68529
[6] Glass, C. A.; Kellerer, H., Parallel machine scheduling with job assignment restrictions, Naval Research Logistics, 54, 250-257 (2007) · Zbl 1149.90058
[7] Ou, J.; Leung, J. Y.T.; Li, C. L., Scheduling parallel machines with inclusive processing set restrictions, Naval Research Logistics, 55, 328-338 (2008) · Zbl 1153.90432
[8] Glass, C. A.; Mills, H. R., Scheduling unit length jobs with parallel nested machine processing set restrictions, Computers and Operations Research, 33, 620-638 (2006) · Zbl 1077.90526
[9] Hochbaum, D. S.; Shmoys, D. B., Using dual approximation algorithms for scheduling problems: Theoretical and practical results, Journal of the ACM, 34, 144-162 (1987)
[10] Alon, N.; Azar, Y.; Woeginger, G. J.; Yadid, T., Approximation schemes for scheduling on parallel machines, Journal of Scheduling, 1, 55-66 (1998) · Zbl 0909.90168
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.