move in solution space is downhill away from optimal  then the modified prioritization is discarded and the old prioritization is restored As is usual with local search ALS also sometimes makes random moves  in order to escape local minima ALS  and also List Scheduling  Pinson  Prins     Rullier are scheduling algorithms that deal with domains that include precedence constraints on tasks  Both accommodate precedence constraints by constructing schedules left to right temporally  A task cannot be placed in the schedule until all of its predecessors have been placed  In order for the analysis prioritization and construction to be appropriately coupled it is not sufficient to simply increase the priority of a task that is late  because the constructor may not be able to place that task until after a lot of other decisions have been made  Consequently some amount of blame must be propagated to the task s predecessors The commercial scheduler OPTIFLEX Syswerda uses a genetic algorithm approach to modify a sequence of tasks  and a constraint based schedule constructor that generates schedules from those sequences  op tiflex can also be viewed as an instance of SWO  with a genetic algorithm replacing analysis  In effect  the  analysis" instead emerges from the relative fitness of the members of the population Two graph coloring algorithms also bear some similarity to SWO  Impasse Class Col oration Neighborhood Search IMPASSE  Morgenstern Lewandowski Condon like SWO  maintains a target set of colors and produces only feasible colorings   Given a coloring IMPASSE places any nodes that are colored outside of the target set into an impasse set On each iteration a node is selected from the impasse set  using a noisy degree based heuristic and assigned a random color from the target set Any neighbor nodes that are now in conflict are moved to the impasse set like SWO  uses a sequence of nodes to Iterated Greedy IG   Culberson Luo create a new coloring on each iteration  and then uses that coloring to produce a new sequence for the next iteration The method used to generate each new sequence differs from SWO The key observation behind IG is that if all nodes with the same color in the current solution are grouped together in the next sequence  i e  adjacent to each other in the sequence then the next solution will be no worse than the current solution IG achieves improvement by manipulating the order in which the groups occur in the new sequence using several heuristics including random based on color  descending based on color  and ascending based on the cardinality of each group 1G learns groupings of nodes as it runs but it does not learn about about the difficulty of any nodes  A node s place in the sequence indicates nothing about its expected or detected difficulty

## 6.  Analysis And Future Work

This section summarizes several areas of future research suggested by the results reported in the previous sections

## 6.1 Scaling

While SWO uses fast  greedy algorithms for constructing solutions  and we have demon strated its effectiveness on problems of realistic size the greatest threat to the scalability of swo is that it constructs a new solution from scratch on each iteration A partial solution to this problem is seen in the use of a "history" mechanism for the graph coloring problems