Efficient algorithms for scheduling equal-length jobs with processing set restrictions on uniform parallel batch machines

Shuguang Li; Shuguang Li

doi:10.3934/mbe.2022502

Mathematical Biosciences and Engineering

2022, Volume 19, Issue 11: 10731-10740. doi: 10.3934/mbe.2022502

Previous Article Next Article

Research article

Efficient algorithms for scheduling equal-length jobs with processing set restrictions on uniform parallel batch machines

Shuguang Li ^,

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

Received: 28 May 2022 Revised: 10 July 2022 Accepted: 25 July 2022 Published: 28 July 2022

We consider the problem of scheduling jobs with equal lengths on uniform parallel batch machines with non-identical capacities where each job can only be processed on a specified subset of machines called its processing set. For the case of equal release times, we give efficient exact algorithms for various objective functions. For the case of unequal release times, we give efficient exact algorithms for minimizing makespan.
- scheduling,
- uniform parallel batch machines,
- processing set restrictions,
- equal job lengths,
- exact algorithms
Citation: Shuguang Li. Efficient algorithms for scheduling equal-length jobs with processing set restrictions on uniform parallel batch machines[J]. Mathematical Biosciences and Engineering, 2022, 19(11): 10731-10740. doi: 10.3934/mbe.2022502

Related Papers:

Abstract

We consider the problem of scheduling jobs with equal lengths on uniform parallel batch machines with non-identical capacities where each job can only be processed on a specified subset of machines called its processing set. For the case of equal release times, we give efficient exact algorithms for various objective functions. For the case of unequal release times, we give efficient exact algorithms for minimizing makespan.

References

[1]	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
[2]	P. Brucker, Scheduling Algorithms, 5th edition, Springer, 2007.
[3]	M. R. Garey and D. S. Johnson, Computers and intractability: a guide to the theory of NP-completeness (michael r. garey and david s. johnson), SIAM Rev., 24 (1982), 90. https://doi.org/10.1137/1024022 doi: 10.1137/1024022
[4]	E. L. Lawler, J. K. Lenstra, A. R. Kan, D. B. Shmoys, Sequencing and scheduling: Algorithms and complexity, Handb. Oper. Res. Manage. Sci., 4 (1993), 445–522. https://doi.org/10.1016/S0927-0507(05)80189-6 doi: 10.1016/S0927-0507(05)80189-6
[5]	J. Y. T. Leung, Handbook of Scheduling: Algorithms, Models, and Performance Analysis, CRC Press, 2004.
[6]	C. H. Papadimitriou, K. Steiglitz, Combinatorial optimization: Algorithms and Complexity, Courier Dover Publications, 1998.
[7]	C. L. Li, Scheduling unit-length jobs with machine eligibility restrictions, Eur. J. Oper. Res., 174 (2006), 1325–1328. https://doi.org/10.1016/j.ejor.2005.03.023 doi: 10.1016/j.ejor.2005.03.023
[8]	C. P. Low, An efficient retrieval selection algorithm for video servers with random duplicated assignment storage technique, Inf. Process. Lett., 83 (2002), 315–321, 2002. https://doi.org/10.1016/S0020-0190(02)00210-7 doi: 10.1016/S0020-0190(02)00210-7
[9]	S. Suri, C. D. Toth, Y. Zhou, Selfish load balancing and atomic congestion games, Algorithmica, 47 (2007), 79–96.
[10]	S. Kittipiyakul, T. Javidi, Delay-optimal server allocation in multiqueue multiserver systems with time-varying connectivities, IEEE Trans. Inf. Theory, 55 (2009), 2319–2333. https://doi.org/10.1109/TIT.2009.2016051 doi: 10.1109/TIT.2009.2016051
[11]	M. Shan, G. Chen, D. Luo, X. Zhu, X. Wu, Building maximum lifetime shortest path data aggregation trees in wireless sensor networks, ACM Trans. Sensor Networks, 11 (2014), 1–24. https://doi.org/10.1145/2629662 doi: 10.1145/2629662
[12]	J. P. Champati, B. Liang, Efficient minimization of sum and differential costs on machines with job placement constraints, in IEEE INFOCOM 2017-IEEE Conference on Computer Communications, (2017), 1–9. https://doi.org/10.1109/INFOCOM.2017.8057085
[13]	J. Y. T. Leung, C. L. 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
[14]	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
[15]	M. Mathirajan, A. Sivakumar, A literature review, classification and simple meta-analysis on scheduling of batch processors in semiconductor, Int. J. Adv. Manuf. Technol., 29 (2006), 990–1001. https://doi.org/10.1007/s00170-005-2585-1 doi: 10.1007/s00170-005-2585-1
[16]	L. Monch, J. W. Fowler, S. Dauzere-Peres, S. J. Mason, O. Rose, A survey of problems, solution techniques, and future challenges in scheduling semiconductor manufacturing operations, J. Scheduling, 14 (2011), 583–599. https://doi.org/10.1007/s10951-010-0222-9 doi: 10.1007/s10951-010-0222-9
[17]	P. Damodaran, D. A. Diyadawagamage, O. Ghrayeb, M. C. Vélez-Gallego, A particle swarm optimization algorithm for minimizing makespan of nonidentical parallel batch processing machines, Int. J. Adv. Manuf. Technol., 58 (2012), 1131–1140. https://doi.org/10.1007/s00170-011-3442-z doi: 10.1007/s00170-011-3442-z
[18]	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
[19]	Z. h. 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
[20]	Z. h. Jia, T. T. Wen, J. Y. T. Leung, K. Li, Effective heuristics for makespan minimization in parallel batch machines with non-identical capacities and job release times, J. Ind. Manage. Optim., 13 (2017), 977–993. http://dx.doi.org/10.3934/jimo.2016057 doi: 10.3934/jimo.2016057
[21]	S. Li, Approximation algorithms for scheduling jobs with release times and arbitrary sizes on batch machines with non-identical capacities, Eur. J. Oper. Res., 263 (2017), 815–826. https://doi.org/10.1016/j.ejor.2017.06.021 doi: 10.1016/j.ejor.2017.06.021
[22]	S. Li, Parallel batch scheduling with inclusive processing set restrictions and non-identical capacities to minimize makespan, Eur. J. Oper. Res., 260 (2017), 12–20, 2017. https://doi.org/10.1016/j.ejor.2016.11.044 doi: 10.1016/j.ejor.2016.11.044
[23]	S. Li, Parallel batch scheduling with nested processing set restrictions, Theor. Comput. Sci., 689 (2017), 117–125. https://doi.org/10.1016/j.tcs.2017.06.003 doi: 10.1016/j.tcs.2017.06.003
[24]	Y. Lin, W. Li, Parallel machine scheduling of machine-dependent jobs with unit-length, Eur. J. Oper. Res., 156 (2004), 261–266. https://doi.org/10.1016/S0377-2217(02)00914-1 doi: 10.1016/S0377-2217(02)00914-1
[25]	N. J. Harvey, R. E. Ladner, L. Lovasz, T. Tamir, Semi-matchings for bipartite graphs and load balancing, J. Algorithms, 59 (2006), 53–78. https://doi.org/10.1016/j.jalgor.2005.01.003 doi: 10.1016/j.jalgor.2005.01.003
[26]	P. Brucker, B. Jurisch, A. Kramer, Complexity of scheduling problems with multi-purpose machines, Ann. Oper. Res., 70 (1997), 57–73. https://doi.org/10.1023/A:1018950911030 doi: 10.1023/A:1018950911030
[27]	K. Lee, Y. T. Leung, M. L. Pinedo, Scheduling jobs with equal processing times subject to machine eligibility constraints, J. Scheduling, 14 (2011), 27–38. https://doi.org/10.1007/s10951-010-0190-0 doi: 10.1007/s10951-010-0190-0
[28]	D. Shabtay, S. Karhi, D. Oron, Multipurpose machine scheduling with rejection and identical job processing times, J. Scheduling, 18 (2015), 75–88. https://doi.org/10.1007/s10951-014-0386-9 doi: 10.1007/s10951-014-0386-9
[29]	J. Hong, K. Lee, M. L. Pinedo, Scheduling equal length jobs with eligibility restrictions, Ann. Oper. Res., 285 (2020), 295–314. https://doi.org/10.1007/s10479-019-03172-8 doi: 10.1007/s10479-019-03172-8
[30]	X. Jiang, K. Lee, M. L. Pinedo, Ideal schedules in parallel machine settings, Eur. J. Oper. Res., 290 (2021), 422–434. https://doi.org/10.1016/j.ejor.2020.08.010 doi: 10.1016/j.ejor.2020.08.010
[31]	C. Jing, W. Huang, L. Zhang, H. Zhang, Scheduling high multiplicity jobs on parallel multi-purpose machines with setup times and machine available times, Asia Pac. J. Oper. Res., 2022 (2022), 2250012. https://doi.org/10.1142/S0217595922500129 doi: 10.1142/S0217595922500129
[32]	M. L. Pinedo, Scheduling: Theory, Algorithms and Systems, Spring, 2018.
[33]	C. A. Glass, H. R. Mills, Scheduling unit length jobs with parallel nested machine processing set restrictions, Comput. Oper. Res., 33 (2006), 620–638. https://doi.org/10.1016/j.cor.2004.07.010 doi: 10.1016/j.cor.2004.07.010
[34]	C. L. Li, Q. Li, Scheduling jobs with release dates, equal processing times, and inclusive processing set restrictions, J. Oper. Res. Soc., 66 (2015), 516–523. https://doi.org/10.1057/jors.2014.22 doi: 10.1057/jors.2014.22
[35]	C. L. Li, K. Lee, A note on scheduling jobs with equal processing times and inclusive processing set restrictions, J. Oper. Res. Soc., 67 (2016), 83–86. https://doi.org/10.1057/jors.2015.56 doi: 10.1057/jors.2015.56
[36]	L. Liu, C. Ng, T. Cheng, Scheduling jobs with release dates on parallel batch processing machines to minimize the makespan, Optim. Lett., 8 (2014), 307–318. https://doi.org/10.1007/s11590-012-0575-4 doi: 10.1007/s11590-012-0575-4
[37]	O. Ozturk, M. L. Espinouse, M. D. Mascolo, A. Gouin, Makespan minimisation on parallel batch processing machines with non-identical job sizes and release dates, Int. J. Prod. Res., 50 (2011), 1–14. https://doi.org/10.1080/00207543.2011.641358 doi: 10.1080/00207543.2011.641358
[38]	X. Li, H. Chen, B. Du, Q. Tan, Heuristics to schedule uniform parallel batch processing machines with dynamic job arrivals, Int. J. Comput. Integr. Manuf., 26 (2012), 474–486. https://doi.org/10.1080/0951192X.2012.731612 doi: 10.1080/0951192X.2012.731612
[39]	S. Zhou, M. Liu, H. Chen, X. Li, An effective discrete differential evolution algorithm for scheduling uniform parallel batch processing machines with non-identical capacities and arbitrary job sizes, Int. J. Prod. Econ., 179 (2016), 1–11. https://doi.org/10.1016/j.ijpe.2016.05.014 doi: 10.1016/j.ijpe.2016.05.014
[40]	R. K. Ahuja, T. L. Magnanti, J. B. Orlin, Network Flows, Theory, Algorithms, and Applications, Prentice Hall, Englewood Cliffs, 1993.
[41]	M. L. Fredman, R. E. Tarjan, Fibonacci heaps and their uses in improved network optimization algorithms, J. ACM, 34 (1987), 596–615. https://doi.org/10.1145/28869.28874 doi: 10.1145/28869.28874
[42]	J. E. Hopcroft, R. M. Karp, An ${{n}^{5/2}}$ algorithm for maximum matching in bipartite graphs, SIAM J. Comput., 2 (1973), 225–231. https://doi.org/10.1137/0202019 doi: 10.1137/0202019
[43]	C. C. Wu, D. Bai, X. Zhang, S. R. Cheng, J. C. Lin, Z. L. Wu, et al., A robust customer order scheduling problem along with scenario-dependent component processing times and due dates, J. Manuf. Syst., 58 (2021), 291–305. https://doi.org/10.1016/j.jmsy.2020.12.013 doi: 10.1016/j.jmsy.2020.12.013
[44]	C. C. Wu, J. N. Gupta, W. C. Lin, S. R. Cheng, Y. L. Chiu, J. H. Chen, et al., Robust scheduling of two-agent customer orders with scenario-dependent component processing times and release dates, Mathematics, 10 (2022), 1545. https://doi.org/10.3390/math10091545 doi: 10.3390/math10091545
[45]	C. C. Wu, A. Azzouz, J. Y. Chen, J. Xu, W. L. Shen, L. Lu, et al., A two-agent one-machine multitasking scheduling problem solving by exact and metaheuristics, Complex Intell. Syst., 8 (2022), 199–212. https://doi.org/10.1007/s40747-021-00355-4 doi: 10.1007/s40747-021-00355-4

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)