[1] Liao Xiaoping, Liu Yougen, Li Xiaoping,. Hybrid evolutionary algorithm for no-wait flow shopsto minimize makespan and total flowtime [J]. Journal of Southeast University (English Edition), 2008, 24 (4): 450-454. [doi:10.3969/j.issn.1003-7985.2008.04.011]

Copy

Hybrid evolutionary algorithm for no-wait flow shopsto minimize makespan and total flowtime()

Share：

Journal of Southeast University (English Edition)[ISSN:1003-7985/CN:32-1325/N]

Volumn:

24

Issue:

2008 4

Page:

450-454

Research Field:

Automation

Publishing date:

2008-12-30

Info

Title:

Hybrid evolutionary algorithm for no-wait flow shopsto minimize makespan and total flowtime

Author(s):

Liao Xiaoping¹;  Liu Yougen²;  Li Xiaoping²

¹College of Computer and Information Engineering, Hohai University, Nanjing 210098, China
²School of Computer Science and Engineering, Southeast University, Nanjing 210096, China

Keywords:

no-wait flow shop;  objective increment;  makespan;  total flowtime;  evolutionary algorithm

PACS:

TP278

DOI:

10.3969/j.issn.1003-7985.2008.04.011

Abstract:

The NP-hard no-wait flow shop scheduling problems with makespan and total flowtime minimization are considered.Objective increment properties of the problems are analyzed.A non-dominated classification method is introduced to class population individuals into Pareto fronts to improve searching efficiency.Besides investigating the crowding distance and the elitist solution strategy, two effective bi-criteria local search procedures based on objective increments are presented to improve searching effectiveness.Based on the properties and methods, a hybrid evolutionary algorithm is proposed for the considered problems and compared with the best existing algorithms.Experimental results show that the proposed algorithm is effective with high efficiency.

References:

[1] Gangadharan R, Rajendran C.Heuristic algorithms for scheduling in the no-wait flow shop [J].International Journal of Production Economics, 1993, 32(3):285-290.
[2] Rajendran C.A no-wait flow shop scheduling heuristic to minimize makespan [J].Journal of the Operational Research Society, 1994, 45(4):472-478.
[3] Aldowiasan T, Allahverdi A.New heuristics for no-wait flow shops to minimize makespan [J].Computers and Operations Research, 2003, 30(8):1219-1231.
[4] Grabowski J, Pempera J.Some local search algorithms for no-wait flow-shop problem with makespam criterion [J].Computers and Operations Research, 2005, 32(8):2197-2213.
[5] Li Xiaoping, Wu Cheng.Heuristic for no-wait flow shops with makespan minimization based on total idle-time increments [J].Science in China, Series F:Information Sciences, 2008, 51(7):896-909.
[6] Li Xiaoping, Wang Qian, Wu Cheng.Heuristic for no-wait flow shops with makespan minimization [J].International Journal of Production Research, 2008, 46(9):2519-2530.
[7] Allahverdi A, Aldowaisan T.No-wait flow shops with bicriteria of makespan and total completion time [J].Journal of the Operational Research Society, 2002, 53(9):1004-1015.
[8] Allahverdi A, Aldowaisan T.No-wait flow shops with bicriteria of makespan and maximum lateness [J].European Journal of Operational Research, 2004, 152(1):132-147.
[9] Reza Tavakkoli-Moghaddam, Alireza Rahimi-Vahed, Ali Hossein Mirzaei.A hybrid multi-objective immune algorithm for a flow shop scheduling problem with bi-objectives:weighted mean completion time and weighted mean tardiness [J].Information Sciences, 2007, 177:5072-5090.
[10] Jones D F, Mirrazavi S K, Tamiz M.Multiobjective meta-heuristics:an overview of the current state-of-the-art [J].European Journal of Operational Research, 2002, 137(1):1-9.
[11] Deb K, Pratap A, Agarwal S, et al.A fast and elitist multiobjective genetic algorithm:NSGA-Ⅱ [J].IEEE Transactions on Evolutionary Computation, 2002, 6(2):182-197.
[12] Taillard E.Benchmarks for basic scheduling problems [J].European Journal of Operational Research, 1993, 64(2):278-285.
[13] Nawaz M, Enscore E E Jr, Ham I.A heuristic algorithm for the m-machine, n-job flow shop sequencing problem [J].Omega, 1983, 11(1):91-95.
[14] Allahverdi A, Aldowaisan T.New heuristics to minimize total completion time in m-machine flow shops [J].International Journal of Production Economics, 2002, 77(1):71-83.

Memo

Memo:

Biography: Liao Xiaoping(1965—), male, lecturer, xpliao@sina.com.
Foundation items: The National Natural Science Foundation of China(No.60504029, 60672092), the National High Technology Research and Development Program of China(863 Program)(No.2008AA04Z103).
Citation: Liao Xiaoping, Liu Yougen, Li Xiaoping.Hybrid evolutionary algorithm for no-wait flow shops to minimize makespan and total flowtime[J].Journal of Southeast University(English Edition), 2008, 24(4):450-454.

Common functions