Abstract: The scheduling problem of hybrid flow shop with makespan as objective is discussed. In a hybrid flow shop, there are multiple machines at each stage and its scheduling problem is known to be NPhard. A new method is proposed in this paper. By the proposed method, for the first stage, the job sequencing is formulated as a traveling salesman problem and the ant colony method is used to solve it. For the following stages, dispatching rules, such as first come first served and first available machine first, are used to obtain an initial solution. Then, the initial solution is improved by identifying the bottleneck stage in taking the advantage of knowledge about job processing times and machine configurations. To evaluate the performance of the proposed algorithm, it is tested by using the Carlier and Nerons benchmark problems. It is shown that proposed method is effective and outperforms the wellknown NawazEnscoreHam (NEH) heuristic.

Key words: hybrid flow shop（HFS）, scheduling, ant colony system, dispatching rule