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

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,

PDF

___

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