A review of traveling salesman problem based approaches for flowshop scheduling

A review of traveling salesman problem based approaches for flowshop scheduling

0.00 Avg rating0 Votes
Article ID: iaor2007152
Country: Netherlands
Volume: 169
Issue: 3
Start Page Number: 816
End Page Number: 854
Publication Date: Mar 2006
Journal: European Journal of Operational Research
Authors: , ,
Keywords: computational analysis, programming: travelling salesman
Abstract:

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.

Reviews

Required fields are marked *. Your email address will not be published.