Scheduling Jobs with Release and Delivery Times Subject to Nested Eligibility Constraints

doi:10.1007/s40305-019-00268-7

Abstract

Abstract: The problem of scheduling jobs with release and delivery time subject to machine eligibility constraints is considered. The eligible sets of the jobs are nested, and preemptions are not allowed. The goal is to minimize the maximum delivery completion time, i.e., the time by which all jobs are delivered. For the special case of equal release time, a 2-approximation algorithm is presented whose running time depends linearly on the number of jobs. For the general case of unequal release time, a polynomial time approximation scheme is derived.

Key words: Scheduling, Nested eligibility constraints, Release time, Delivery time, Polynomial time approximation scheme

CLC Number:

90B35
68M20

Yu-Zhong Zhang, Shu-Guang Li. Scheduling Jobs with Release and Delivery Times Subject to Nested Eligibility Constraints[J]. Journal of the Operations Research Society of China, 2021, 9(1): 63-77.

TrendMD

References

[1] Graham,R.L.,Lawler,E.L.,Lenstra,J.K.,Kan,A.R.:Optimizationandapproximationindeterministic sequencing and scheduling:a survey. Ann. Discret. Math. 5, 287-326(1979)
[2] Hall, L.A., Shmoys, D.B.:Jackson's rule for single-machine scheduling:making a good heuristic better. Math. Oper. Res. 17, 22-35(1992)
[3] Leung, J.Y.-T., Li, C.-L.:Scheduling with processing set restrictions:a survey. Int. J. Prod. Econ. 116(2), 251-262(2008)
[4] Leung, J.Y.-T., Li, C.-L.:Scheduling with processing set restrictions:a literature update. Int. J. Prod. Econ. 175, 1-11(2016)
[5] Lenstra, J.K., Shmoys, D.B., Tardos, É.:Approximation algorithms for scheduling unrelated parallel machines. Math. Program. 46, 259-271(1990)
[6] Shchepin, E.V., Vakhania, N.:An optimal rounding gives a better approximation for scheduling unrelated machines. Oper. Res. Lett. 33, 127-133(2005)
[7] Schuurman, P., Woeginger, G.J.:Polynomial time approximation algorithms for machine scheduling:ten open problems. J. Sched. 2, 203-213(1999)
[8] Ebenlendr, T., Krcal, M., Sgall, J.:Graph balancing:a special case of scheduling unrelated parallel machines. In:Proceedings of the 19th ACM-SIAM Symposium on Discrete algorithms, pp. 483-490(2008)
[9] Lawler, E.L., Lenstra, J.K., Kan, A.H.R., Shmoys, D.B.:Sequencing and scheduling:algorithms and complexity. Handb. Oper. Res. Manag. Sci. 4, 445-522(1993)
[10] Chen, B., Potts, C.N., Woeginger, G.J.:A review of machine scheduling:complexity, algorithms and approximability. In:Du DZ., Pardalos P.M. (eds), Handbook of Combinatorial Optimization. Springer, US, pp. 1493-1641(1998)
[11] Kafura, D.G., Shen, V.:Task scheduling on a multiprocessor system with independent memories. SIAM J. Comput. 6, 167-187(1977)
[12] Hwang, H.-C., Chang, S.Y., Lee, K.:Parallel machine scheduling under a grade of service provision. Comput. Oper. Res. 31, 2055-2061(2004)
[13] Glass, C.A., Kellerer, H.:Parallel machine scheduling with job assignment restrictions. Nav. Res. Logist. 54, 250-257(2007)
[14] Ou, J., Leung, J.Y.T., Li, C.L.:Scheduling parallel machines with inclusive processing set restrictions. Nav. Res. Logist. 55(4), 328-338(2008)
[15] Li, C.-L., Wang, X.:Scheduling parallel machines with inclusive processing set restrictions and job release times. Eur. J. Oper. Res. 200(3), 702-710(2010)
[16] Huo, Y., Leung, J.Y.-T.:Parallel machine scheduling with nested processing set restrictions. Eur. J. Oper. Res. 204, 229-236(2010)
[17] Huo, Y., Leung, J.Y.-T.:Fast approximation algorithms for job scheduling with processing set restrictions. Theo. Comput. Sci. 411, 3947-3955(2010)
[18] Muratore, G., Schwarz, U.M., Woeginger, G.J.:Parallel machine scheduling with nested job assignment restrictions. Oper. Res. Lett. 38, 47-50(2010)
[19] Epstein, L., Levin, A.:Scheduling with processing set restrictions:PTAS results for several variants. Int. J. Prod. Econ. 133, 586-595(2011)
[20] Glass, C.A., Mills, H.R.:Scheduling unit length jobs with parallel nested machine processing set restrictions. Comput. Oper. Res. 33, 620-638(2006)
[21] Li, S.:Parallel machine scheduling with nested processing set restrictions and job delivery times. Math. Prob. Eng. (2016). https://doi.org/10.1155/2016/3203728
[22] Leung, J.Y.:Handbook of Scheduling:Algorithms, Models, and Performance Analysis. CRC Press, Boca Raton (2004)
[23] Lenstra, J.K., Kan, A.R., Brucker, P.:Complexity of machine scheduling problems. Ann. Discret. Math. 1, 343-362(1977)
[24] Horn, W.A.:Some simple scheduling algorithms. Nav. Res. Logist. Q. 21, 177-185(1974)
[25] Simons, B., Warmuth, M.:A fast algorithm for multiprocessor scheduling of unit-length jobs. SIAM J. Comput. 18, 690-710(1989)
[26] Carlier, J.:Scheduling jobs with release dates and tails on identical parallel machines to minimize the makespan. Eur. J. Oper. Res. 29, 298-306(1987)
[27] Gharbi, A., Haouari, M.:Minimizing makespan on parallel machines subject to release dates and delivery times. J. Sched. 5, 329-355(2002)
[28] Neron, E., Tercinet, F., Sourd, F.:Search tree based approaches for parallel machine scheduling. Comput. Oper. Res. 35(4), 1127-1137(2008)
[29] Hall, L.A., Shmoys, D.B.:Approximation schemes for constrained scheduling problems. In:Proceedings of the 30th Annual IEEE Symposium on Foundations of Computer Science, pp. 134-139(1989)
[30] Mastrolilli, M.:Efficient approximation schemes for scheduling problems with release times and delivery times. J. Sched. 6, 521-531(2003)
[31] Papadimitriou, C.H., Steiglitz, K.:Combinatorial Optimization:Algorithms and Complexity. Courier Dover Publications, New York (1998)
[32] Pinedo, M.L.:Scheduling-Theory, Algorithms and Systems. Prentice Hall, New York (1995)
[33] Jackson, J.R.:Scheduling a Production Line to Minimize Maximum Tardiness. DTIC Document, Virginia (1955)