Squeaky Wheel Optimization
Squeaky wheel optimization is a nonsystematic search technique
for solving optimization problems. It is a metaheuristic (like tabu search
or simulated annealing) that can be applied to a wide range of problems.
It is particularly well suited to problems
with complex objective functions where high quality results are needed
quickly.
In squeaky wheel, a priority ordering of problem elements is given
to a greedy algorithm that constructs a solution. That solution
is then analyzed to find trouble spots. Trouble spots are those
elements that are not handled as well as they could be, relative to
some lower bound. The priority of the elements that are trouble spots
is then increased, and the new priority ordering
is given to the greedy constructor, with the likely result that those
elements will be handled better in the next solution.
Squeaky wheel finds high quality solutions quickly by performing search
in dual spaces -- the traditional solution space and the new priority space --
and by avoiding many of the problems that local search often encounters.
These features allow squeaky wheel to effectively make large coherent moves
to quickly move out of unpromising regions of the search space.
The construct-analyze-prioritize loop learns as it executes:
Problem elements that are hard to handle well tend to rise in the
priority queue, and elements that are easy to handle well tend
to sink.
CIRL
Squeaky wheel was developed at CIRL while working on a manufacturing scheduling
problem with a complex objective function. It was inspired by,
and can be viewed as a
generalization of, schedule packing (also known as doubleback optimization).
Unlike schedule packing, which is applicable only to certain types
of scheduling problems, squeaky wheel can be applied to a wide variety
of optimization problems. Thus far CIRL has implemented it in manufacturing
scheduling and graph coloring domains. Continuing and future work at CIRL
will focus on improving the core algorithm and on applying squeaky wheel to
new domains such as vehicle routing and generalized assignment problems.
Pointers
-
Squeaky Wheel Optimization.
- An article by David Joslin and Dave Clements describing squeaky wheel
and how it was applied to scheduling work in a fiber optic
cable assembly plant, and to a standard set of graph coloring problems.
Appeared in Journal of Artificial Intelligence Research, May 1999.
A
conference version of this material appeared in
Proc. AAAI in 1998.
Compressed postscript.
-
Heuristic Optimization: A Hybrid AI/OR Approach.
- This article describes how squeaky wheel, a nonsystematic AI method, was
combined with systematic Operations Research (OR) methods to produce
better solutions than either the AI or OR techniques did on their own.
This was joint work between CIRL and George Nemhauser, Markus Puttlitz,
and Martin Savelsbergh at Georgia Tech.
Presented at the Workshop on Industrial Constraint-Directed
Scheduling, held in conjunction with Constraint
Programming in 1997. Compressed postscript.
- Parent areas:
- Nonsystematic Search
- Implementation:
- Fiber optic cable assembly
Back to the CIRL Overview Page.