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

Year 2023, Volume: 7 Issue: 1, 1579 - 1590, 30.06.2023

Oğuz Torağay , Shaheen Pouya

https://doi.org/10.56554/jtom.1286288

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

• 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
• 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
• 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
• 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
• Chankong, V., & Haimes, Y. Y. (2008). Multiobjective decision making: theory and methodology. Courier Dover Publications. ISBN 9780486462899
• 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
• 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
• 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
• 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
• 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
• 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
• 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
• Gurobi Optimization, LLC. (2023). Gurobi Optimizer Reference Manual. Retrieved from https://www.gurobi.com/wp-content/plugins/hd_documentations/documentation/10.0/refman.pdf
• 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
• 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
• 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
• 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
• 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
• 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
• 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
• Mooney, C. Z. (1997). Monte carlo simulation (No. 116). Sage. http://doi.org/10.4135/9781412985116
• 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
• 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
• 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
• 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.
• 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
• 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
• 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
• 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
• 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
• 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
• 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
• Winston, W. L. (2022). Operations research: applications and algorithms. Cengage Learning. ISBN: 9780357907818
• 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
• 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