A linear time approximation scheme for scheduling unbounded batch machines with delivery times and inclusive processing set restrictions

Xiaofang Zhao; Shuguang Li; Xiaofang Zhao; Shuguang Li

doi:10.3934/era.2022213

Electronic Research Archive

2022, Volume 30, Issue 11: 4209-4219. doi: 10.3934/era.2022213

Previous Article Next Article

Research article

A linear time approximation scheme for scheduling unbounded batch machines with delivery times and inclusive processing set restrictions

Xiaofang Zhao ,
Shuguang Li ^,

College of Computer Science and Technology, Shandong Technology and Business University, Yantai 264005, China

Received: 20 May 2022 Revised: 15 September 2022 Accepted: 15 September 2022 Published: 21 September 2022

We consider the problem of scheduling jobs with delivery times and inclusive processing set restrictions on unbounded batch machines to minimize the maximum delivery completion time, which is equivalent to minimizing the maximum lateness from the optimization viewpoint. We develop a polynomial time approximation scheme for this strongly NP-hard problem that runs in linear time for any fixed accuracy requirement.
- scheduling,
- unbounded batch machines,
- inclusive processing set restrictions,
- maximum delivery completion time,
- polynomial time approximation scheme
Citation: Xiaofang Zhao, Shuguang Li. A linear time approximation scheme for scheduling unbounded batch machines with delivery times and inclusive processing set restrictions[J]. Electronic Research Archive, 2022, 30(11): 4209-4219. doi: 10.3934/era.2022213

Related Papers:

Abstract

We consider the problem of scheduling jobs with delivery times and inclusive processing set restrictions on unbounded batch machines to minimize the maximum delivery completion time, which is equivalent to minimizing the maximum lateness from the optimization viewpoint. We develop a polynomial time approximation scheme for this strongly NP-hard problem that runs in linear time for any fixed accuracy requirement.

References

[1]	J. Y. T. Leunga, C. Li, Scheduling with processing set restrictions: A survey, Int. J. Prod. Econ., 116 (2008), 251–262. https://doi.org/10.1016/j.ijpe.2008.09.003 doi: 10.1016/j.ijpe.2008.09.003
[2]	J. Y. T. Leunga, C. Li, Scheduling with processing set restrictions: A literature update, Int. J. Prod. Econ., 175 (2016), 1–11. https://doi.org/10.1016/j.ijpe.2014.09.038 doi: 10.1016/j.ijpe.2014.09.038
[3]	C. H. Papadimitriou, K. Steiglitz, Combinatorial optimization: algorithms and complexity, Courier Dover Publications, 1998.
[4]	R. L. Graham, E. L. Lawler, J. K. Lenstra, A. R. Kan, Optimization and approximation in deterministic sequencing and scheduling: A survey, Ann. Discrete Math., 5 (1979), 287–326. https://doi.org/10.1016/S0167-5060(08)70356-X doi: 10.1016/S0167-5060(08)70356-X
[5]	D. G. Kafura, V. Y. Shen, Task scheduling on a multiprocessor system with independent memories, SIAM J. Comput., 6 (1977), 167–187. https://doi.org/10.1137/0206014 doi: 10.1137/0206014
[6]	H. C. Hwang, S. Y. Chang, Y. Hong, A posterior competitiveness for list scheduling algorithm on machines with eligibility constraints, Asia-Pacific J. Operat. Res., 21 (2004), 117–125. https://doi.org/10.1142/S0217595904000084 doi: 10.1142/S0217595904000084
[7]	C. A. Glass, H. Kellerer, Parallel machine scheduling with job assignment restrictions, Nav. Res. Log., 54 (2007), 250–257. https://doi.org/10.1002/nav.20202 doi: 10.1002/nav.20202
[8]	J. Ou, J. Y. T. Leung, C. L. Li, Scheduling parallel machines with inclusive processing set restrictions, Nav. Res. Log., 55 (2008), 328–338. https://doi.org/10.1002/nav.20286 doi: 10.1002/nav.20286
[9]	C. L. Li, X. Wang, Scheduling parallel machines with inclusive processing set restrictions and job release times, Eur. J. Oper. Res., 200 (2010), 702–710. https://doi.org/10.1016/j.ejor.2009.02.011 doi: 10.1016/j.ejor.2009.02.011
[10]	C. N. Potts, M. Y. Kovalyov, Scheduling with batching: A review. Eur. J. Oper. Res., 120 (2000), 228–249. https://doi.org/10.1016/S0377-2217(99)00153-8 doi: 10.1016/S0377-2217(99)00153-8
[11]	M. Mathirajan, A. Sivakumar, A literature review, classification and simple meta-analysis on scheduling of batch processors in semiconductor, Int. J. Adv. Manuf. Tech., 29 (2006), 990–1001. https://doi.org/10.1007/s00170-005-2585-1 doi: 10.1007/s00170-005-2585-1
[12]	J. W. Fowler, L. Mönch, A survey of scheduling with parallel batch (p-batch) processing, Eur. J. Oper. Res., 299 (2022), 1–24. https://doi.org/10.1016/j.ejor.2021.06.012 doi: 10.1016/j.ejor.2021.06.012
[13]	J. Q. Wang, J. Y. T. Leung, Scheduling jobs with equal-processing-time on parallel machines with non-identical capacities to minimize makespan, Int. J. Prod. Econ., 156 (2014), 325–331. https://doi.org/10.1016/j.ijpe.2014.06.019 doi: 10.1016/j.ijpe.2014.06.019
[14]	P. Damodaran, D. A. Diyadawagamage, O. Ghrayeb, M. C. Velez-Gallego, A particle swarm optimization algorithm for minimizing makespan of nonidentical parallel batch processing machines, Int. J. Adv. Manuf. Tech., 58 (2012), 1131–1140. https://doi.org/10.1007/s00170-011-3442-z doi: 10.1007/s00170-011-3442-z
[15]	Z. Jia, K. Li, J. Y. T. Leung, Effective heuristic for makespan minimization in parallel batch machines with non-identical capacities, Int. J. Prod. Econ., 169 (2015), 1–10. https://doi.org/10.1016/j.ijpe.2015.07.021 doi: 10.1016/j.ijpe.2015.07.021
[16]	P. Brucker, A. Gladky, H. Hoogeveen, M. Y. Kovalyov, C. N. Potts, T. Tautenhahn, et al., Scheduling a batching machine, J. Scheduling, 1 (1998), 31–54. https://doi.org/10.1002/(SICI)1099-1425(199806)1:1<31::AID-JOS4>3.0.CO;2-R doi: 10.1002/(SICI)1099-1425(199806)1:1<31::AID-JOS4>3.0.CO;2-R
[17]	J. Y. T. Leung, Handbook of Scheduling: Algorithms, Models, and Performance Analysis, CRC Press, 2004.
[18]	L. A. Hall, D. B. Shmoys, Jackson's rule for single-machine scheduling: Making a good heuristic better, Math. Oper. Res., 17 (1992), 22–35. https://doi.org/10.1287/moor.17.1.22 doi: 10.1287/moor.17.1.22
[19]	A. P. M. Wagelmans, A. E. Gerodimos, Improved dynamic programs for some batching problems involving the maximum lateness criterion, Oper. Res. Lett., 27 (2000), 109–118. https://doi.org/10.1016/S0167-6377(00)00040-7 doi: 10.1016/S0167-6377(00)00040-7
[20]	T. E. Cheng, Z. Liu, W. Yu, Scheduling jobs with release dates and deadlines on a batch processing machine, IIE Trans., 33 (2001), 685–690. https://doi.org/10.1080/07408170108936864 doi: 10.1080/07408170108936864
[21]	S. Bai, F. Zhang, S. Li, Q. Liu, Scheduling an unbounded batch machine to minimize maximum lateness, Front. Algorithmics, (2007), 172–177. https://doi.org/10.1007/978-3-540-73814-5_16 doi: 10.1007/978-3-540-73814-5_16
[22]	L. L. Liu, C. T. Ng, T. C. E. Cheng, Scheduling jobs with release dates on parallel batch processing machines, Discrete Appl. Math., 157 (2009), 1825–1830. https://doi.org/10.1016/j.dam.2008.12.012 doi: 10.1016/j.dam.2008.12.012
[23]	Y. Fang, X. Lu, P. Liu, Online batch scheduling on parallel machines with delivery times, Theor. Comput. Sci., 412 (2011), 5333–5339. https://doi.org/10.1016/j.tcs.2011.06.011 doi: 10.1016/j.tcs.2011.06.011
[24]	P. Liu, X. Lu, Online unbounded batch scheduling on parallel machines with delivery times, J. Comb. Optim., 29 (2015), 228–236. https://doi.org/10.1007/s10878-014-9706-4 doi: 10.1007/s10878-014-9706-4
[25]	L. A. Hall, D. B. Shmoys, Approximation schemes for constrained scheduling problems, in Proceedings of the 30th Annual IEEE Symposium on Foundations of Computer Science, (1989), 134–139. https://doi.org/10.1109/SFCS.1989.63468
[26]	M. Mastrolilli, Efficient approximation schemes for scheduling problems with release dates and delivery times, J. Scheduling, 6 (2003), 521–531. https://doi.org/10.1023/A:1026272526225 doi: 10.1023/A:1026272526225
[27]	J. R. Jackson, Scheduling a production line to minimize maximum tardiness, DTIC Document, 1955.
[28]	M. Mnich, A. Wiese, Scheduling and fixed-parameter tractability, Math. Program., 154 (2015), 533–562. https://doi.org/10.1007/s10107-014-0830-9 doi: 10.1007/s10107-014-0830-9
[29]	M. Mnich, R. van Bevern, Parameterized complexity of machine scheduling: 15 open problems, Comput. & Oper. Res., 100 (2018), 254–261. https://doi.org/10.1016/j.cor.2018.07.020 doi: 10.1016/j.cor.2018.07.020

Reader Comments

Your name:*

Email:*
© 2022 the Author(s), licensee AIMS Press. This is an open access article distributed under the terms of the Creative Commons Attribution License (http://creativecommons.org/licenses/by/4.0)