[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(
)
最小化最大延误无等待流水车间调度问题的禁忌搜索算法
)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(n4)while the block swap and the simplified block exchange neighborhoods have a size of O(n3).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(n3)neighborhoods outperform the existing algorithms and the tabu search algorithm with the union has the best performance among all the tested algorithms.
- 为求解最小化最大延误无等待流水车间调度问题, 提出了3个基于任务块交换的邻域, 其中块交换邻域的规模为O(n4), 块对换和简化块交换邻域的规模为O(n3).所提邻域的规模均大于现有邻域, 因此可提高局部搜索算法的解质量.给出了3个邻域的加速性质, 使一个相邻解的评估时间为常量, 邻域的评估时间与其规模成正比.同基于支配规则的加速方法相比, 所提出的加速性质适用于任何机器数.在禁忌搜索中比较了3个邻域, 以及块对换和简化块交换邻域的并集.标准实例集上的计算结果表明:3个基于O(n3)邻域的禁忌搜索算法均好于现有算法;在所有的测试算法中, 采用邻域并集的禁忌搜索算法的性能最好.
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.