 |
Machine
Scheduling with Ant Colony Optimisation
Ant Colony Optimisation (ACO) is a relatively new nature-inspired
meta-heuristic for solving combinatorial optimisation problems.
It is a highly parallel multi-agent method that is - as the name
suggests - inspired by the behaviour of real ants, in particular
by foraging activities.
The original ACO algorithm was first applied to the well-known traveling
salesman problem, as the structure of this problem is closest to
the biological inspiration of foraging and nest building ants. Generalizations
to other problems, such as the quadratic assignment problem soon
followed, and today ACO (often hybridised with local search or other
methods) is among the most promising meta heuristics for many industrially
relevant problems.
We investigate ACO for machine scheduling, ie. for the problem of
finding a sequence assignment of tasks to machines in a manufacturing
process such that the production process is optimal in regard to
production time, tardiness and other factors that influence the
overall production cost. This problem is in principle closely related
to the asymmetric traveling salesman problem, but vastly more complex
in real-world settings.
Our particular interest is the applicability of adaptive ant-colony
methods in a dynamically changing production environment.
Core Reference
“Inspiration for optimization from social insect behaviour”
by E. Bonabeau, M. Dorigo and G. Theraulaz
in Nature 406, 39 - 42 (2000)
Student
Lam Phuong Lam
Supervisor
Bernd
Meyer, Andreas Ernst (CSIRO)
Type
Bachelor Computer Science (Honours)
Project Start
February 2002
Completion
November 2002
In cooperation with
CSIRO |
|
|
Click
to print
