Application of ant colony optimization for no-wait flowshop scheduling problem to minimize the total completion time

摘要

Ant colony optimization (AGO) is a meta-heuristic proposed to derive approximate solutions for computationally hard problems by emulating the natural behaviors of ants. In the literature, several successful applications have been reported for graph-based optimization problems, such as vehicle routing problems and traveling salesman problems. In this paper, we propose an application of the AGO to a two-machine flowshop scheduling problem. In the flowshop, no intermediate storage is available between two machines and each operation demands a setup time on the machines. The problem seeks to compose a schedule that minimizes the total completion time. We first present a transformation of the scheduling problem into a graph-based model. An AGO algorithm is then developed with several specific features incorporated. A series of computational experiments is conducted by comparing our algorithm with previous heuristic algorithms. Numerical results evince that the AGO algorithm exhibits impressive performances with small error ratios. The results in the meantime demonstrate the success of ACO's applications to the scheduling problem of interest.