Squeaky Wheel Optimization (SWO)

Squeaky Wheel Optimization (SWO) is a nonsystematic search technique for solving a wide range of optimization 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 used to quickly construct a solution by allocating resources first to high-priority tasks. That solution is then analyzed to find trouble spots—those elements that are not handled as well as they could be if they had their pick of resources. The priority of the problem elements is then increased, and the new priority ordering is used to construct a new solution, with the likely result that those elements will be handled better.

Squeaky wheel finds good solutions quickly by searching for effective priority orderings, rather than searching directly from solution to solution. This lets it avoid many of the problems that traditional search techniques often encounter. This lets SWO make large coherent jumps 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.

SWO has been used to achieve the best results known for Aircraft Assembly and Fiber-optic Cable Manufacturing. It has also been employed in optimizing Aircraft Fleet Utilization. A generalized version of SWO has been used in generic Project Management Scheduling to minimize makespan and overload.

Aircraft Assembly

A well known aircraft manufacturer published a large scheduling problem available in order to encourage academic researchers to demonstrate the applicability of their techniques on realistic scheduling problems. This particular problem is relevant to large-scale assembly and is an instance of a class of problems known as resource constrained project scheduling (RCPS).

We developed a scheduler that produces the best results known on this problem. We extended this scheduler to handle more general aircraft manufacturing problems involving more complicated resource types and constraints. We have also converted several other benchmark problems to the same format and solved them successfully. The basic aircraft assembly problem has these features:

  • Zone Resources - A zone is an area of the aircraft in which work can be done. Zone resources specify the maximum number of people that can work in that zone at the same time.
  • Labor Resources - These specify how many laborers are available with a particular skill set.
  • Shifts - The availability of labor resources varies over time, with more being available during the day.
  • Tasks - Tasks have a specified duration and set of zone and labor resources that are needed to perform the task.
  • Precedences - These specify which tasks must be completed before other tasks can begin.
The program uses limited discrepancy search (LDS) and schedule packing (also known as doubleback optimization) to generate solutions. LDS and schedule packing can be used in isolation or in combination with each other. The best results are generally produced using LDS with schedule packing or schedule packing on its own. When used in combination, multiple seed schedules generated with LDS are fed to schedule packing.

In the figures below, the top part indicates resource usage over time. There is one horizontal bar for each of the 17 resources in this problem. Red indicates a resource is fully utilized, and green indicates it is unused. The boxes in the bottom part of the figures represent the tasks. The width of a box represents the duration of a task, and the height is an indicator of how many resources a task requires. A task's color indicates where the task starts in the PERT schedule for this problem. The alternating gray and black vertical bars in the background represent the day and night shifts.

Figure 1 shows the PERT schedule for the problem. In PERT schedules, precedences are honored, but resource constraints are not. Each blue rectangle in the top area of this solution indicates an overallocated resource for that period of time. This PERT schedule ends after 37 days, 2 hours and 58 minutes, and is a loose lower bound on the minimum length any solution to this problem can have.
The PERT Schedule
Fig.1: The PERT schedule for the problem.
Figure 2 shows a typical best solution that is found within the first 400 iterations of schedule packing. It ends after 40 days, 7 hours and 13 minutes. This schedule has no overallocated resources and all of the blue areas in the PERT schedule have disappeared. Also note that many of the tasks that were early in the PERT schedule (yellow tasks) have shifted over to much later in the schedule. These tasks are relatively unconstrained in their precedence relationships with other tasks.
Best Solution
Fig.2: A typical best solution.
Figure 3 shows a solution that we believe is optimal for this problem. This ends after 39 days, 5 hours and 5 minutes. Solutions of this length are produced by about 10% of schedule packing runs that are allowed to run for 200,000 iterations (which takes only a few minutes).
Optimal Solution
Fig.3: A solution that we believe is optimal for this problem.

On Time Systems has algorithms to solve a set of problems dealing with the scheduling of jobs in a multiple production line, fiber optic cable assembly plant. These problems are instances of job shop problems with added constraints. This domain features:

  • Multiple production lines with different speeds and capabilities. Each line can assemble one order at a time. A set of cables to schedule. Each cable has a strength member, number of fibers, length, sheathing material, and connectors. These attributes determine which subset of lines a cable can be made on. In addition, each cable has a release time (a hard constraint reflecting the availability of raw materials), and a deadline by which the cable should be finished (a soft constraint).
  • Setup costs. When a cable is completed it leaves that line in a particular state. Before the next cable is started, that line needs to be put in the state needed to assemble that line. Cables of identical or similar types tend to have low setup costs between them, while dissimilar cables have higher setup costs between them. Some transitions, while physically possible, are disallowed because they incur costs, such as powering the line down, that the manufacturer never wants to incur. These are modeled as infeasible setups.
  • An objective function that seeks to minimize setup costs and lateness.
Squeaky wheel optimization, a nonsystematic search technique, was originally developed at CIRL to solve these problems. In addition, CIRL has also worked on these problems in collaboration with an Operations Research group at Georgia Tech. That collaboration used squeaky wheel in combination with an LP/IP solver to produce solutions that were better than either squeaky wheel or the LP/IP solver produced in isolation.

These figures are taken from the squeaky wheel solver for these problems. They show a 297 cable problem, with 13 production lines (297 cables represents a week's production). Figure 1 shows a typical initial solution produced by the solver. The horizontal lines represent the 13 parallel production lines. Each box within a line represents a particular cable. Time runs from left to right and the left edge of each box is when work on that cable is started, and the right edge is when work on that cable finishes. Cables are not lined up along the left side because most cables have release times that occur after the start of the scheduling window. The color of each box is an indication of how well that cable is handled in this solution, relative to some lower bound for each cable. Dark green is best, red is worst.
Typical Initial Solution
Fig.1: A typical initial solution.
The large red boxes indicate cables that cause infeasible setups, and solutions with such boxes in them are not implementable. It is worth noting that the LP/IP solver and a Tabu solver were never able to produce a feasible solution for this problem, although they were able to produce feasible solutions for most of the smaller problems.

Figure 2 figure shows a feasible solution that was produced after 32 seconds (on a SparcStation 10) on the 16th iteration of squeaky wheel. The general color of this solution is greener then the first one, reflecting better setup costs and fewer late cables. This solution is within 2.5 percent of the best solution ever produced for this problem.
Feasible Solution
Fig.2: A feasible SWO solution.
Figure 3 shows the movement of 3 cables through the squeaky wheel priority queue over consecutive iterations of the solver. The solver starts with an initial ordering based on the number of lines each cable can run on (each cable can be assembled on from 1 to 9 of the lines). As the solver produces successive solutions it learns which of the cables are actually harder than others. The color inside each box indicates how well a cable was handled on that iteration. Two of the three cables are mostly dark green, indicating that they were handled optimally or near optimally on most iterations. These cables decrease in priority as the solver runs. The remaining cable is harder to schedule well and its priority tends to rise over time.
Optimal Solution
Fig.3: An Optimal SWO Solution.

The GLOBE (Global Logistics Optimization to Boost Effectiveness) system was developed in collaboration with BBN Technologies and C5T for the the U.S. Air Force's Air Force Research Laboratory and Air Mobility Command. Based partly on On Time Systems' Distributed Worldwide Aeronautical Route Planner (DWARP) and BBN's WIDE Timeline Tool, the GLOBE system manages schedule disruptions and new requirements across the entire mobility air fleet.

GLOBE combines cross-mission, multi-constraint optimization, advanced work-centered interface design, and new work in multiple solution optimization, to comprehensibly present users with a variety of operationally distinct alternative solutions. Users can easily focus in on key differences between candidate solutions and understand the repercussions of different strategic choices in responding to new requirements or disruptions. Empirical studies with USAF users using real data have shown that GLOBE results in:

  • Improved Situational Awareness
  • Faster Response Time
  • Decreased Cognitive Load
  • Better Solutions
than existing approaches.

The optimizer takes into account the limited availability of resources such as airspace clearances, aircraft parking space, and time, along with constraints on things such as crew-duty-day length and airport operating hours to develop a minimum-disruption/minimum-cost/maximum-value overall assignment of resources. GLOBE identifies operationally distinct solutions — solutions that differ meaningfully on operationally important dimensions—maintains a set candidate best distinct solutions during search. Effective presentation distinct solutions allow users to comprehend the effects of alternate courses of action and quickly choose the solution that best meets their goals.
Comparison of Multiple Distinct Options
Comparison of Multiple Distinct Options.

Existing project management systems include functionality to produce schedules (called leveling or scheduling). OTS has developed algorithms that use squeaky wheel optimization to outperform this existing functionality. The following table shows typical results obtained by comparing OTS algorithms with the Primavera leveler for actual projects from the construction industry.

Improvement Over Primavera Leveler
Approximate Number of Activities Project Duration Resource Overload
Municipal Utility 2700 14% 32%
Residential Home Construction 12300 30% 0%
Manufacturing Facility 33000 13% 0% *
Oil Refinery Facility Maintenance 12200 15% 74%

* the initial schedule had no overload

The following snapshot shows schedule optimization in PSOP for an aircraft assembly problem. The Primavera-leveled schedule is on top and the PSOP schedule on the bottom. Overload is shown in red. The PSOP schedule eliminates all (100%) of the overload and is approximately 30% shorter as well.

PSOP Schedule