[1] Wang Chuyang, Li Xiaoping, Wang Qian,. Tabu search for no-wait flowshop scheduling problemto minimize maximum lateness [J]. Journal of Southeast University (English Edition), 2010, 26 (1): 26-30. [doi:10.3969/j.issn.1003-7985.2010.01006]

Copy

Tabu search for no-wait flowshop scheduling problemto minimize maximum lateness()

Share：

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

Volumn:

26

Issue:

2010 1

Page:

26-30

Research Field:

Automation

Publishing date:

2010-03-30

Info

Title:

Tabu search for no-wait flowshop scheduling problemto minimize maximum lateness

Author(s):

Wang Chuyang;  Li Xiaoping;  Wang Qian

School of Computer Science and Engineering, Southeast University, Nanjing 210096, China

Keywords:

tabu search;  no-wait flowshop;  scheduling;  maximum lateness;  neighborhood

PACS:

TP278

DOI:

10.3969/j.issn.1003-7985.2010.01006

Abstract:

In order to solve the no-wait flowshop scheduling problem to minimize the maximum lateness, three job-block-based neighborhoods are proposed, among which the block exchange neighborhood have a size of O(n⁴)while the block swap and the simplified block exchange neighborhoods have a size of O(n³).With larger sizes than the existing neighborhoods, the proposed neighborhoods can enhance the solution quality of local search algorithms.Speedup properties for the neighborhoods are developed, which can evaluate a neighbor in constant time and explore the neighborhoods in time proportional to their proposed sizes. Unlike the dominance-rule-based speedup method, the proposed speedups are applicable to any machine number.Three neighborhoods and the union of block swap and the simplified block exchange neighborhoods are compared in the tabu search.Computational results on benchmark instances show that three tabu search algorithms with O(n³)neighborhoods outperform the existing algorithms and the tabu search algorithm with the union has the best performance among all the tested algorithms.

References:

[1] Brown S I, McGarvey R, Ventura J A. Total flowtime and makespan for a no-wait m-machine flowshop with set-up times separated [J]. Journal of the Operational Research Society, 2004, 55(6): 614-621.
[2] Hall N G, Sriskandarayah C. A survey of machine scheduling problems with blocking and no-wait in process [J]. Operations Research, 1996, 44(3): 510-525.
[3] Graham R L, Lawler E L, Lenstra J K, et al. Optimization and approximation in deterministic sequencing and scheduling: a survey [J]. Annals of Discrete Mathematics, 1979, 5: 287-326.
[4] Röck H. Some new results in flow shop scheduling [J]. Mathematical Methods of Operations Research, 1984, 28(1): 1-16.
[5] Dileepan P. A note on minimizing maximum lateness in a two-machine no-wait flowshop [J]. Computers and Operations Research, 2004, 31(12): 2111-2115.
[6] Wang X L, Cheng T C E. A heuristic approach for two-machine no-wait flowshop scheduling with due dates and class setups [J]. Computers and Operations Research, 2006, 33(5): 1326-1344.
[7] Ruiz R, Allahverdi A. No-wait flowshop with separate setup times to minimize maximum lateness [J]. The International Journal of Advanced Manufacturing Technology, 2007, 35(5/6): 551-565.
[8] Allahverdi A, Aldowaisan T. No-wait flowshops with bicriteria of makespan and maximum lateness [J]. European Journal of Operational Research, 2004, 152(1): 132-147.
[9] Ruiz R, Allahverdi A. New heuristics for no-wait flow shops with a linear combination of makespan and maximum lateness [J]. International Journal of Production Research, 2009, 47(20): 5717-5738.
[10] Glover F. Tabu search—Part Ⅰ [J]. ORSA Journal on Computing, 1989, 1(3): 190-206.
[11] Glover F, Laguna M. Tabu search[M]. Dordrecht: Kluwer Academic Publishers, 1997.
[12] 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.
[13] Taillard E. Robust taboo search for the quadratic assignment problem [J]. Parallel Computing, 1991, 17(4/5): 443-455.
[14] Nawaz M, Enscore Jr E E, Ham I. A heuristic algorithm for the m-machine, n-job flow shop sequencing problem [J]. Omega, International Journal of Management Science, 1983, 11(1): 91-95.
[15] Misevicius A. A tabu search algorithm for the quadratic assignment problem [J]. Computational Optimization and Applications, 2005, 30(1): 95-111.
[16] Potts C N, Van Wassenhove L N. A decomposition algorithm for the single machine total tardiness problem [J]. Operations Research Letters, 1982, 1(5): 177-181.
[17] Reeves C R. Landscapes, operators and heuristic search [J]. Annals of Operations Research, 1999, 86(1): 473-490.
[18] Fink A, Voß S. Solving the continuous flow-shop scheduling problem by metaheuristics [J]. European Journal of Operational Research, 2003, 151(2): 400-414.

Memo

Memo:

Biographies: Wang Chuyang(1975—), male, graduate; Li Xiaoping(corresponding author), male, doctor, professor, xpli@seu.edu.cn.
Foundation items: The National Natural Science Foundation of China(No.60672092, 60504029, 60873236), the National High Technology Research and Development Program of China(863 Program)(No.2008AA04Z103).
Citation: Wang Chuyang, Li Xiaoping, Wang Qian. Tabu search for no-wait flowshop scheduling problem to minimize maximum lateness[J]. Journal of Southeast University(English Edition), 2010, 26(1): 26-30.

Common functions