Survey for Open Shop Scheduling
DOI:
https://doi.org/10.29304/jqcsm.2025.17.11965Keywords:
Open shop scheduling, Operations, Makespan, Open shopAbstract
In the Open Shop Scheduling, a group of jobs are assigned to several machines, and each job can be handled on any machine without following a set order. The main difficulty is figuring out the best scheduling configuration to reduce the makespan or the amount of time needed to finish all jobs from the beginning of the first work to the end of the last. Multiple jobs requiring the same machine simultaneously can cause scheduling conflicts, which must be avoided while considering work order flexibility among different machines. Scheduling considerations in OSS are extremely complicated because every job must be executed on every machine exactly once. The goal is to determine an efficient sequence that balances the workload across available machines, minimizing makespan while adhering to various operational constraints. This survey provides a comprehensive analysis of Open Shop Scheduling, a widely studied topic in scientific research focusing on minimizing makespan, synthesizes key contributions from the literature, highlights recent advancements, and outlines potential avenues for future research.
Downloads
References
J. Dick, J. M. Schumann, B. Nuseibeh, L. Athens, J. Zobel, and A. M. Qazi, “Scheduling: theory, algorithms, and systems,” 2022.
K. R. Baker and D. Trietsch, Principles of sequencing and scheduling. John Wiley & Sons,2018.
S. M. Goldansaz, F. Jolai, and A. H. Z. Anaraki, “A hybrid imperialist competitive algorithm for minimising makespan in a multi-processor open shop,” Applied Mathematical Modelling, vol. 37, no. 23, pp. 9603–9616, 2013.
T. Gonzalez and S. Sahni, “Open shop scheduling to minimise finish time,” Journal of the ACM (JACM), vol. 23, no. 4, pp. 665–679, 1976.
M. B. Shareh, S. H. Bargh, A. A. R. Hosseinabadi, and A. Slowik, “An improved bat optimisation algorithm to solve the tasks scheduling problem in an open shop,” Neural Computing and Applications, vol. 33, pp. 1559–1573, 2021.
C. Low and Y. Yeh, “Genetic algorithm-based heuristics for an open shop scheduling problem with setup, processing, and removal times separated,” Robotics and Computer-Integrated Manufacturing, vol. 25, no. 2, pp. 314–322, 2009.
A. H. Lal, V. KR, and A. N. Haq, “The mean flow time in open shop scheduling,” Journal of Advances in Management Research, vol. 17, no. 2, pp. 251–261, 2020.
I. Pietri and R. Sakellariou, “Mapping virtual machines onto physical machines in cloud computing: A survey,” ACM Computing Surveys (CSUR), vol. 49, no. 3, pp. 1–30, 2016.
M. L. Pinedo and M. L. Pinedo, “Design and implementation of scheduling systems: More advanced concepts,” Scheduling: Theory, Algorithms, and Systems, pp. 485–508, 2016.
J. Blazewicz, K. H. Ecker, E. Pesch, G. Schmidt, and J. Weglarz, Scheduling computer and manufacturing processes. Springer Science & Business Media, 2013.
E. L. Lawler, J. K. Lenstra, A. H. R. Kan, and D. B. Shmoys, “Sequencing and scheduling: Algorithms and complexity,” Handbooks in operations research and management science, vol. 4, pp. 445–522, 1993.
M. Sophia, S. Jayakumar, and M. Lakshmi, “Minimizing the total completion time for hypothetical cases in open shop scheduling problem.”
M. M. Ahmadian, M. Khatami, A. Salehipour, and T. Cheng, “Four decades of research on the open-shop scheduling problem to minimise the makespan,” European Journal of Operational Research, vol. 295, no. 2, pp. 399–426, 2021.
S. Aghighi, E. Mehdizadeh, and S. T. A. Niaki, “No-wait open-shop scheduling problems with reverse flows,” Journal of Engineering Research, 2024.
A. M. Cañadas, O. M. Mendez, J.-C. Riaño-Rojas, and J.-D. Hormaza, “An algebraic approach to the solutions of the open shop scheduling problem,” Computation, vol. 11, no. 5, p. 94, 2023.
W. Kubiak, Book of Open Shop Scheduling. Springer, 2022.
H.-M. Gu, R. Hu, B. Qian, H.-P. Jin, and L. Wang, “Whale optimisation algorithm with local search for open shop scheduling problem to minimise the makespan,” in Intelligent Computing Theories and Application: 15th International Conference, ICIC 2019, Nanchang, China, August 3–6, 2019, Proceedings, Part II 15. Springer, 2019, pp. 678–687.
A. Atay, P. Calleja, and S. Soteras, “Open shop scheduling games,” European Journal of Operational Research, vol. 295, no. 1, pp. 12–21, 2021.
J. Li, X. Dong, K. Zhang, and S. Han, “Solving open shop scheduling problem via graph attention neural network,” in 2020 IEEE 32nd International Conference on Tools with Artificial Intelligence (ICTAI). IEEE, 2020, pp. 277–284.
H. Wang and W. Chen, “Task scheduling for transport and pick robots in logistics: A comparative study on constructive heuristics,” Autonomous Intelligent Systems, vol. 1, no. 1, p. 17,2021.
Z. Zhuang, Z. Lu, Z. Huang, C. Liu, and W. Qin, “A novel complex network-based dynamic rule selection approach for open shop scheduling problem with release dates,” Math. Biosci.Eng, vol. 16, no. 5, pp. 4491–4505, 2019.
K. Kumar and J. Dhas, “Mitigation of makespan time in job shop scheduling problem using a gannet optimisation algorithm.” EAI Endorsed Transactions on Scalable Information Systems, vol. 10, no. 5, 2023.
G. Koßmann, L. Binkowski, C. Tutschku, and R. Schwonnek, “Open-shop scheduling with hard constraints,” arXiv preprint arXiv:2211.05822, 2022.
H. Alghamdi, T. Alsubait, H. Alhakami, and A. Baz, “A review of optimisation algorithms for university timetable scheduling,” Engineering, Technology & Applied Science Research,
vol. 10, no. 6, pp. 6410–6417, 2020.
A. Tsirlin and A. Balunov, “Job-shop scheduling problem and its solution method,” 2022.
M. A. Belmamoune, L. Ghomri, and Z. Yahouni, “Solving a job shop scheduling problem using learning algorithm,” in International Workshop on Service Orientation in Holonic and Multi-Agent Manufacturing. Springer, 2022, pp. 196–209.
A. Bouzidi, M. E. Riffi, and M. Barkatou, “Cat swarm optimisation for solving the open shop scheduling problem,” Journal of Industrial Engineering International, vol. 15, no. 2, pp.367–378, 2019.
Y. Fu and A. Banerjee, “A stochastic programming model for service scheduling with uncertain demand: an application in open-access clinic scheduling,” in Operations Research Forum, vol. 2. Springer, 2021, pp. 1–32.
S. Knust, N. V. Shakhlevich, S. Waldherr, and C. Weiß, “Shop scheduling problems with pliable jobs,” Journal of Scheduling, vol. 22, pp. 635–661, 2019.
L. R. Abreu, J. O. Cunha, B. A. Prata, and J. M. Framinan, “A genetic algorithm for scheduling open shops with sequence-dependent setup times,” Computers & Operations Research, vol.113, p. 104793, 2020.
T. F. Abdelmaguid, “Bi-objective dynamic multiprocessor open shop scheduling: an exact algorithm,” Algorithms, vol. 13, no. 3, p. 74, 2020.
V. H. L. C. Lima and B. de Athayde Prata, “Um algoritmo híbrido busca tabu/ils para o problema de sequenciamento da produção em ambiente open shop,” Exacta, vol. 19, no. 4, pp.729–744, 2021.
W. Kubiak, “On the complexity of open shop scheduling with time lags,” Journal of Scheduling, vol. 26, no. 3, pp. 331–334, 2023.
J. Dong, R. Jin, G. Lin, B. Su, W. Tong, and Y. Xu, “An efficient polynomial-time approximation scheme for parallel multi-stage open shops,” arXiv preprint arXiv:2205.14407, 2022.
S. H. Shams Lahroudi, F. Mahalleh, and S. Mirkamali, “Multiobjective parallel algorithms for solving biobjective open shop scheduling problem,” Complexity, vol. 2022, no. 1, p. 5043058,2022.
A. A. Rahmani Hosseinabadi, J. Vahidi, B. Saemi, A. K. Sangaiah, and M. Elhoseny, “Extended genetic algorithm for solving open-shop scheduling problem,” Soft computing, vol. 23, pp. 5099–5116, 2019.
G. Ni and L. Chen, “Improved scheduling for the three-machine proportionate open shop and mixed shop minimum makespan problems,” IEEE Access, vol. 8, pp. 186 805–186 812, 2020.
K. Nip and Z. Wang, “A complexity analysis and algorithms for two-machine shop scheduling problems under linear constraints,” Journal of Scheduling, vol. 26, no. 6, pp. 543–558, 2023.
I. G. Smit, J. Zhou, R. Reijnen, Y. Wu, J. Chen, C. Zhang, Z. Bukhsh, W. Nuijten, and Y. Zhang, “Graph neural networks for job shop scheduling problems: A survey,” arXiv preprint arXiv:2406.14096, 2024.
K.-H. Ho, J.-Y. Cheng, J.-H. Wu, F. Chiang, Y.-C. Chen, Y.-Y. Wu, and I.-C. Wu, “Residual scheduling: A new reinforcement learning approach to solving job shop scheduling problem,” IEEE Access, 2024.
A. H. Lal, V. KR, and A. N. Haq, “The mean flow time in open shop scheduling,” Journal of Advances in Management Research, vol. 17, no. 2, pp. 251–261, 2020.
A. Kekli, H. E. Nouri, and O. B. Driss, “Hybrid cat swarm optimisation with genetic algorithm to solve the open shop scheduling with vehicle routing problem,” 2023.
Downloads
Published
How to Cite
Issue
Section
License
Copyright (c) 2025 Tabark Nameer Abd Ali , Luma S. Hasan
This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.
