A Monte Carlo simulation approach to the gap-time relationship in solving scheduling problem

Abstract

This article presents a study on the job shop problem, a combinatorial optimization problem that models scheduling and resource allocation in industrial settings. The article aims to investigate the relationship between optimality gap and required computational resources, considering various optimality gap levels that are applicable in real-life situations. The study uses a Monte Carlo simulation to analyze the behavior of solvers in solving different sizes of random-generated scheduling problems. The findings of the study offer insights into the worthiness of reaching an optimal solution versus implementing a near-optimal solution and starting the work. The codes used in the study are accessible on the author's GitHub account.

Keywords

• Integer Programming
• Scheduling Problem
• Random Generation
• Solving Time Approximation
• Combinatorial Optimization

References

1. Ahmadinejad, M., Taheri, N., & Moaiyeri, M. H. (2020). Energy-efficient magnetic approximate full adder with spin-Hall assistance for signal processing applications. Analog Integrated Circuits and Signal Processing, 102, 645-657. http://doi.org/10.1007/s10470-020-01630-z
2. Baker, K. R., & Keller, B. (2010). Solving the single-machine sequencing problem using integer programming. Computers & Industrial Engineering, 59(4), 730-735. http://doi.org/10.1016/j.cie.2010.07.028
3. Belotti, P., Kirches, C., Leyffer, S., Linderoth, J., Luedtke, J., & Mahajan, A. (2013). Mixed-integer nonlinear optimization. Acta Numerica, 22, 1-131. http://doi.org/10.1017/S0962492913000032
4. Bynum, M. L., Hackebeil, G. A., Hart, W. E., Laird, C. D., Nicholson, B. L., Siirola, J. D., ... & Woodruff, D. L. (2021). Pyomo-optimization modeling in python (Vol. 67). Berlin/Heidelberg, Germany: Springer. http://doi.org/10.1007/978-3-030-68928-5
5. Chankong, V., & Haimes, Y. Y. (2008). Multiobjective decision making: theory and methodology. Courier Dover Publications. ISBN 9780486462899
6. Chen, J. S. (2006). Using integer programming to solve the machine scheduling problem with a flexible maintenance activity. Journal of Statistics and Management Systems, 9(1), 87-104. http://doi.org/10.1080/09720510.2006.10701195
7. Engin, O., & İşler, M. (2022). An efficient parallel greedy algorithm for fuzzy hybrid flow shop scheduling with setup time and lot size: a case study in apparel process. Journal of fuzzy extension and applications, 3(3), 249-262. https://doi.org/10.22105/jfea.2021.314312.1169
8. Fatehi, N., Politis, A., Lin, L., Stobby, M., & Nazari, M. H. (2023, January). Machine Learning based Occupant Behavior Prediction in Smart Building to Improve Energy Efficiency. In 2023 IEEE Power & Energy Society Innovative Smart Grid Technologies Conference (ISGT) (pp. 1-5). IEEE. http://doi.org/10.1109/ISGT51731.2023.10066411

9. Fischetti, M., & Monaci, M. (2020). A branch-and-cut algorithm for mixed-integer bilinear programming. European Journal of Operational Research, 282(2), 506-514. http://doi.org/10.1016/j.ejor.2019.09.043 Fowler, J. W., & Mönch, L. (2022). A survey of scheduling with parallel batch (p-batch) processing. European journal of operational research, 298(1), 1-24. http://doi.org/10.1016/j.ejor.2021.06.012
10. Garey, M. R., Johnson, D. S., & Sethi, R. (1976). The complexity of flowshop and jobshop scheduling. Mathematics of operations research, 1(2), 117-129. http://doi.org/10.1287/moor.1.2.117 Garey, M. R., & Johnson, D. S. (1979). Computers and intractability (Vol. 174). San Francisco: freeman. ISBN: 9780716710448 Gharbi, A., Mrad, M., Chalghoumi, S., & Ladhari, T., (2019). Enhanced lower bounds and exact procedures for total completion time minimization in a two‐machine permutation flowshop with release dates. International Transactions in Operational Research, 26(6), 2432-2449. https://doi.org/10.1111/itor.12421
11. Gharibi, K., & Abdollahzadeh, S. (2021). A mixed-integer linear programming approach for circular economy-led closed-loop supply chains in green reverse logistics network design under uncertainty. Journal of Enterprise Information Management, (ahead-of-print). http://doi.org/10.1108/JEIM-11-2020-0472
12. Grigoriev, A., Sviridenko, M., & Uetz, M. (2007). Machine scheduling with resource-dependent processing times. Mathematical programming, 110, 209-228. http://doi.org/10.1007/s10107-006-0059-3
13. Gurobi Optimization, LLC. (2023). Gurobi Optimizer Reference Manual. Retrieved from https://www.gurobi.com/wp-content/plugins/hd_documentations/documentation/10.0/refman.pdf
14. Héctor, G., Nucamendi-Guillén, S., & Avalos-Rosales, O. (2022). A mixed integer formulation and an efficient metaheuristic for the unrelated parallel machine scheduling problem: total tardiness minimization. EURO Journal on Computational Optimization, 10, 100034. https://doi.org/10.1016/j.ejco.2022.100034
15. Kazemzadeh, F., Safaei, A. A., Mirzarezaee, M., Afsharian, S., & Kosarirad, H. (2023). Determination of influential nodes based on the communities’ structure to maximize influence in social networks. Neurocomputing, 534, 18-28. http://doi.org/10.1016/j.neucom.2023.02.059
16. Kis, T. (2002). On the complexity of non-preemptive shop scheduling with two jobs. Computing, 69, 37-49. http://doi.org/10.1007/s00607-002-1455-z
17. Liu, Q., Kosarirad, H., Meisami, S., Alnowibet, K. A., & Hoshyar, A. N. (2023). An Optimal Scheduling Method in IoT-Fog-Cloud Network Using Combination of Aquila Optimizer and African Vultures Optimization. Processes, 11(4), 1162. http://doi.org/10.3390/pr11041162
18. Linderoth, J., & Wright, S. J. (2005). Computational grids for stochastic programming. In Applications of stochastic programming (pp. 61-77). Society for Industrial and Applied Mathematics. http://doi.org/10.1137/1.9780898718799.ch5
19. Mohabbati-Kalejahi, N., & Yoon, S. W. (2015). Parallel machines scheduling problem for minimization of maximum lateness with sequence-dependent setup times. In IIE Annual Conference. Proceedings (p. 837). Institute of Industrial and Systems Engineers (IISE). Retrieved from https://www.proquest.com/scholarly-journals/parallel-machines-scheduling-problem-minimization/docview/1791989138/se-2
20. Mokhtari, A., Bagheri, H., Ghazvini, M., & Ghader, S. (2022). New mathematical modeling of temperature-based properties of ionic liquids mixture: Comparison between semi-empirical equation and equation of state. Chemical Engineering Research and Design, 177, 331-353. http://doi.org/10.1016/j.cherd.2021.10.039
21. Mooney, C. Z. (1997). Monte carlo simulation (No. 116). Sage. http://doi.org/10.4135/9781412985116
22. Pferschy, U., & Staněk, R. (2017). Generating subtour elimination constraints for the TSP from pure integer solutions. Central European journal of operations research, 25, 231-260. http://doi.org/10.1007/s10100-016-0437-8
23. Pourghorban, A., Dorothy, M., Shishika, D., Von Moll, A., & Maity, D. (2022, December). Target Defense against Sequentially Arriving Intruders. In 2022 IEEE 61st Conference on Decision and Control (CDC) (pp. 6594-6601). http://doi.org/10.1109/CDC51059.2022.9992425
24. Qiao, L., Zhang, Z., & Huang, Z. (2021). A scheduling algorithm for multi-workshop production based on BOM and process route. Applied Sciences, 11(11), 5078. http://doi.org/10.3390/app11115078
25. Sattarkhan, M. H. (2023). Production Scheduling of Parallel Identical Lines in a Multi-Product Manufacturing System with Genetic Algorithm. International Journal of Research in Industrial Engineering, 12(1), 7-20.
26. Shahparvari, S., Hassanizadeh, B., Mohammadi, A., Kiani, B., Lau, K. H., Chhetri, P., & Abbasi, B. (2022). A decision support system for prioritised COVID-19 two-dosage vaccination allocation and distribution. Transportation Research Part E: Logistics and Transportation Review, 159, 102598. http://doi.org/10.1016/j.tre.2021.102598
27. Shirneshan, H., Sadegheih, A., Hosseini-Nasab, H., & Lotfi, M. M. (2022). A two-stage stochastic programming approach for care providers shift scheduling problems. Journal of Applied Research on Industrial Engineering. https://doi.org/10.22105/jarie.2022.349970.1488
28. Soleimani, M., Mahmudi, F., & Naderi, M. H. (2023). Some results on the maximal graph of commutative rings. Advanced Studies: Euro-Tbilisi Mathematical Journal, 16(supp1), 21-26. http://doi.org/10.32513/asetmj/1932200823104
29. Taha, H. A. (2013). Operations Research: An Introduction. Pearson Education. ISBN 9789332518223 Taillard, E. (1993). Benchmarks for basic scheduling problems. European journal of operational research, 64(2), 278-285. http://doi.org/10.1016/0377-2217(93)90182-M
30. Toragay, O., & Silva, D. F. (2021). Fast heuristic approach for control of complex authentication systems. Applied Stochastic Models in Business and Industry, 37(4), 744-766. http://doi.org/10.1002/asmb.2619
31. Vaisi, B., Farughi, H., Raissi, S., & Sadeghi, H. (2023). A bi-objective optimal task scheduling model for two-machine robotic-cell subject to probable machine failures. Journal of applied research on industrial engineering, 10(1), 141-154. https://doi.org/10.22105/jarie.2022.336768.1465
32. Waller, L. (1973). A Branch-bound-and-imply Algorithm for an Improved Attack Upon the Job-shop Scheduling Problem. Computing Laboratory Technical Report Series. Retrieved from https://eprints.ncl.ac.uk/file_store/production/160014/DC7B64C6-C876-4D3D-8DAC-270375AEFADE.pdf
33. Winston, W. L. (2022). Operations research: applications and algorithms. Cengage Learning. ISBN: 9780357907818
34. Yavary, A., & Sajedi, H. (2018, June). Solving dynamic vehicle routing problem with pickup and delivery by CLARITY method. In 2018 IEEE 22nd International Conference on Intelligent Engineering Systems (INES) (pp. 000207-000212). IEEE. http://doi.org/10.1109/INES.2018.8523908
35. Zhou, T., El-Wahed Khalifa, H. A., Najafi, S. E., & Edalatpanah, S. A. (2022). Minimizing the Machine Processing Time in a Flow Shop Scheduling Problem under Piecewise Quadratic Fuzzy Numbers. Discrete Dynamics in Nature and Society. http://doi.org/10.1155/2022/3990534