Production scheduling problems such as the job shop consist of a collection of operations (grouped into jobs) that must be scheduled for processing on different machines. Typical ant colony optimisation applications for these problems generate solutions by constructing a permutation of the operations, from which a deterministic algorithm can generate the actual schedule. This paper considers an alternative approach in which each machine is assigned a dispatching rule, which heuristically determines the order of operations on that machine. This representation creates a substantially smaller search space that likely contains good solutions. The performance of both approaches is compared on a real-world job shop scheduling problem in which processing times and job due dates are modelled with fuzzy sets. Results indicate that the new approach produces better solutions more quickly than the traditional approach.
History
Publication title
Proceedings of the Fifth International Workshop on Ant Colony Optimization and Swarm Intelligence (ANTS 2006)
Volume
4150
Editors
M Dorigo, LM Gambardella, M Birattari, A Martinoli, R Poli, T Stutzle
Pagination
484-491
ISBN
9783540384823
Department/School
School of Information and Communication Technology
Publisher
Springer-Verlag
Place of publication
Berlin
Event title
Fifth International Workshop on Ant Colony Optimization and Swarm Intelligence (ANTS 2006)
Event Venue
Brussels, Belgium
Date of Event (Start Date)
2006-09-04
Date of Event (End Date)
2006-09-07
Rights statement
Copyright 2006 Springer-Verlag Berlin Heidelberg
Repository Status
Open
Socio-economic Objectives
Expanding knowledge in the information and computing sciences