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

Authors: Lee Yih Rou, Hishammuddin Asmuni

Abstract:

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.

Keywords: Co-evolution, Genetic Algorithm (GA), Flexible JobShop Problem(FJSP)

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

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