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.
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:
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:
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:
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|
|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.