Please use this identifier to cite or link to this item: http://hdl.handle.net/1959.3/26092

Download PDF (Author's final draft) (Adobe Acrobat PDF, -1 bytes)

Title

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

Author(s)

Montgomery, James

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 type

Conference paper

Research centre

Swinburne University of Technology. Faculty of Information and Communication Technologies. Centre for Information Technology Research

Source

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

Publication year

2007

Keyword(s)

ACO;  Ant colony optimisation;  Job shop scheduling;  Solution representation

Publisher

Springer

ISBN

9783540769309

Publisher URL

http://dx.doi.org/10.1007/978-3-540-76931-6_1

Copyright

Copyright © Springer-Verlag Berlin Heidelberg 2007. The author's final draft of this paper is reproduced here in accordance with the copyright policy of the publisher. The original publication is available at www.springerlink.com.

Full text

Peer reviewed