Abstract
In the last years, researchers have been paying special attention to scheduling problems with scarce resource consumption and periodic maintenance activities with a view to the adoption of more realistic assumptions. This paper aims at presenting heuristics to a single-machine scheduling environment with periodical resource constraints. In this new variant of the single-machine scheduling problem, in each production period, there are resource consumption constraints. To the best of our knowledge, the proposed variant has not been addressed in the revised literature. An integer linear programming model is presented based on a bin packing formulation taking two packing constraints into consideration. The objective function adopted is makespan minimization, and relative deviation is used as a performance criterion. Since the problem under study is NP-hard, heuristic algorithms are proposed to obtain high-quality solutions in acceptable computational times. Eighteen constructive heuristics, two local search heuristics, and a hybrid matheuristics, based on the size reduction and simulated annealing algorithms, have been presented. The extensive computational experience carried out shows that the proposed local search algorithms, as well as the proposed matheuristics, are promising tools to solve large-sized instances.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Afzalirad M, Rezaeian J (2016) Resource-constrained unrelated parallel machine scheduling problem with sequence dependent setup times, precedence constraints and machine eligibility restrictions. Comput Ind Eng 98:40–52. https://doi.org/10.1016/j.cie.2016.05.020
Afzalirad M, Shafipour M (2018) Design of an efficient genetic algorithm for resource-constrained unrelated parallel machine scheduling problem with machine eligibility restrictions. J Intell Manuf 29(2):423–437. https://doi.org/10.1007/s10845-015-1117-6
Ángel Bello F, Álvarez A, Pacheco J, Martínez I (2011) A heuristic approach for a scheduling problem with periodic maintenance and sequence-dependent setup times. Comput Math Appl 61(4):797–808. https://doi.org/10.1016/j.camwa.2010.12.028
Birgin EG, Ronconi DP (2012) Heuristic methods for the single machine scheduling problem with different ready times and a common due date. Eng Optim 44(10):1197–1208. https://doi.org/10.1080/0305215X.2011.634409
Edis EB, Ozkarahan I (2012) Solution approaches for a real-life resource-constrained parallel machine scheduling problem. Int J Adv Manuf Technol 58(9):1141–1153. https://doi.org/10.1007/s00170-011-3454-8
Fanjul-Peyro L, Ruiz R (2011) Size-reduction heuristics for the unrelated parallel machines scheduling problem. Comput Oper Res 38(1):301–309. https://doi.org/10.1016/j.cor.2010.05.005
Fanjul-Peyro L, Perea F, Ruiz R (2017) Models and matheuristics for the unrelated parallel machine scheduling problem with additional resources. Eur J Oper Res 260(2):482–493. https://doi.org/10.1016/j.ejor.2017.01.002
Framinan JM, Leisten R, Ruiz R (2014) Manufacturing scheduling systems. Springer, Berlin
Hsu CJ, Low C, Su CT (2010) A single-machine scheduling problem with maintenance activities to minimize makespan. Appl Math Comput 215(11):3929–3935. https://doi.org/10.1016/j.amc.2009.11.040
Ji M, He Y, Cheng T (2007) Single-machine scheduling with periodic maintenance to minimize makespan. Comput Oper Res 34(6):1764–1770. https://doi.org/10.1016/j.cor.2005.05.034 (part Special Issue: Odysseus 2003 Second International Workshop on Freight Transportation Logistics)
Ji M, Wang JY, Lee WC (2013) Minimizing resource consumption on uniform parallel machines with a bound on makespan. Comput Oper Res 40(12):2970–2974. https://doi.org/10.1016/j.cor.2013.06.011
Karhi S, Shabtay D (2018) Single machine scheduling to minimise resource consumption cost with a bound on scheduling plus due date assignment penalties. Int J Prod Res 56(9):3080–3096. https://doi.org/10.1080/00207543.2017.1400708
Kirkpatrick S (1984) Optimization by simulated annealing: quantitative studies. J Stat Phys 34(5–6):975–986
Low C, Hsu CJ, Su CT (2010a) A modified particle swarm optimization algorithm for a single-machine scheduling problem with periodic maintenance. Expert Syst Appl 37(9):6429–6434. https://doi.org/10.1016/j.eswa.2010.02.075
Low C, Ji M, Hsu CJ, Su CT (2010b) Minimizing the makespan in a single machine scheduling problems with flexible and periodic maintenance. Appl Math Model 34(2):334–342. https://doi.org/10.1016/j.apm.2009.04.014
Martello S (1990) Knapsack problems: algorithms and computer implementations. Wiley-Interscience series in discrete mathematics and optimization
Montgomery DC (2017) Design and analysis of experiments. Wiley, New York
Pacheco J, Ángel-Bello F, Álvarez A (2013) A multi-start tabu search method for a single-machine scheduling problem with periodic maintenance and sequence-dependent set-up times. J Sched 16(6):661–673. https://doi.org/10.1007/s10951-012-0280-2
Perez-Gonzalez P, Framinan JM (2018) Single machine scheduling with periodic machine availability. Comput Ind Eng 123:180–188. https://doi.org/10.1016/j.cie.2018.06.025
Pitombeira-Neto AR, Prata BdA (2019) A matheuristic algorithm for the one-dimensional cutting stock and scheduling problem with heterogeneous orders. TOP. https://doi.org/10.1007/s11750-019-00531-3
Prata BA, Pitombeira-Neto AR, Sales CJM (2015) An integer linear programming model for the multiperiod production planning of precast concrete beams. J Constr Eng Manag 141(10):04015029. https://doi.org/10.1061/(ASCE)CO.1943-7862.0000991
Scheithauer G (2017) Introduction to cutting and packing optimization: problems, modeling approaches, solution methods, vol 263. Springer, Berlin
Valente JM (2007) Heuristics for the single machine scheduling problem with early and quadratic tardy penalties. Eur J Ind Eng 1(4):431–448
Ventura JA, Kim D (2003) Parallel machine scheduling with earliness-tardiness penalties and additional resource constraints. Comput Oper Res 30(13):1945–1958. https://doi.org/10.1016/S0305-0548(02)00118-1
Villa F, Vallada E, Fanjul-Peyro L (2018) Heuristic algorithms for the unrelated parallel machine scheduling problem with one scarce additional resource. Expert Syst Appl 93:28–38. https://doi.org/10.1016/j.eswa.2017.09.054
Wang JB, Wang MZ (2012) Single-machine scheduling to minimize total convex resource consumption with a constraint on total weighted flow time. Comput Oper Res 39(3):492–497. https://doi.org/10.1016/j.cor.2011.05.026
Wang XR, Wang JJ (2013) Single-machine scheduling with convex resource dependent processing times and deteriorating jobs. Appl Math Model 37(4):2388–2393. https://doi.org/10.1016/j.apm.2012.05.025
Wu L, Cheng CD (2016) On single machine scheduling with resource constraint. J Combin Optim 31(2):491–505. https://doi.org/10.1007/s10878-014-9721-5
Yeh WC, Chuang MC, Lee WC (2015) Uniform parallel machine scheduling with resource consumption constraint. Appl Math Model 39(8):2131–2138. https://doi.org/10.1016/j.apm.2014.10.012
Yu X, Zhang Y, Steiner G (2014) Single-machine scheduling with periodic maintenance to minimize makespan revisited. J Sched 17(3):263–270. https://doi.org/10.1007/s10951-013-0350-0
Zheng XL, Wang L (2016) A two-stage adaptive fruit fly optimization algorithm for unrelated parallel machine scheduling problem with additional resource constraints. Expert Syst Appl 65:28–39. https://doi.org/10.1016/j.eswa.2016.08.039
Zheng XL, Wang L (2018) A collaborative multiobjective fruit fly optimization algorithm for the resource constrained unrelated parallel machine green scheduling problem. IEEE Trans Syst Man Cybern Syst 48(5):790–800. https://doi.org/10.1109/TSMC.2016.2616347
Zhu Z, Chu F, Sun L, Liu M (2013) Single machine scheduling with resource allocation and learning effect considering the rate-modifying activity. Appl Math Model 37(7):5371–5380. https://doi.org/10.1016/j.apm.2012.09.072
Acknowledgements
This study was financed in part by the Coordination for the Improvement of Higher Education Personnel (CAPES)- Finance Code 001. This work was partially funded by National Council for Scientific and Technological Development (CNPq) through grants 404232/2016-7 and 303594/2018-7.
Author information
Authors and Affiliations
Corresponding author
Additional information
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
Rights and permissions
About this article
Cite this article
Prata, B.A., de Abreu, L.R. & Lima, J.Y.F. Heuristic methods for the single-machine scheduling problem with periodical resource constraints. TOP 29, 524–546 (2021). https://doi.org/10.1007/s11750-020-00574-x
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s11750-020-00574-x