Journal
INTERNATIONAL JOURNAL OF PRODUCTION RESEARCH
Volume 48, Issue 4, Pages 1143-1154Publisher
TAYLOR & FRANCIS LTD
DOI: 10.1080/00207540802538021
Keywords
job-shop scheduling; ant colony optimisation; disjunctive graph; makespan; NP-hard
Ask authors/readers for more resources
The job-shop scheduling problem (JSSP) is known to be NP-hard. Due to its complexity, many metaheuristic algorithm approaches have arisen. Ant colony metaheuristic algorithm, lately proposed, has successful application to various combinatorial optimisation problems. In this study, an ant colony optimisation algorithm with parameterised search space is developed for JSSP with an objective of minimising makespan. The problem is modelled as a disjunctive graph where arcs connect only pairs of operations related rather than all operations are connected in pairs to mitigate the increase of the spatial complexity. The proposed algorithm is compared with a multiple colony ant algorithm using 20 benchmark problems. The results show that the proposed algorithm is very accurate by generating 12 optimal solutions out of 20 benchmark problems, and mean relative errors of the proposed and the multiple colony ant algorithms to the optimal solutions are 0.93% and 1.24%, respectively.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available