Makespan minimization on two parallel dedicated machines under resource constraints

Huai-Che Hong; Elaine Yi-Ling Wu; Bertrand M.T. Lin; Huai-Che Hong; Elaine Yi-Ling Wu; Bertrand M.T. Lin

doi:10.3934/jimo.2026180

Journal of Industrial and Management Optimization

2026, Volume 22, Issue 10: 5227-5246. doi: 10.3934/jimo.2026180

Previous Article Next Article

Research article Special Issues

Makespan minimization on two parallel dedicated machines under resource constraints

1.
Institute of Information Management, Institute of Hospital and Health Care Administration, National Yang Ming Chiao Tung University, Hsinchu 300093, Taiwan
2.
Department of Information Management, National Dong Hwa University, Hualien 974301, Taiwan
3.
International College, Department of Computer Science and Information Management, Providence University, Taichung 433303, Taiwan

Received: 13 March 2026 Revised: 07 September 2026 Accepted: 11 September 2026 Published: 21 September 2026
90B35, 90C11, 90C59

This paper investigates a strongly NP-hard two-machine scheduling problem where the objective is to minimize the makespan. The system consists of two machines, each assigned a dedicated set of jobs. Processing is subject to a common resource pool of a single-type resource. A key challenge lies in the dynamic resource requirement: each job must acquire a specific amount of the resource to commence its processing, and it releases a potentially unequal amount back to the pool upon completion. To model this complex resource flow and processing interdependence, we first develop a mixed-integer linear programming model. Recognizing the problem's strong NP-hardness, we embed an existing polynomial-time dynamic programming algorithm, which was designed for two given processing sequences a priori, within two newly designed search-based meta-heuristics. We conclude by presenting extensive computational tests that rigorously evaluate the performance characteristics of these algorithms.
- resource constraints,
- relocation project,
- parallel dedicated machines,
- NP-hardness,
- meta-heuristics
Citation: Huai-Che Hong, Elaine Yi-Ling Wu, Bertrand M.T. Lin. Makespan minimization on two parallel dedicated machines under resource constraints[J]. Journal of Industrial and Management Optimization, 2026, 22(10): 5227-5246. doi: 10.3934/jimo.2026180

Related Papers:

Abstract

This paper investigates a strongly NP-hard two-machine scheduling problem where the objective is to minimize the makespan. The system consists of two machines, each assigned a dedicated set of jobs. Processing is subject to a common resource pool of a single-type resource. A key challenge lies in the dynamic resource requirement: each job must acquire a specific amount of the resource to commence its processing, and it releases a potentially unequal amount back to the pool upon completion. To model this complex resource flow and processing interdependence, we first develop a mixed-integer linear programming model. Recognizing the problem's strong NP-hardness, we embed an existing polynomial-time dynamic programming algorithm, which was designed for two given processing sequences a priori, within two newly designed search-based meta-heuristics. We conclude by presenting extensive computational tests that rigorously evaluate the performance characteristics of these algorithms.

References

[1]	C. Artigues, S. Demassey, E. Néron, Resource-Constrained Project Scheduling: Models, Algorithms, Extensions and Applications, London: ISTE Ltd and John Wiley & Sons, 2008.
[2]	P. Brucker, A. Drexl, R. Möhring, K. Neumann, E. Pesch, Resource-constrained project scheduling: Notation, classification, models, and methods, Eur. J. Oper. Res. 112 (1999), 3–41. https://doi.org/10.1016/S0377-2217(98)00204-5
[3]	S. Hartmann, D. Briskorn, A survey of variants and extensions of the resource-constrained project scheduling problem, Eur. J. Oper. Res., 207 (2010), 1–14. https://doi.org/10.1016/j.ejor.2009.11.005 doi: 10.1016/j.ejor.2009.11.005
[4]	W. Herroelen, B. De Reyck, E. Demeulemeester, Resource-constrained project scheduling: A survey of recent developments, Comput. Oper. Res., 25 (1998), 279–302. https://doi.org/10.1016/S0305-0548(97)00055-5 doi: 10.1016/S0305-0548(97)00055-5
[5]	S. Issa, Y. Tu, A survey in the resource-constrained project and multi-project scheduling problems, J. Proj. Manag., 5 (2020), 117–138. https://doi.org/10.5267/j.jpm.2019.11.001 doi: 10.5267/j.jpm.2019.11.001
[6]	L. Özdamar, G. Ulusoy, A survey on the resource-constrained project scheduling problem, IIE Trans., 27 (1995), 574–586. https://doi.org/10.1080/07408179508936773 doi: 10.1080/07408179508936773
[7]	E. H. Kaplan, Relocation models for public housing redevelopment programs, Environ. Plan. B Plan. Des., 13 (1986), 5–19. https://doi.org/10.1177/239980838601300101 doi: 10.1177/239980838601300101
[8]	E. H. Kaplan, A. Amir, A fast feasibility test for relocation problems, Eur. J. Oper. Res., 35 (1988), 201–206. https://doi.org/10.1016/0377-2217(88)90030-6 doi: 10.1016/0377-2217(88)90030-6
[9]	R. L. Graham, E. L. Lawler, J. K. Lenstra, A. H. G. Rinnooy 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
[10]	B. M. T. Lin, F. J. Hwang, A. V. Kononov, Relocation scheduling subject to fixed processing sequences, J. Sched., 19 (2016), 153–163. https://doi.org/10.1007/s10951-015-0455-8 doi: 10.1007/s10951-015-0455-8
[11]	S. M. Johnson, Optimal two- and three-stage production schedules with setup times included, Nav. Res. Logist. Q., 1 (1954), 61–68. https://doi.org/10.1002/nav.3800010110 doi: 10.1002/nav.3800010110
[12]	E. H. Kaplan, O. Berman, OR hits the heights: Relocation planning at the Orient Heights housing project, Interfaces, 18 (1988), 14–22. https://doi.org/10.1287/inte.18.6.14 doi: 10.1287/inte.18.6.14
[13]	A. Amir, E. H. Kaplan, Relocation problems are hard, Int. J. Comput. Math., 25 (1988), 101–110. https://doi.org/10.1080/00207168808803664 doi: 10.1080/00207168808803664
[14]	A. V. Kononov, B. M. T. Lin, On relocation problems with multiple identical working crews, Discrete Optim., 3 (2006), 366–381. https://doi.org/10.1016/j.disopt.2006.06.003 doi: 10.1016/j.disopt.2006.06.003
[15]	B. M. T. Lin, S. S. Tseng, Some results of relocation problems with processing times and deadlines, Int. J. Comput. Math., 40 (1991), 1–15. https://doi.org/10.1080/00207169108803998 doi: 10.1080/00207169108803998
[16]	B. M. T. Lin, S. S. Tseng, On the relocation problems of maximizing new capacities under a common due-date, Int. J. Syst. Sci., 23 (1992), 1433–1448. https://doi.org/10.1080/00207729208949397 doi: 10.1080/00207729208949397
[17]	B. M. T. Lin, S. T. Liu, Maximizing total reward in the relocation problem subject to generalized due dates, Int. J. Prod. Econ., 115 (2008), 55–63. https://doi.org/10.1016/j.ijpe.2008.04.009 doi: 10.1016/j.ijpe.2008.04.009
[18]	N. G. Hall, Scheduling problems with generalized due dates, IIE Trans., 18 (1986), 220–222. https://doi.org/10.1080/07408178608975351 doi: 10.1080/07408178608975351
[19]	S. V. Sevastyanov, B. M. T. Lin, H. L. Huang, Time complexity analysis in the relocation problem with arbitrary release dates, Theor. Comput. Sci., 412 (2011), 4536–4544. https://doi.org/10.1016/j.tcs.2011.04.034 doi: 10.1016/j.tcs.2011.04.034
[20]	Y. C. Su, B. M. T. Lin, Minimizing the total weighted completion time in relocation scheduling, Comput. Ind. Eng., 173 (2022), 108662. https://doi.org/10.1016/j.cie.2022.108662 doi: 10.1016/j.cie.2022.108662
[21]	T. C. E. Cheng, B. M. T. Lin, H. L. Huang, Resource-constrained flowshop scheduling with separate resource recycling operations, Comput. Oper. Res., 39 (2012), 1206–1212. https://doi.org/10.1016/j.cor.2010.07.015 doi: 10.1016/j.cor.2010.07.015
[22]	T. C. Lo, B. M. T. Lin, Relocation scheduling in a two-machine flow shop with resource recycling operations, Mathematics, 9 (2021), 1527. https://doi.org/10.3390/math9131527 doi: 10.3390/math9131527
[23]	M. R. Garey, D. S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, San Francisco: Freeman, 1979.
[24]	S. Kirkpatrick, C. D. Gelatt, M. P. Vecchi, Optimization by simulated annealing, Science, 220 (1983), 671–680. https://doi.org/10.1126/science.220.4598.671 doi: 10.1126/science.220.4598.671
[25]	F. Glover, Future paths for integer programming and links to artificial intelligence, Comput. Oper. Res., 13 (1986), 533–549. https://doi.org/10.1016/0305-0548(86)90048-1 doi: 10.1016/0305-0548(86)90048-1
[26]	F. Glover, Tabu search—Part Ⅱ, ORSA J. Comput., 2 (1990), 4–32. https://doi.org/10.1287/ijoc.2.1.4
[27]	F. Glover, Tabu search—Part Ⅰ, ORSA J. Comput., 1 (1989), 190–206. https://doi.org/10.1287/ijoc.1.3.190
[28]	F. Dammeyer, S. Voß, Dynamic tabu list management using the reverse elimination method, Ann. Oper. Res., 41 (1993), 29–46. https://doi.org/10.1007/BF02022561 doi: 10.1007/BF02022561

Reader Comments

Your name:*

Email:*
© 2026 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)