Back
 WJET  Vol.3 No.3 C , October 2015
A Particle Swarm Optimization to Minimize Makespan for a Four-Stage Multiprocessor Open Shop with Dynamic Job Release Time
Abstract: 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.
Cite this paper: 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.
References

[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

 
 
Top