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.