"Squeaky wheel" optimization

We describe a general approach to optimization which we term "Squeaky Wheel " Optimization (SWO). In SWO, a greedy algorithm is used to construct a sol ution which is then analyzed to find the trouble spots, i.e., those element s, that, if improved, are likely to improve the objective function score. T he results of the analysis are used to generate new priorities that determi ne the order in which the greedy algorithm constructs the next solution. Th is Construct/Analyze/Prioritize cycle continues until some limit is reached , or an acceptable solution is found. SWO can be viewed as operating on two search spaces: solutions and prioriti zations. Successive solutions are only indirectly related, via the re-prior itization that results from analyzing the prior solution. Similarly, succes sive 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 probl ems that arise in fiber-optic cable manufacturing, and graph coloring probl ems. The fact that these domains are very different supports our claim that SWO is a general technique for optimization.