Scheduling parallel machines with inclusive processing set restrictions and job release times. (English) Zbl 1177.90170

Summary: We consider the problem of scheduling a set of jobs with different release times on parallel machines so as to minimize the makespan of the schedule. The machines have the same processing speed, but each job is compatible with only a subset of those machines. The machines can be linearly ordered such that a higher-indexed machine can process all those jobs that a lower-indexed machine can process. We present an efficient algorithm for this problem with a worst-case performance ratio of 2. We also develop a polynomial time approximation scheme (PTAS) for the problem, as well as a fully polynomial time approximation scheme (FPTAS) for the case in which the number of machines is fixed.


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


[1] Bar-Noy, A.; Freund, A.; Naor, J., On-line load balancing in a hierarchical server topology, SIAM Journal on Computing, 31, 527-549 (2001) · Zbl 0994.68069
[2] 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, 3 (1998), Kluwer Academic Publishers: Kluwer Academic Publishers Boston), 21-169 · Zbl 0944.90022
[3] Chekuri, C.; Motwani, R.; Natarajan, B.; Stein, C., Approximation techniques for average completion time scheduling, SIAM Journal on Computing, 31, 146-166 (2001) · Zbl 0992.68066
[4] Fishkin, A. V.; Jansen, K.; Mastrolilli, M., Grouping techniques for scheduling problems: Simpler and faster, Algorithmica, 51, 183-199 (2008) · Zbl 1159.90403
[5] Glass, C. A.; Kellerer, H., Parallel machine scheduling with job assignment restrictions, Naval Research Logistics, 54, 250-257 (2007) · Zbl 1149.90058
[6] 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
[8] Horowitz, E.; Sahni, S., Exact and approximate algorithms for scheduling nonidentical processors, Journal of the Association for Computing Machinery, 23, 317-327 (1976) · Zbl 0329.68041
[10] 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
[11] Jansen, K.; Porkolab, L., Improved approximation schemes for scheduling unrelated parallel machines, Mathematics of Operations Research, 26, 324-338 (2001) · Zbl 1082.90525
[12] Ji, M.; Cheng, T. C.E., An FPTAS for parallel-machine scheduling under a grade of service provision to minimize makespan, Information Processing Letters, 108, 171-174 (2008) · Zbl 1191.68102
[13] Jiang, Y., Online scheduling on parallel machines with two GoS levels, Journal of Combinatorial Optimization, 16, 28-38 (2008) · Zbl 1176.90221
[14] Jiang, Y.-W.; He, Y.; Tang, C.-M., Optimal online algorithms for scheduling on two identical machines under a grade of service, Journal of Zhejiang University Science A, 7, 309-314 (2006) · Zbl 1108.90314
[15] Kafura, D. G.; Shen, V. Y., Task scheduling on a multiprocessor system with independent memories, SIAM Journal on Computing, 6, 167-187 (1977) · Zbl 0349.68027
[16] Lai, T.-H.; Sahni, S., Preemptive scheduling of a multiprocessor system with memories to minimize maximum lateness, SIAM Journal on Computing, 13, 690-704 (1984) · Zbl 0548.68027
[17] 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., Handbooks in Operations Research and Management Science. Handbooks in Operations Research and Management Science, Logistics of Production and Inventory, vol. 4 (1993), North-Holland: North-Holland Amsterdam), 445-522
[18] Lenstra, H. W., Integer programming with a fixed number of variables, Mathematics of Operations Research, 8, 538-548 (1983) · Zbl 0524.90067
[19] Lenstra, J. K.; Shmoys, D. B.; Tardos, E., Approximation algorithms for scheduling unrelated parallel machines, Mathematical Programming, 46, 259-271 (1990) · Zbl 0715.90063
[20] Leung, J. Y.-T.; Li, C.-L., Scheduling with processing set restrictions: A survey, International Journal of Production Economics, 116, 251-262 (2008)
[21] Mastrolilli, M., Efficient approximation schemes for scheduling problems with release dates and delivery times, Journal of Scheduling, 6, 521-531 (2003) · Zbl 1154.90473
[22] Mastrolilli, M., Scheduling to minimize max flow time: Off-line and on-line algorithms, International Journal of Foundations of Computer Science, 15, 385-401 (2004) · Zbl 1067.68026
[23] 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
[24] Park, J.; Chang, S. Y.; Lee, K., Online and semi-online scheduling of two machines under a grade of service provision, Operations Research Letters, 34, 692-696 (2006) · Zbl 1112.90036
[25] Schulz, A. S.; Skutella, M., Scheduling unrelated machines by randomized rounding, SIAM Journal on Discrete Mathematics, 15, 450-469 (2002) · Zbl 1055.90040
[26] Shchepin, E. V.; Vakhania, N., An optimal rounding gives a better approximation for scheduling unrelated machines, Operations Research Letters, 33, 127-133 (2005) · Zbl 1099.90024
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.