Total Tardiness Minimization in a Single-Machine with Periodical Resource Constraints
Main Article Content
Keywords
Production Sequencing, Combinatorial Optimization, Matheuristics, Resource Consumption
Abstract
In this paper we introduce a variant of the single machine considering resource restriction per period. The objective function to be minimized is the total tardiness. We proposed an integer linear programming modeling based on a bin packing formulation. In view of the NP-hardness of the introduced variant, heuristic algorithms are required to find high-quality solutions within an admissible computation times. In this sense, we present a new hybrid matheuristic called Relax-and-Fix with Variable Fixing Search (RFVFS). This innovative solution approach combines the relax-and-fix algorithm and a strategy for the fixation of decision variables based on the concept of the variable neighborhood search metaheuristic. As statistical indicators to evaluate the solution procedures under comparison, we employ the Average Relative Deviation Index (ARDI) and the Success Rate (SR). We performed extensive computational experimentation with a testbed composed by 450 proposed test problems. Considering the results for the number of jobs, the RFVFS returned ARDI and SR values of 35.6% and 41.3%, respectively. Our proposal outperformed the best solution approach available for a closely-related problem with statistical significance.
Downloads
References
[2] M. Afzalirad and M. Shafipour, “Design of an efficient genetic algorithm for a resource-constrained unrelated parallel machine scheduling problem with machine eligibility restrictions,” Journal of Intelligent Manufacturing, vol. 29, no. 2, pp. 423–437, 2018. https://doi.org/10.1007/s10845-015-1117-6.
[3] M. Akbar and T. Irohara, “Scheduling for sustainable manufacturing: A review,” Journal of cleaner production, vol. 205, pp. 866–883, 2018. https://doi.org/10.1016/j.jclepro.2018.09.100.
[4] M. P. Antonioli, C. D. Rodrigues, and B. A. Prata, “Minimizing total tardiness for the order scheduling problem with sequence-dependent setup times using hybrid metaheuristics,” International Journal of Industrial Engineering Computations, vol. 13, 2022. https://doi.org/10.5267/j.ijiec.2021.11.002.
[5] F. Della Croce and F. Salassa, “A variable neighborhood search based metaheuristic for nurse rostering problems,” Annals of Operations Re-search, vol. 218, no. 1, pp. 185–199, 2014. https://doi.org/10.1007/s10479-012-1235-x.
[6] F. Della Croce, V. Narayan, and R. Tadei, “The two-machine total completion time flow shop problem,” European Journal of Operational Research, vol. 90, no. 2, pp. 227–237, 1996.
https://doi.org/10.1016/0377-2217(95)00351-7.
[7] F. Della Croce, F. Salassa, and V. T’kindt, “A hybrid heuristic approach for single machine scheduling with release times,” Computers & Operations Research, vol. 45, pp. 7–11, 2014. https://doi.org/10.1016/j.cor.2013.11.016.
[8] E. B. Edis and I. Ozkarahan, “Solution approaches for a real-life resource-constrained parallel machine scheduling problem,” The International Journal of Advanced Manufacturing Technology, vol. 58, no. 9, pp. 1141–1153, 2012. https://doi.org/10.1007/s00170-011-3454-8.
[9] E. B. Edis, C. Oguz, and I. Ozkarahan, “Parallel machine scheduling with additional resources: Notation, classification, models and solution methods,” European Journal of Operational Research, vol. 230, no. 3, pp. 449 – 463, 2013. https://doi.org/10.1016/j.ejor.2013.02.042.
[10] L. Fanjul-Peyro, F. Perea, and R. Ruiz, “Models and metaheuristics for the unrelated parallel machine scheduling problem with additional resources,” European Journal of Operational Research, vol. 260, no. 2, pp. 482 – 493, 2017. https://doi.org/10.1016/j.ejor.2017.01.002.
[11] V. Fernandez-Viagas and J. M. Framinan, “Neh-based heuristics for the permutation flow shop scheduling problem to minimize total tardiness,” Computers & Operations Research, vol. 60, pp. 27–36, 2015. https://doi.org/10.1016/j.cor.2015.02.002.
[12] J. M. Framinan and P. Perez-Gonzalez, “Order scheduling with tardiness objective: Improved approximate solutions,” European Journal of Operational Research, vol. 266, no. 3, pp. 840–850, 2018. https://doi.org/10.1016/j.ejor.2017.10.064.
[13] O. Herr and A. Goel, “Minimising total tardiness for a single machine scheduling problem with family setups and resource constraints,” European Journal of Operational Research, vol. 248, no. 1, pp. 123–135, 2016. https://doi.org/10.1016/j.ejor.2015.07.001.
[14] M. Ji, J.-Y. Wang, and W.-C. Lee, “Minimizing resource consumption on uniform parallel machines with a bound on makespan,” Computers & Operations Research, vol. 40, no. 12, pp. 2970 – 2974, 2013. https://doi.org/10.1016/j.cor.2013.06.011.
[15] S. Karhi and D. Shabtay, “Single machine scheduling to minimise resource consumption cost with a bound on scheduling plus due date assignment penalties,” International Journal of Production Research, vol. 56, no. 9, pp. 3080–3096, 2018. https://doi.org/10.1080/00207543.2017.1400708.
[16] A. B. Keha, K. Khowala, and J. W. Fowler, “Mixed integer programming formulations for single machine scheduling problems,” Computers & Industrial Engineering, vol. 56, no. 1, pp. 357–367, 2009. https://doi.org/10.1016/j.cie.2008.06.008.
[17] Y. Kochetov and A. Kondakov, “Vns metaheuristic for a bin packing problem with a color constraint,” Electronic Notes in Discrete Mathematics, vol. 58, pp. 39–46, 2017. https://doi.org/10.1016/j.endm.2017.03.006.
[18] S.-W. Lin and K.-C. Ying, “Optimization of makespan for no-wait flowshop scheduling problems using efficient matheuristics,” Omega, vol. 64, pp. 115–125, 2016. https://doi.org/10.1016/j.omega.2015.12.002.
[19] M. Lubin and I. Dunning, “Computing in operations research using julia,” INFORMS Journal on Computing, vol. 27, no. 2, pp. 238–248, 2015. https://doi.org/10.1287/ijoc.2014.0623.
[20] S. Martello, “Knapsack problems: algorithms and computer implementations,” Wiley-Interscience series in discrete mathematics and optimization, 1990.
[21] N. Mladenovic and P. Hansen, “Variable neighborhood search,” Computers & operations research, vol. 24, no. 11, pp. 1097–1100, 1997. https://doi.org/10.1016/S0305-0548(97)00031-2.
[22] J. C. Pinheiro and J. E. C. Arroyo, “Effective IG heuristics for a single-machine scheduling problem with family setups and resource constraints,” Annals of Mathematics and Artificial Intelligence, vol. 88, no. 1-3, pp. 169–185, 2020. https://doi.org/10.1007/s10472-019-09646-6.
[23] A. R. Pitombeira-Neto and B. d. A. Prata, “A matheuristic algorithm for the one-dimensional cutting stock and scheduling problem with heterogeneous orders,” TOP, Sep 2019. https://doi.org/10.1007/s11750-019-00531-3.
[24] B. A. Prata, A. R. Pitombeira-Neto, and C. J. M. Sales, “An integer linear programming model for the multiperiod production planning of precast concrete beams,” Journal of Construction Engineering and Management, vol. 141, no. 10, p. 04015029, 2015. https://doi.org/10.1061/(ASCE)CO.1943-7862.0000991.
[25] B. A. Prata, L. R. de Abreu, and J. Y. F. Lima, “Heuristic methods for the single-machine scheduling problem with periodical resource constraints,” TOP, pp. 1–23, 2020. https://doi.org/10.1007/s11750-020-00574-x.
[26] B. A. Prata, C. D. Rodrigues, and J. M. Framinan, “Customer order scheduling problem to minimize makespan with sequence-dependent setup times,” Computers & Industrial Engineering, vol. 151, p. 106962, 2021. https://doi.org/10.1016/j.cie.2020.106962.
[27] E. Rahimian, K. Akartunalı, and J. Levine, “A hybrid integer programming and variable neighbourhood search algorithm to solve nurse rostering problems,” European Journal of Operational Research, vol. 258, no. 2, pp. 411–423, 2017. https://doi.org/10.1016/j.ejor.2016.09.030.
[28] G. Scheithauer, Introduction to Cutting and Packing Optimization: Problems, Modeling Approaches, Solution Methods. Springer, 2017, vol. 263. https://doi.org/10.1007/978-3-319-64403-5_1.
[29] D. Shabtay, “Single-machine scheduling with machine unavailability periods and resource dependent processing times,” European Journal of Operational Research, 2021. https://doi.org/10.1016/j.ejor.2021.03.034.
[30] J. P. Sousa and L. A. Wolsey, “A time-indexed formulation of non-preemptive single machine scheduling problems,” Mathematical programming, vol. 54, no. 1-3, pp. 353–367, 1992. https://doi.org/10.1007/BF01586059.
[31] J. A. Ventura and D. Kim, “Parallel machine scheduling with earliness–tardiness penalties and additional resource constraints,” Computers & Operations Research, vol. 30, no. 13, pp. 1945 – 1958, 2003. https://doi.org/10.1016/S0305-0548(02)00118-1.
[32] F. Villa, E. Vallada, and L. Fanjul-Peyro, “Heuristic algorithms for the unrelated parallel machine scheduling problem with one scarce additional resource,” Expert Systems with Applications, vol. 93, pp. 28 – 38, 2018. https://doi.org/10.1016/j.eswa.2017.09.054.
[33] J.-B. Wang and M.-Z. Wang, “Single-machine scheduling to minimize total convex resource consumption with a constraint on total weighted flow time,” Computers & Operations Research, vol. 39, no. 3, pp. 492 – 497, 2012. https://doi.org/10.1016/j.cor.2011.05.026.
[34] X.-R. Wang and J.-J. Wang, “Single-machine scheduling with convex resource-dependent processing times and deteriorating jobs,” Applied Mathematical Modelling, vol. 37, no. 4, pp. 2388 – 2393, 2013. https://doi.org/10.1016/j.apm.2012.05.025.
[35] L. Wu and C.-D. Cheng, “On single machine scheduling with resource constraint,” Journal of Combinatorial Optimization, vol. 31, no. 2, pp. 491–505, 2016. https://doi.org/10.1007/s10878-014-9721-5.
[36] W.-C. Yeh, M.-C. Chuang, and W.-C. Lee, “Uniform parallel machine scheduling with resource consumption constraint,” Applied Mathematical Modelling, vol. 39, no. 8, pp. 2131 – 2138, 2015. https://doi.org/10.1016/j.apm.2014.10.012.
[37] Z. Zhu, F. Chu, L. Sun, and M. Liu, “Single machine scheduling with resource allocation and learning effect considering the rate-modifying activity,” Applied Mathematical Modelling, vol. 37, no. 7, pp. 5371 – 5380, 2013. https://doi.org/10.1016/j.apm.2012.09.072.
Article Sidebar
Article Details
This work is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License.
Authors' Retention of Copyright
Authors retain the copyright of their original work published in Jurnal Optimasi Sistem Industri (JOSI). By submitting their manuscript to the journal, authors grant Jurnal Optimasi Sistem Industri (JOSI) a non-exclusive license to publish the work under the CC BY-NC-SA 4.0 International License. This means that others are permitted to:
- Share and adapt the work for non-commercial purposes, provided proper attribution is given to the original authors and source.
- Create derivative works based on the original article, as long as the new work is non-commercial and under the same CC BY-NC-SA 4.0 International License.
Non-Commercial Usage
The CC BY-NC-SA 4.0 International License restricts commercial use of the published work and its derivatives. Commercial use includes generating revenue, financial gain, or any form of commercial exploitation. This limitation aims to preserve the scholarly and educational nature of the content.
ShareAlike Requirement
If you remix, adapt, or build upon the work, you must distribute your contributions under the same CC BY-NC-SA 4.0 International License as the original work. This "ShareAlike" requirement ensures that any new works based on the original content adhere to the same non-commercial, share-alike principles.
Usage, Attribution, and Citations
Authors and readers are allowed to:
- Share and distribute the published article in any medium or format.
- Adapt, remix, transform, and build upon the article for non-commercial purposes.
- Provide appropriate attribution to the original authors and the journal.
When using content from Jurnal Optimasi Sistem Industri (JOSI), proper attribution must be provided through citation of the original source and authors.
Copyright Infringement and Ethical Considerations
If you believe that any material published in Jurnal Optimasi Sistem Industri (JOSI) infringes upon your copyright or the copyright of someone you represent, please contact the editorial team promptly. The journal is committed to addressing copyright concerns in accordance with established ethical guidelines set forth by the Committee on Publication Ethics (COPE).
For any questions or inquiries related to copyright and licensing, please contact the editorial team at editor_josi[at]eng.unand.ac.id.
