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:
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 (, 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
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. ).