Proposing a Pareto-based Multi-Objective Evolutionary Algorithm to Flexible Job Shop Scheduling Problem

Authors: Seyed Habib A. Rahmati

Abstract:

During last decades, developing multi-objective evolutionary algorithms for optimization problems has found considerable attention. Flexible job shop scheduling problem, as an important scheduling optimization problem, has found this attention too. However, most of the multi-objective algorithms that are developed for this problem use nonprofessional approaches. In another words, most of them combine their objectives and then solve multi-objective problem through single objective approaches. Of course, except some scarce researches that uses Pareto-based algorithms. Therefore, in this paper, a new Pareto-based algorithm called controlled elitism non-dominated sorting genetic algorithm (CENSGA) is proposed for the multi-objective FJSP (MOFJSP). Our considered objectives are makespan, critical machine work load, and total work load of machines. The proposed algorithm is also compared with one the best Pareto-based algorithms of the literature on some multi-objective criteria, statistically.

Keywords: Scheduling, Flexible job shop scheduling problem, controlled elitism non-dominated sorting genetic algorithm

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1081926

References:

[1] X. Wang, L. Gao, G. Zhang, X. Shao, A multi-objective genetic algorithm based on immune and entropy principle for flexible job-shop scheduling problem, Intelligent Journal of Advance Manufacturing Technology vol. 51, no. (5-8), 2010, pp. 757-767.
[2] P. Brandimarte, Routing and scheduling in a flexible job shop by taboo search. Annual operation research vol. 41, 1993, pp. 157-183.
[3] J.W. Barnes, J.B. Chambers, Flexible job shop scheduling by tabu search. Graduate program in operations research and industrial engineering. University of Texas, Austin, Technical Report Series, ORP96-09, 1996.
[4] W.J. Xia, Z.M. Wu, An effective hybrid optimization approach for multi-objective flexible job-shop scheduling problems. Computer and Industrial Engineering vol. 48, no. 2, 2005, pp. 409-425.
[5] E. Hurink, B. Jurisch, M. Thole, Tabu search for the job shop scheduling problem with multi-purpose machine. Operations Research Spectrum vol. 15, no. 4, 1994, pp. 205-215.
[6] M. Mastrolilli, L.M. Gambardella, Effective neighborhood functions for the flexible job shop problem. Journal of Scheduling vol. 3, no. 1, 2000, pp. 3-20.
[7] C.R. Scrich, V.A. Armentano, M. Laguna, Tardiness minimization in a flexible job shop: a tabu search approach. Intelligent Journal of Advance Manufacturing Technology vol. 15, no. 1, 2004, pp. 103-115.
[8] M. Saidi-Mehrabad, P. Fattahi, Flexible job shop scheduling with Tabu search algorithms. Intelligent Journal of Advance Manufacturing Technology vol. 32, no. 5-6, 2007, pp. 563-570.
[9] Y. Mati, N. Rezg, , X.L. Xie, An integrated greedy heuristic for a flexible job shop scheduling problem. Proceedings of the 2001 IEEE International Conference on Systems, Man, and Cybernetics. OPAC, Tucson, 2001, pp. 2534-2539.
[10] N.B. Ho, J.C.J. Tay, E. Lai, An effective architecture for learning and evolving flexible job-shop schedules, European Journal of Operational Research vol. 179, 2007, pp. 316-333.
[11] J.C. Chen, K.H. Chen, J.J. Wu, C.W. Chen, A study of the flexible job shop scheduling problem with parallel machines and reentrant process. Intelligent Journal of Advance Manufacturing Technology vol. 39, no. (3-4), 2008, pp. 344-354.
[12] M. Yazdani, M. Amiri, M. Zandieh, Flexible job-shop scheduling with parallel variable neighborhood search algorithm. Expert Systems with Applications vol. 37, 2010, pp. 678-687.
[13] S.H.A. Rahmati, M. Zandieh, A new biogeography-based optimization (BBO) algorithm for the flexible job shop scheduling problem, International Journal of Advance Manufacturing Technology, 2011, DOI 10.1007/s00170-011-3437-9.
[14] I. Kacem, S. Hammadi, P. Borne, Approach by localization and multiobjective evolutionary optimization for flexible job-shop scheduling problems. IEEE Transactions on Systems, Man and Cybernetics Part C: Applications and Reviews vol. 32, no. 2, 2002, pp. 172-172.
[15] H.B. Liu, A. Abraham, O. Choi, S.H. Moon, Variable neighborhood particle swarm optimization for multi-objective flexible job-shop scheduling problems. Lecture Notes in Computer Science vol. 4247, 2006, pp.197-204.
[16] J. Gao, M. Gen, L.Y. Sun, X.H. Zhao, A hybrid of genetic algorithm and bottleneck shifting for multiobjective flexible job shop scheduling problems. Computer and Industrial Engineering vol. 53, no. 1, 2007, pp. 149-162.
[17] K. Deb, Multiobjective optimization using evolutionary algorithms. Chichester, U.K: Wiley, 2001.
[18] E. Zitzler, L. Thiele, Multiobjective optimization using evolutionary algorithms a comparative case study. In A.E. Eiben, T. Back, M. Schoenauer and H. P. Schwefel (Eds.), Fifth International Conference on Parallel Problem Solving from Nature (PPSN-V), Berlin, Germany, 1998, pp. 292 - 301.
[19] J R. Schott, Fault tolerant design using single and multicriteria genetic algorithms optimization. Master-s thesis, Department of Aeronautics and Astronautics, Massachusetts Institute of Technology, Cambridge, MA, 1995.
[20] N. Karimi, M. Zandieh, H.R. Karamooz, Bi-objective group scheduling in hybrid flexible flow shop: A multi-phase approach. Expert Systems with Applications vol. 37, 2010, pp. 4024-4032.
[21] M. Hollander , D.A. Wolfe, Non-parametric Statistical Methods. John Wiley & Sons, 1973.
[22] G. O. Young, "Synthetic structure of industrial plastics (Book style with paper title and editor)," in Plastics, 2nd ed. vol. 3, J. Peters, Ed. New York: McGraw-Hill, 1964, pp. 15-64.