An Adaptive Differential Evolution Algorithm for Flow Shop Scheduling to Minimize Makespan

Abstract:

This paper proposed an adaptive differential evolution algorithm. The algorithm has an adaptive mutation factor which can be nonlinear reduced along with evolution process. Mutation factor is declined slowly in the beginning of evolution process in order to improve the global searching ability of the algorithm, and declined rapidly in the later of evolution process. The proposed algorithm is applied to solve flow shop scheduling to minimize makespan, computational experiments on a typical scheduling benchmark shows that the algorithm has a good performance.

• Periodical: Applied Mechanics and Materials (Volumes 411-414)
• Pages: 2089-2092
• DOI: https://doi.org/10.4028/www.scientific.net/AMM.411-414.2089
• Online since: September 2013
• Authors: Yan Ping Zhou
• Keywords: Adaptive, Differential Evolution (DE) Algorithm, Flow Shop Scheduling

References

[1] R. Storn and K. Price, Differential evolution - a simple and efficient adaptive scheme for global optimization over continuous spaces, in: International Computer Science Institute, Technical Report TR-95-012, Berkley, (1995).

[2] R. Storn and K. Price, Differential evolution - a simple and efficient heuristic for global optimization over continuous spaces, J. Global. Optimiz. 11 (1997) 341-359.

[3] Y. P. Zhou and X. S. Gu, Development of differential evolution algorithm, Control and Instruments in Chemical Industry. 34 (2007) 1-5.

[4] P. K. Bergeya and C. Ragsdale, Modified differential evolution: a greedy random strategy for genetic recombination. Omega. 33 (2005) 255-265.

DOI: 10.1016/j.omega.2004.04.009

[5] Y.L. Gao and J.F. Liu, Adaptive Differential evolution algorithm, Journal of Hebei University of Engineering (Natural Science Edition). 25 (2008) 107-109.

[6] S. Das and P.N. Suganthan, Differential evolution: A survey of the state-of-the-art, IEEE Transactions on Evolutionary Computation. 15 (2011) 4-31.

[7] M. R. Garey and D. S. Johnson, The complexity of flowshop and jobshop scheduling, Math. Oper. Res. 1 (1976) 117-129.

[8] E. Nowicki and C. Smutnicki, A fast tabu search algorithm for the permutation flowshop problem, European J. Oper. Res. 91 (1996) 160-175.

DOI: 10.1016/0377-2217(95)00037-2

[9] O. Etiler, B. Toklu, M. Atak and J. Wilson, A genetic algorithm for flow shop scheduling problems, J. Opl. Res. Soc. 55 (2004) 830-835.

DOI: 10.1057/palgrave.jors.2601766

[10] C. Rajendran and H. Ziegler, Ant-colony algorithms for permutation flowshop scheduling to minimize makespan / total flowtime of jobs, European J. Oper. Res. 155 (2004) 426-438.

DOI: 10.1016/s0377-2217(02)00908-6

[11] B. Liu, L. Wang and Y. H. Jin, An effective PSO-based memetic algorithm for flow shop scheduling, IEEE Trans. Syst. Man Cybern. B 37 (2007) 18-27.

DOI: 10.1109/tsmcb.2006.883272

[12] G. Onwubolu and D. Davendra, Scheduling flow shops using differential evolution algorithm, European J. Oper. Res. 171 (2006) 674-692.

DOI: 10.1016/j.ejor.2004.08.043

[13] E. Taillard, Benchmarks for basic scheduling, European J. Oper. Res. 64 (1993) 278-285.