# "Squeaky Wheel" Optimization

David E. Joslin DAVID_JOSLIN@12.COM
i2 Technologies 909 E. Las Colinas Blvd.

Irving, TX 75039

## David P. Clements

CLEMENTS@CIRL.UOREGON.EDU
Computational Intelligence Research Laboratory 1269 University of Oregon Eugene, OR 97403-1269

## Abstract

We describe a general approach to optimization which we term "Squeaky Wheel" Optimization (swo). In swo, a greedy algorithm is used to construct a solution which is then analyzed to find the trouble spots, i.e., those elements, that, if improved, are likely to improve the objective function score. The results of the analysis are used to generate new priorities that determine the order in which the greedy algorithm constructs the next solution. This Construct/Analyze/Prioritize cycle continues until some limit is reached, or an acceptable solution is found.

SW O can be viewed as operating on two search spaces: solutions and prioritizations.

Successive solutions are only indirectly related, via the re-prioritization that results from analyzing the prior solution.  Similarly, successive prioritizations are generated by constructing and analyzing solutions. This "coupled search" has some interesting properties, which we discuss.

We report encouraging experimental results on two domains, scheduling problems that arise in fiber-optic cable manufacturing, and graph coloring problems. The fact that these domains are very different supports our claim that swo is a general technique for optimization.

## 1. Overview

We describe a general approach to optimization which we term   Squeaky Wheel"  Optimiza tion  SWO   Joslin    Clements The core of SWO is a Construct  Analyze  Prioritize cycle  illustrated in Figure    A solution is constructed by a greedy algorithm  making de cisions in an order determined by priorities assigned to the elements of the problem  That solution is then analyzed to find the elements of the problem that are   trouble makers "  The priorities of the trouble makers are then increased  causing the greedy constructor to deal with them sooner on the next iteration This cycle repeats until a termination condition occurs On each iteration the analyzer determines which elements of the problem are causing the most trouble in the current solution  and the prioritizer ensures that the constructor to gives more attention to those elements on the next iteration The squeaky wheel gets the grease " The construction analysis and prioritization are all in terms of the elements that ©1999 AI Access Foundation and Morgan Kaufmann Publishers. All rights reserved.