Scheduling Hybrid Flow Shop for Minimizing Total Weight Completion Time
Hybrid flow shop scheduling problems are quite common in process industries. In this paper we study the hybrid flow shop (HFS) problem with parallel identical machines at each stage. The objective is to minimize the total weighted completion times of the jobs. We formulate the problem as an integer programming formulation. Since the problem has proven to be NP-hard, an algorithm based on tabu search with specific neighborhoods is proposed. For hybrid flow shop scheduling problem, the schedule on the first stage have great influences on the result. Taking this character into consideration, in our algorithm each iteration consists of two steps, large scope search and deep search. The purpose in the first step is to search more extensively the neighborhood by modifying schedule of the first stage only, and in the second step the algorithm aims to intensify the search in a certain region where the schedule of the first stage is fixed. The algorithm is computationally compared with the lower bound provided by a Lagrangian relaxation algorithm. It is shown that the algorithm can perform well on test problems up to 50 jobs.
HFS tabu search
Cong Gao Lixin Tang
The Logistic Institute Northeastern University Shenyang, Liaoning, China
国际会议
2007 IEEE International Conference on Automation and Lofistics
山东济南
英文
2007-08-18（万方平台首次上网日期，不代表论文的发表时间）