ots logo

Solutions  • Technology  • Clients  • Company  • Contact

Cable Manufacturing

OTS 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). 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.