Abstract:

The scheduling problem of a multi-stage hybrid flow shop (HFS) with single processing machines and batch processing machines is addressed. Aiming at minimization of the maximum completion time, a time window-based ant colony optimization (TWACO) approach is proposed, which achieves cooperative optimization for part assignment, part sequencing, and batch formation simultaneously. Besides, to obtain higher utilization rate for the batch processing machines, a time window is dynamically constructed by a look-ahead algorithm during batch formation. The computational results show that by the adoption of the look-ahead algorithm, TWACO maintains a good balance between the utilization rate of the batch processing machines and the solution quality; and TWACO has significant advantages over CPLEX in minimizing the maximum completion time while retaining low computational costs. Therefore, TWACO is much more suitable for the problem of a multi-stage HFS.

Key words: ant colony optimization, batch processing machine, single processing machine, time window, hybrid flow shop