A review of TSP based approaches for flowshop scheduling

被引:62
作者
Bagchi, TP
Gupta, JND
Sriskandarajah, C
机构
[1] Univ Texas, Sch Management, Richardson, TX 75083 USA
[2] Natl Inst Ind Engn, Bombay 400087, Maharashtra, India
[3] Univ Alabama, Dept Accounting & Informat Syst, Huntsville, AL 35899 USA
关键词
manufacturing; flowshop scheduling; NP-hard; robotic; limited buffer; blocking; and no-wait flowshops; setup times; traveling salesman problem;
D O I
10.1016/j.ejor.2004.06.040
中图分类号
C93 [管理学];
学科分类号
12 [管理学]; 1201 [管理科学与工程]; 1202 [工商管理学]; 120202 [企业管理];
摘要
Contemporary flowshops that are variants of the classical flowshop frequently pose challenging scheduling problems. Such flowshops include no-wait, blocking, and robotic flowshops. These may sometimes be modeled as traveling salesman problems (TSP) and then solved using efficient algorithms available for the TSP. Encountered in auto, electronic, chemical, steel and even modern service industries, such problems are reviewed in this paper. We show that the TSP based approach is quite effective over a broad range. It tackles no-wait flowshops, blocking flowshops, group scheduling of parts in a flowshop using a generalized extension of the TSP, lot streaming and scheduling problems, and as recently done, scheduling of parts and robot movements in automated production cells. In this review paper, we describe several well-documented applications of no-wait and blocking scheduling models and illustrate some ways in which the increasingly used modern manufacturing systems such as robotic cells may be modeled as TSP. We also review the computational complexity of a wide variety of flowshop models. Finally, we suggest some fruitful directions for future research. (c) 2005 Elsevier B.V. All rights reserved.
引用
收藏
页码:816 / 854
页数:39
相关论文
共 162 条
[1]
Minimizing cycle time in a blocking flowshop [J].
Abadi, INK ;
Hall, NG ;
Sriskandarajah, C .
OPERATIONS RESEARCH, 2000, 48 (01) :177-180
[2]
No-wait flow shop scheduling with large lot sizes [J].
Agnetis, A .
ANNALS OF OPERATIONS RESEARCH, 1997, 70 (0) :415-438
[3]
Part sequencing in three-machine no-wait robotic cells [J].
Agnetis, A ;
Pacciarelli, D .
OPERATIONS RESEARCH LETTERS, 2000, 27 (04) :185-192
[5]
A review of scheduling research involving setup considerations [J].
Allahverdi, A ;
Gupta, JND ;
Aldowaisan, T .
OMEGA-INTERNATIONAL JOURNAL OF MANAGEMENT SCIENCE, 1999, 27 (02) :219-239
[6]
Scheduling of parts and robot activities in a two machine robotic cell [J].
Aneja, YP ;
Kamoun, H .
COMPUTERS & OPERATIONS RESEARCH, 1999, 26 (04) :297-312
[7]
[Anonymous], 1997, Tabu Search
[8]
[Anonymous], 2002, COMB OPT (SER)
[9]
[Anonymous], 1979, Computers and Intractablity: A Guide to the Theoryof NP-Completeness
[10]
[Anonymous], TRAVELING SALESMAN P