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. The first figure is 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.
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.
The next 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.
The last figure 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.
