eCite Digital Repository

Alternative solution representations for the job shop scheduling problem in ant colony optimisation


Montgomery, J, Alternative solution representations for the job shop scheduling problem in ant colony optimisation, Proceedings of the Third Australian Conference on Artificial Life (ACAL07), 4-6 December 2007, Gold Coast, Australia, pp. 1-12. ISBN 9783540769309 (2007) [Refereed Conference Paper]

PDF (Author's final draft (probably called post-print by some publishers))

Copyright Statement

Copyright 2007 Springer-Verlag Berlin Heidelberg

DOI: doi:10.1007/978-3-540-76931-6_1


Ant colony optimisation (ACO), a constructive metaheuristic inspired by the foraging behaviour of ants, has frequently been applied to shop scheduling problems such as the job shop, in which a collection of operations (grouped into jobs) must be scheduled for processing on different machines. In typical ACO applications solutions are generated by constructing a permutation of the operations, from which a deterministic algorithm can generate the actual schedule. An alternative approach is to assign each machine one of a number of alternative dispatching rules to determine its individual processing order. This representation creates a substantially smaller search space biased towards good solutions. A previous study compared the two alternatives applied to a complex real-world instance and found that the new approach produced better solutions more quickly than the original. This paper considers its application to a wider set of standard benchmark job shop instances. More detailed analysis of the resultant search space reveals that, while it focuses on a smaller region of good solutions, it also excludes the optimal solution. Nevertheless, comparison of the performance of ACO algorithms using the different solution representations shows that, using this solution space, ACO can find better solutions than with the typical representation. Hence, it may offer a promising alternative for quickly generating good solutions to seed a local search procedure which can take those solutions to optimality.

Item Details

Item Type:Refereed Conference Paper
Keywords:ant colony optimisation, job shop scheduling, solution representation
Research Division:Information and Computing Sciences
Research Group:Machine learning
Research Field:Neural networks
Objective Division:Expanding Knowledge
Objective Group:Expanding knowledge
Objective Field:Expanding knowledge in the information and computing sciences
UTAS Author:Montgomery, J (Dr James Montgomery)
ID Code:97245
Year Published:2007
Web of Science® Times Cited:6
Deposited By:Information and Communication Technology
Deposited On:2014-12-09
Last Modified:2016-01-19
Downloads:2 View Download Statistics

Repository Staff Only: item control page