Two-stage no-wait hybrid flow-shop scheduling with sequence-dependent setup times

摘要

In this paper, a two-stage no-wait hybrid flow-shop scheduling problem is investigated in which the sequence-dependent setup time at the first stage is considered. The NP-hardness of the problem is first proven. A lower bound based on the Hungarian method is proposed. A branch-and-bound approach, a tabu search and three heuristic methods are developed for the problem. Extensive computational experiments are conducted to evaluate the performance of these methods. The computational results show the efficiency of the proposed methods.