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

Author(s)

Montgomery, James

Available versions

Abstract

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.

Publication year

2007

Publication type

Conference paper

Source

Lecture Notes in Computer Science: Progress in Artificial Life: Third Australian Conference on Artificial Life (ACAL07), Gold Coast, Queensland, Australia, 04-06 December 2007, Vol. 4828, pp. 1-12

Publisher

Springer

ISBN

9783540769309

Copyright

Copyright © 2007 Springer-Verlag Berlin Heidelberg 2007. The accepted manuscript is reproduced in accordance with the copyright policy of the publisher. The original publication is available at www.springerlink.com.

Details