A Particle Swarm Optimization to Minimize Makespan for a Four-Stage Multiprocessor Open Shop with Dynamic Job Release Time


This paper considers the scheduling problem observed in chip sorting operation of LED manufacturing, where each lot (job) with release time have four operations to be processed on a set of processing stages without pre-determined necessary route. Each stage has one and more identical sorting machines. The sorting machines scheduling problem can be treated as a four-stage multiprocessor open shop problem with dynamic job release, and the objective is minimizing the makespan in the paper. This problem is formulated into a mixed integer programming (MIP) model and empirically shows its computational intractability. Due to the computational intractability, a particle swarm optimization (PSO) algorithm is proposed. A series of computational experiments are conducted to evaluate the performance of the proposed PSO in comparison with exact solution on various small-size problem instances. The results show that the PSO algorithm could finds most optimal or better solutions in one second.

Share and Cite:

Wang, H. and Chou, F. (2015) A Particle Swarm Optimization to Minimize Makespan for a Four-Stage Multiprocessor Open Shop with Dynamic Job Release Time. World Journal of Engineering and Technology, 3, 78-83. doi: 10.4236/wjet.2015.33C012.

Conflicts of Interest

The authors declare no conflicts of interest.


[1] Shiang, W.-J., Lin, Y.-H. and Rau, H. (2009) Application of Simulation to the Scheduling Problem for a Led Sorting System. Proceedings of the Eighth International Conference on Machine Learning and Cybernetics, Baoding, 2875-2879.
[2] Wu, T., Li, B., Wang, L.-W. and Huang, Y. (2010) Study on Auto-Path Planning According to Grade Priority for Sorting Dies. Proceedings of the Ninth International Conference on Machine Learning and Cybernetics, Qingdao, 11-14 July 2010, 1590-1595. http://dx.doi.org/10.1109/icmlc.2010.5580803
[3] Matta, M. (2004) An Empirical and Theoretical Study of Outpatient Scheduling Problems Employing Simulation and Genetic Algorithm Methodologies. Ph.D. Thesis, Duke University.
[4] Matta, M.E. (2009) A Genetic Algorithm for the Proportionate Multiprocessor Open Shop. Computers & Operations Research, 36, 2601-2618. http://dx.doi.org/10.1016/j.cor.2008.11.009
[5] Tamer, F.A., Mohamed, A.S. and Mohamed, A.A. (2014) A Tabu Search Approach for Proportionate Multiprocessor Open shop Scheduling. Computational Optimization and Applications, 58, 187-203. http://dx.doi.org/10.1007/s10589-013-9621-0
[6] Brucker, P., Hurink, J., Jurisch, B. and Wostmann, B. (1997) A Branch and Bound Algorithm for the Open Shop Problem. Discrete Applied Mathematics, 76, 43-59. http://dx.doi.org/10.1016/S0166-218X(96)00116-3
[7] Gueret, C., Jussien, N. and Prins, C. (2000) Using Intelligent Backtracking to Improve Branch-and-Bound Methods: An Application to Open-Shop Problems. European Journal of Operational Research, 127, 344-354. http://dx.doi.org/10.1016/S0377-2217(99)00488-9
[8] Taillard, E. (1993) Benchmarks for Basic Scheduling Problems. European Journal of Operational Research, 64, 278- 285. http://dx.doi.org/10.1016/0377-2217(93)90182-M
[9] Liaw, C.F. (2000) A Hybrid Genetic Algorithm for the Open Shop Scheduling Problem. European Journal of Operational Research, 124, 28-42. http://dx.doi.org/10.1016/S0377-2217(99)00168-X
[10] Naderi, B., Fatemi, Ghomi, S.M.T., Aminnayeri, M. and Zandieh, M. (2011) Scheduling Open Shops with Parallel Machines to Minimize Total Completion Time. Journal of Computational and Applied Mathematics, 235, 1275-1287. http://dx.doi.org/10.1016/j.cam.2010.08.013
[11] Ellur, A. and Ramasamy, P. (2015) Literature Review of Open Shop Scheduling Problems. Intelligent Information Management, 7, 33-52. http://dx.doi.org/10.4236/iim.2015.71004
[12] Graham, R.L., Lawler, E.L., Lenstra, J.K. and Rinnooy Kan, A.H.G. (1979) Optimization and Approximation in Deterministic Sequencing and Scheduling—A Survey. Annals of Discrete Mathematics, 5, 287-326. http://dx.doi.org/10.1016/S0167-5060(08)70356-X
[13] Kennedy, J. and Eberhart, R. (1995) Particle Swarm Optimization. Proceedings of the IEEE International Conference on Neural Networks, 4, 1942-1948. http://dx.doi.org/10.1109/ICNN.1995.488968

Copyright © 2021 by authors and Scientific Research Publishing Inc.

Creative Commons License

This work and the related PDF file are licensed under a Creative Commons Attribution 4.0 International License.