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

Ant colony optimization (ACO) 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 routin...

Full description

Saved in:
Bibliographic Details
Published in:Computers & industrial engineering 2004-11, Vol.47 (2), p.181-193
Main Authors: Shyu, S.J., Lin, B.M.T., Yin, P.Y.
Format: Article
Language:English
Subjects:
Algorithms
Ant colony optimization
Flowcharts
Heuristic
Job shops
Meta-heuristics
Optimization
Production
Production planning
Scheduling
Studies
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Ant colony optimization (ACO) 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 ACO 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 ACO 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 ACO 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.
ISSN:0360-8352
1879-0550
DOI:10.1016/j.cie.2004.06.006