A Comparative Framework for Job Shop Scheduling Between Exact Method and Genetic Algorithm
Main Article Content
Abstract
In modern industries optimizing production processes time consumption has become very important for enhancing competitiveness and reducing operation costs. This research explores two case studies of the job shop scheduling problem (JSSP) through a comparative study applied to real-world data from the Iraqi hydraulic industry to find the optimal makespan time by using two approaches: an exact method Via linear programming LP for a small-scale problem in the first case study and constraint programming (CP-SAT) applied to the larger problem to overcome the computational limitations of LP. Artificial intelligence (AI) techniques model as genetics algorithm (GA) applied to both case studies for comparison. A model is solved using Python to minimize makespan time. The results show a significant effect of job size on model efficiency. In the first case study has 5 jobs done on five machines; the optimal Exact LP Method makespan time is 234 minutes, and (GA) shows the same result. In the second case study, the 8*8 Exact CP model optimal makespan is 209, and (GA) optimal makespan time in the second case study is 212 minutes. This research achieved a 33.1% time reduction compared to the company's traditional scheduling, providing valuable insights into the strengths and limitations of each approach, offering guidance for industries seeking to optimize production processes and reduce work time.
Downloads
Article Details
Section
How to Cite
References
Abdullah, W.N., 2022. Solving job‐shop scheduling problem using genetic algorithm approach. Journal of the College of Basic Education, 17(70), pp. 241–253. https://doi.org/10.35950/cbej.vi.8491.
Al‐Ashhab, M.S. and Fadag, H., 2018. Multi‐product master production scheduling optimization modelling using mixed integer linear programming and genetic algorithms. International Journal of Research–Granthaalayah,6(5), pp. 78–92. https://doi.org/10.29121/granthaalayah.v6.i5.2018.1429.
Birgin, E.G., Feofiloff, P., Fernandes, C.G., de Melo, E.L., Oshiro, M.T.I. and Ronconi, D.P., 2014. A MILP model for an extended version of the flexible job shop scheduling problem. Optimization Letters, 8(4), pp. 1417–1431. https://doi.org/10.1007/s11590-013-0669-7.
Blum, C. and Roli, A., 2003. Metaheuristics in combinatorial optimization: Overview and conceptual comparison. ACM Computing Surveys, 35(3), pp. 268–308. https://www.ac.tuwien.ac.at/files/pub/blum-11.
Burke, E.K., Hyde, M.R., Kendall, G., Ochoa, G., Özcan, E. and Woodward, J.R., 2013. Hyperheuristics: A survey of the state of the art. Journal of the Operational Research Society, 64(12), pp. 1695–1724. https://doi.org/10.1057/jors.2013.71.
Buske, J. and Jendle, T., 2024. Integer Linear Programming Applied to Production Planning. Master’s thesis, Chalmers University of Technology. http://hdl.handle.net/20.500.12380/308396.
Chang, X., Jia, X. and Ren, J., 2025. A reinforcement learning enhanced memetic algorithm for multi-objective flexible job shop scheduling toward Industry 5.0. International Journal of Production Research, 63(1), pp. 119–147. https://doi.org/10.1080/00207543.2024.2357740
Christoforidis, S., Titopoulos, E., Mihaylova, B., Kromitoglou, E. and Intzes, S., 2025. Solving the job shop scheduling problem - Different techniques and programming languages. Vocational Education, 27(3-4), pp. 177–194. https://doi.org/10.53656/voc25-3-4-12
Da Col, G. and Teppan, E.C., 2022. Industrial-size job shop scheduling with constraint programming. Operations Research Perspectives, 9, article 100249. https://doi.org/10.1016/j.orp.2022.100249.
Dauzère-Pérès, S., Ding, J., Shen, L. and Tamssaouet, K., 2024. The flexible job shop scheduling problem: A review. European Journal of Operational Research, 314(2), pp. 409–432. https://doi.org/10.1016/j.ejor.2023.05.017.
DeGarmo, E.P., 1984. Materials and processes in manufacturing. 6th ed. Macmillan publishing.
Gonçalves, J.F., de Magalhães Mendes, J.J. and Resende, M.G.C., 2002. A hybrid genetic algorithm for the job shop scheduling problem (Technical Report TD-5EAL6J). AT&T Labs Research. https://optimization-online.org/wp-content/uploads/2002/09/538.pdf.
Ham, A., Park, M.-J. and Kim, K.M., 2021. Energy-aware flexible job shop scheduling using mixed integer programming and constraint programming. Mathematical Problems in Engineering, 2021, article 8035806. https://doi.org/10.1155/2021/8035806.
Ismail, A.H., 2018. Multiple Ant Colony Algorithm for Job Shop Scheduling problem. Master's thesis, College of Engineering, University of Baghdad, Baghdad, Iraq.
Leusin, M.E., Frazzon, E.M., Uriona Maldonado, M., Kück, M. and Freitag, M., 2018. Solving the job-shop scheduling problem in the industry 4.0 era. Technologies, 6(4), P. 107. https://doi.org/10.3390/technologies6040107.
Li, Z. and Chen, Y., 2023. Minimizing the makespan and carbon emissions in the green flexible job shop scheduling problem with learning effects. Scientific Reports, 13, article 6369. https://doi.org/10.1038/s41598-023-33615-z.
Lunardi, W.T., Birgin, E.G., Laborie, P., Ronconi, D.P. and Voos, H., 2020. Mixed integer linear programming and constraint programming models for the online printing shop scheduling problem. Computers and Operations Research, 123, article 105020. https://doi.org/10.1016/j.cor.2020.105020.
Magalhães, R., Sousa, J.M.C. and Vieira, S.M., 2025. A heuristic guided genetic algorithm applied to dual resource job shop scheduling. Mathematics, 13(19), p.3116.
Momenikorbekandi, A. and Kalganova, T., 2025. Intelligent scheduling methods for optimisation of job shop scheduling problems in the manufacturing sector: A Systematic Review. Electronics, 14(8), p. 1663. https://doi.org/10.3390/electronics14081663.
Olhager, J., 2013. Evolution of operations planning and control: From production to supply chains. International Journal of Production Research, 51(23–24), pp. 6836–6843. https://doi.org/10.1080/00207543.2012.761363.
Park, J.-S., Ng, H.-Y., Chua, T.-J., Ng, Y.-T. and Kim, J.-W., 2021. Unified genetic algorithm approach for solving flexible job-shop scheduling problem. Applied Sciences, 11(14), article 6454. https://doi.org/10.3390/app11146454.
Park, M.-J. and Ham, A., 2022. Energy-aware flexible job shop scheduling under time-of-use pricing. International Journal of Production Economics, 248, article 108507. https://doi.org/10.1016/j.ijpe.2022.108507.
Pinedo, M.L., 2016. Scheduling: Theory, algorithms, and systems. 5th ed. Springer. https://doi.org/10.1007/978-3-319-26531-1.
Prata, B.A., Abreu, L.R. and Nagano, M.S., 2024. Applications of constraint programming in production scheduling problems: A descriptive bibliometric analysis. Results in Control and Optimization, 14, p. 100350. https://doi.org/10.1016/j.rico.2023.100350.
Shi, G.Y., 1997. A genetic algorithm applied to a classic job-shop scheduling problem. International Journal of Systems Science, 28(1), pp. 25–32. https://doi.org/10.1080/00207729708929359.
Stanković, A., Petrović, G., Ćojbašić, Ž. and Marković, D., 2020. An application of metaheuristic optimization algorithms for solving the flexible job-shop scheduling problem. Operational Research in Engineering Sciences: Theory and Applications, 3(3), pp. 13–28. https://doi.org/10.31181/oresta20303013s.
Tarigan, M., Gaol, F.L., Gunawan, A.A.S. and Budiharto, W., 2025. Advancing dynamic flexible job shop scheduling with a real-world dataset and genetic adaptive scheduling system. IEEE Access, 13, pp. 193020–193031. https://doi.org/10.1109/ACCESS.2025.3630184
Terbrack, H. and Claus, T., 2025. The generalized energy-aware flexible job shop scheduling model: A constraint programming approach. Computers and Industrial Engineering, 204, article 111065. https://doi.org/10.1016/j.cie.2025.111065.
Valencia-Rodriguez, A., et al., 2026. Evolutionary optimization for job shop scheduling with blocking: A genetic algorithm approach. Algorithms, 19(2), p.115.
Vital-Soto, A., Azab, A. and Baki, M.F., 2020. Mathematical modeling and a hybridized bacterial foraging optimization algorithm for the flexible job-shop scheduling problem with sequencing flexibility. Journal of Manufacturing Systems, 54, pp. 74–93. https://doi.org/10.1016/j.jmsy.2019.11.010.
Wang, S., Li, J., Jiao, Q. and Ma, F., 2025. Design patterns of deep reinforcement learning models for job shop scheduling problems. Journal of Intelligent Manufacturing, 36, pp. 3741–3759. https://doi.org/10.1007/s10845-024-02454-8
Xiong, F. and Liu, H., 2026. Logic-based Benders decomposition methods for the distributed flexible job shop scheduling problem. European Journal of Operational Research, 329(3), pp. 778–797. https://doi.org/10.1016/j.ejor.2025.08.039.
Yuraszeck, F., Mejía, G., Rossit, D.A. and Lüer-Villagra, A., 2024. A constraint programming-based lower bounding procedure for the job shop scheduling problem. Computers & Operations Research, 161, p. 106362. https://doi.org/10.1016/j.cor.2024.106964.
Zhang, G., Hu, Y., Sun, J. and Zhang, W., 2020. An improved genetic algorithm for the flexible job shop scheduling problem with multiple time constraints. Swarm and Evolutionary Computation, 54, article 100664. https://doi.org/10.1016/j.swevo.2020.100664.
Zhao, G. and Lu, J., 2026. Application of a reinforcement learning-based improved genetic algorithm in flexible job-shop scheduling problems. Mathematics, 14(2), P. 307.