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

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.

Authors:

• Seyed Habib A. Rahmati

Keywords:

• Scheduling
• Flexible job shop scheduling problem
• controlled elitism non-dominated sorting genetic algorithm

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.