A Study of Cooperative Co-evolutionary Genetic Algorithm for Solving Flexible Job Shop Scheduling Problem

Flexible Job Shop Problem (FJSP) is an extension of classical Job Shop Problem (JSP). The FJSP extends the routing flexibility of the JSP, i.e assigning machine to an operation. Thus it makes it more difficult than the JSP. In this study, Cooperative Coevolutionary Genetic Algorithm (CCGA) is presented to solve the FJSP. Makespan (time needed to complete all jobs) is used as the performance evaluation for CCGA. In order to test performance and efficiency of our CCGA the benchmark problems are solved. Computational result shows that the proposed CCGA is comparable with other approaches.

Authors:

• Lee Yih Rou
• Hishammuddin Asmuni

Keywords:

• Co-evolution
• Genetic Algorithm (GA)
• Flexible JobShop Problem(FJSP)

References:

[1] N.B. Ho and J.C. Tay. GENACE: an efficient cultural algorithm for
solving the flexible job-shop problem. in Evolutionary Computation,
2004. CEC2004. Congress on. 2004: p. 1759-1766 Vol.2F. Pezzella, G.
Morganti, and G. Ciaschetti, A genetic algorithm for the Flexible Jobshop
Scheduling Problem. Comput. Oper. Res., 2008. 35(10): p. 3202-
3212.
[2] F. Pezzella, G. Morganti and G. Ciaschetti, A genetic algorithm for the
Flexible Job-shop Scheduling Problem. Comput. Oper. Res., 2008.
35(10): p. 3202-3212J. Gao, L. Sun, and M. Gen, A hybrid genetic and
variable neighborhood descent algorithm for flexible job shop
scheduling problems. Computers & Operations Research, 2008. 35(9): p.
2892-2907.
[3] P. Brucker and R. Schlie, Job-shop scheduling with multi-purpose
machines. Computing, 1990. 45(4): p. 369-375.S. Dauzère-Pérès and J.
Paulli, An integrated approach for modeling and solving the general
multiprocessor job-shop scheduling problem using tabu search. Annals
of Operations Research, 1997. 70(0): p. 281-306.
[4] J. Gao, L. Sun and M. Gen, A hybrid genetic and variable neighborhood
descent algorithm for flexible job shop scheduling problems. Computers
& Operations Research, 2008. 35(9): p. 2892-2907.
[5] H. Chen, J. Ihlow and C. Lehmann. A genetic algorithm for flexible jobshop
scheduling. in Robotics and Automation, 1999. Proceedings. 1999
IEEE International Conference on. 1999: p. 1120-1125 vol.
[6] S. Dauzère-Pérès and J. Paulli, An integrated approach for modeling and
solving the general multiprocessor job-shop scheduling problem using
tabu search. Annals of Operations Research, 1997. 70(0): p. 281-306.
[7] I. Kacem, S. Hammadi and P. Borne, Approach by localization and
multiobjective evolutionary optimization for flexible job-shop
scheduling problems. Systems, Man, and Cybernetics, Part C:
Applications and Reviews, IEEE Transactions on, 2002. 32(1): p. 1-13.
[8] L.-N. Xing, Y.-W. Chen and K.-W. Yang, Multi-population interactive
coevolutionary algorithm for flexible job shop scheduling problems.
Computational Optimization and Applications.
[9] M. Yazdani, M. Amiri and M. Zandieh, Flexible job-shop scheduling
with parallel variable neighborhood search algorithm. Expert Syst. Appl.,
2010. 37(1): p. 678-687.M. Mastrolilli and L. M. Gambardella, Effective
Neighborhood Functions for the Flexible Job Shop Problem. 1998,
Istituto Dalle Molle Di Studi Sull Intelligenza Artificiale.
[10] M. Yazdani, M. Gholami, M. Zandieh and M. Mousakhani, A Simulated
Annealing Algorithm for Flexible Job-Shop Scheduling Problem.
Journal of Applied Sciences, 2009. 9(4): p. 662-670.
[11] P. Brandimarte, Routing and scheduling in a flexible job shop by tabu
search. Annals of Operations Research, 1993. 41(3): p. 157-183.
[12] J. Hurink, B. Jurisch and M. Thole, Tabu search for the job-shop
scheduling problem with multi-purpose machines. OR Spectrum, 1994.
15(4): p. 205-215.K. A. De Jong and M. A. Potter, A Cooperative
Coevolutionary Approach to Function Optimization, in The Third
Conference on Parallel Problem Solving from Nature: Parallel Problem
Solving from Nature. 1994, Springer-Verlag. p. 249-257.
[13] M. Mastrolilli and L.M. Gambardella, Effective Neighborhood Functions
for the Flexible Job Shop Problem. 1998, Istituto Dalle Molle Di Studi
Sull Intelligenza Artificiale.
[14] Mesghouni K., Hammadi S. and Borne P. Evolution programs for jobshop
scheduling. in Systems, Man, and Cybernetics, 1997.
'Computational Cybernetics and Simulation'., 1997 IEEE International
Conference on. 1997: p. 720-725 vol.1
[15] E.M. David and M. Risto, Forming neural networks through efficient
and adaptive coevolution. Evol. Comput., 1997. 5(4): p. 373-399.
[16] K.A. De Jong and M.A. Potter, Evolving Complex Structures via
Cooperative Coevolution. Evolutionary Programming, 1995.
[17] K.A. De Jong and M.A. Potter, A Cooperative Coevolutionary Approach
to Function Optimization, in The Third Conference on Parallel Problem
Solving from Nature: Parallel Problem Solving from Nature. 1994,
Springer-Verlag. p. 249-257.
[18] K.M. Lee, T. Yamakawa and L. Keon-Myung. A genetic algorithm for
general machine scheduling problems. in Knowledge-Based Intelligent
Electronic Systems, 1998. Proceedings KES '98. 1998 Second
International Conference on. 1998: p. 60-66 vol.2