We have six sets of test data, ranging in size from 40 to 297 tasks, all with 13 parallel production lines. The largest problem was the largest that the manufacturer required in practice. We compare the following solution methods:
On the 297 task problem, SWO was far more effective than either TABU or IP. TABU, for example, failed to find a feasible schedule after running for over 24 hours. On the smallest problems, TABU and IP were able to find solutions, but SWO outperformed both by a substantial margin. Table 1 presents results on each problem for SWO, TABU and IP. For SWO, ten trials were run and the results averaged. The TABU and IP implementations were deterministic, so only the results of a single run are shown. The second column of the table shows the best objective function value we have ever observed on each problem. The remaining columns show the objective function value and running times for SWO, TABU and IP. All but the IP experiments were run on a Sun Sparcstation 10 Model 50. The IP experiments were run on an IBM RS6000 Model 590 (a faster machine).
The best values observed have been the result of combining SWO with IP, as reported in [Clements, Crawford, Joslin, Nemhauser, Puttlitz, SavelsberghClements et al.1997]. In that work, SWO generated solutions, running until it had produced a number of ``good'' schedules. An IP solver was then invoked to re-combine elements of those solutions into a better solution. Although the improvements achieved by the IP solver were relatively small, on the order of 1.5%, it achieved this improvement quickly, and SWO was unable to achieve the same degree of optimization even when given substantially more time. While noting that the hybrid approach can be more effective than SWO alone, and much more effective than IP alone, here we focus on the performance of the individual techniques.
We also note that our very first, fairly naive implementation of SWO for these scheduling problems already outperformed both TABU and IP. Moreover, our improved implementation, reported above, is still fairly simple, and is successful without relying on domain-dependent heuristics. We take this as evidence that the effectiveness of our approach is not due to cleverness in the construction, analysis and prioritization techniques, but due to the effectiveness of the SWO cycle at identifying and responding to whatever elements of the problem happen to be causing difficulty in the local region of the search.
It is also instructive to compare the results of a good heuristic ordering, with the sequence derived by SWO. A good heuristic for this scheduling domain (and the one that is used to initially populate the priority sequence) is to sort the tasks by the number of production lines on which a task could be feasibly assigned in an empty schedule. A task that can be scheduled on many lines is likely to be easier to schedule than one that is compatible with only a small number of lines, and should therefore be expected to need a lower priority. The top graph in Figure 5 shows the sequence of tasks, as determined by this heuristic. The lower graph illustrates the changes in priority of these tasks, after SWO has run for fourteen iterations (enough to improve the solution derived from the sequence to within 0.05 percent of the best known solution).
As the figure illustrates, the heuristic is generally accurate, but SWO has had to move some tasks that are compatible with most of the production lines to positions of relatively high priority, reflecting the fact that contrary to the heuristic, these tasks turned out to be relatively difficult to schedule well. Other tasks that are compatible with only a few production lines are actually easy to schedule well, and have moved to relatively low priorities.
