EXACT SOLUTION OF THE NO-WAIT FLOWSHOP SCHEDULING PROBLEM WITH A COMPARISON TO HEURISTIC METHODS

被引:32
作者
PEKNY, JF [1 ]
MILLER, DL [1 ]
机构
[1] DUPONT CO,DEPT CENT RES & DEV,WILMINGTON,DE 19880
关键词
D O I
10.1016/0098-1354(91)85019-Q
中图分类号
TP39 [计算机的应用];
学科分类号
081203 ; 0835 ;
摘要
Intermediate storage utilization provides a key constraint in the scheduling of multistep batch processes. In some cases, unstable intermediates must be processed without delay at any production step so that intermediate storage may not be used. In a flowshop, such a no-wait scenario can be reduced to a traveling salesman problem. This paper details the application of an exact branch and bound algorithm for the traveling salesman problem to solve the no-wait flowshop scheduling problem. We present and solve an example problem typical of those found in the chemical industry. In addition, we present data comparing two-exchange and simulated annealing heuristics with the exact algorithm for various problem sizes.
引用
收藏
页码:741 / 748
页数:8
相关论文
共 32 条
[1]  
Aarts E., 1989, SIMULATED ANNEALING
[2]  
Ashour S., 1970, AIIE T, V2, P172
[3]  
Baker K., 1974, INTRO SEQUENCING SCH
[4]  
DAS H, 1989, AICHE ANN M
[5]   SEQUENCING 2-MACHINE FLOW-SHOPS WITH FINITE INTERMEDIATE STORAGE [J].
DUTTA, SK ;
CUNNINGHAM, AA .
MANAGEMENT SCIENCE SERIES A-THEORY, 1975, 21 (09) :989-996
[6]  
Garey M.R., 1979, COMPUTERS INTRACTABI, V174
[7]  
Glover F., 1990, ORSA Journal on Computing, V2, P4, DOI [10.1287/ijoc.1.3.190, 10.1287/ijoc.2.1.4]
[8]  
Goldberg DE, 1989, GENETIC ALGORITHMS S
[9]  
Graham R. L., 1979, Discrete Optimisation, P287
[10]   OPTIMAL FLOWSHOP SCHEDULES WITH NO INTERMEDIATE STORAGE SPACE [J].
GUPTA, JND .
NAVAL RESEARCH LOGISTICS, 1976, 23 (02) :235-243