in response to  trouble spots" found in the current solution  The resulting move may be uphill but the move is always motivated by those trouble spots In priority space the only   local optima" are those in which all elements of a solution are assigned equal blame SWO tends to avoid getting trapped in local optima because analysis and prioritization will always  in practice  suggest changes in the sequence  thus changing the solution generated on the next iteration This does not guarantee that SWO will not become trapped in a small cycle however In our implementations we have introduced small amounts of randomness in the basic cycle  We also restart SWO periodically with a nw initial sequence Another aspect of local search is that typically each point in the solution space is as ssession and to the control about hillclimbing  we generally refer to the  terrain" described by this objective function score over the space of solutions The process of analysis in SWO can be thought of as synthesizing a more complex description of that terrain by breaking a solution down into its component elements and assigning a score to each  Prioritization then translates the analysis into a strategy" that the constructor can use to generate the next solution Assigning scores to the individual elements of a solution allows swo to take advantage of the fact that real problems often combine some elements that are difficult to get right plus others that are easy In the scheduling problems presented below  some tasks can be assigned to just a few production lines  while others allow for much more flexibility  Some have due dates close to their release time  while others have a lot of leeway  It is sometimes possible to identify  difficult" elements of a problem with static analysis  but interactions can be complex  and elements that are causing difficulty in one part of the search space may be no trouble at all in another Rather than trying to identify elements that are globally difficult by analyzing the entire problem SWO analyzes individual solutions in order to find elements that are locally difficult  Globally difficult elements tend to be identified over time as they are difficult across large parts of the search space By assigning blame and adjusting priorities based on identified problems in actual so lutions SWO avoids dependence on complex domain dependent heuristics It is our belief that this independence is particularly important in complex domains where even the best heuristics will miss some key interactions and therefore inhibit the search from exploring good areas that the heuristic incorrectly labels as unpromising SWO uses actual solutions to discover which areas of the search space are promising and which are not

## 3. Swo For Scheduling

This section describes an application of swo to a fiber optic production line scheduling problem  derived from data  provided by  Lucent Technologies   In this particular plant  a to cable may be assembled on any one of parallel production lines  For each cable type only a subset of the production lines are compatible  and the time required to produce the cable will depend on which of the compatible lines is selected Each cable also has a setup time  which depends on its own cable type and that of its predecessor  Setups between certain pairs of cable types are infeasible Task preemption is not allowed ie once a cable has started processing on a line  it finishes without interruption