next up previous
Next: Conclusion and Future Up: A comparison between Operations Previous: WIZARD: A knowledge-based

Using OR-data as benchmarks

Despite the limitations of models from Operations Research stated above, there are at least two achievements which can be very useful in the development of knowledge-based scheduling tools:

  1. Dispatch or priority rules ``do not guarantee finding an optimal solution, but instead aim at finding reasonably good solutions in a relatively short time'' ([15], p. 142). They can be used in steps 1. and 4. of the basic algorithm whenever explicit knowledge of human planners is not available; this can be compared to one of the knowledge types in OPAL ([5]).

  2. In the literature several standardized problem instances are described (cf. [9], [1], and [2]). Although they are somewhat simplified in comparison with real life problems they can serve as benchmark data to compare the performance and quality of scheduling systems.

Typical OR-problem instances normally consist of n jobs with m operations (often called tasks) each of which occupies exactly one of m resources for a certain amount of time. The optimal solution as cited in the literature is the minimum amount of time-slices between the start of the first operation and the end of the last one.

WIZARD could be adapted to these structures in a very straightforward way. Instead of various resources per operation there is exactly one machine. The processing time given is used for calculating the possible start of the successor both within the job as well as on the machine. A very simple time model was instantiated with one continuous shift without any interruptions. The functions to propose the next operation to be scheduled and to propose a valid starting time in steps 1. and 2. of our basic algorithm were not changed; the best results were obtained by processing the operations in the sequence within their orders which can be compared to the earliest due date EDD priority rule ([15], p. 35). Additional constraints were defined to tie the operations as tightly together as possible in order to minimize the overall length of a schedule.

With these alterations we examined WIZARD's performance applied to some OR-problem instances which were chosen rather arbitrarily. Short descriptions of the instances and the results as stated in the literature and obtained by WIZARD are shown in Table 1. It contains two more measures showing the quality of the resulting schedule with regard to the resource utilization and the jobs' idle times.

  
Table 1: Results of OR-Benchmarks

Annotations:

Col. Size:
In a problem instance of size of n x m there are n jobs with m tasks each of which occupies exactly one of m resources.
Col. Result
= difference between the start of the first operation and the end of the last
Col. Dev.
= difference between optimal solution as known from the literature (cf. col. Opt.) and solution as found by WIZARD (cf. col. Result)
Col. RJD
= relative job delaytime: relation between lead time and processing time of job
Col. RRU
= relative resource utilization: relation between occupancy and capacity of a resource; the capacity is measured as the difference between the start of the first and the end of the last operation occupying the resource.
Col. Runtime
= time WIZARD needed to complete the task, measured on an Apple PowerMacintosh 9500/150 with 40 MB memory.

The instances abz5, abz6, ft06, ft10, ft20, la01, la02, la03, and la04 are small examples with up to 100 operations. WIZARD's solutions range from 9% deviation from the optimal value up to 38%. In medium sized examples such as abz7, la31, and la36 WIZARD's results are between 6% and 30% worse than the optimal solution. They can be found in some 12 seconds of runtime on a desktop computer of average speed.

The instances swv11--18 show interesting results. On examples considered easy like swv16, swv17, and swv18 WIZARD performs quite well with deviations of 0% to 5% while the hard problems swv11, swv12, and swv15 show values which are up to 73% worse. The relative resource utilizations of more than 95% show that in the time horizon where a machine is actually needed it is planned very closely. Yet the high values of relative job delay, i.e. the idle time's portion of the complete lead time, show that the jobs are processed in far too slack a way. The solutions to these problems are found in some 22 to 24 seconds.

WIZARD's performance on instances tail-5181, tail-5183, and tail-5552 which are rather similar in size to real world problems is quite satisfying. Here the main advantage of our any-time-algorithm shows clearly: Solutions only 14% worse than the optimal value are found in less than two minutes. Their relative resource utilization values can be compared to those which can be observed in reality, but here once more the job delays are too high though quite normal in many production enterprises (cf. [14]).



next up previous
Next: Conclusion and Future Up: A comparison between Operations Previous: WIZARD: A knowledge-based

Christian Hestermann
Fri Dec 6 16:28:54 MET 1996