Even though one of the assumptions leading to the need to solve multiple submodels was that we could not solve the overall problem as one model, the example problems we use are not quite that large and it is, indeed, possible to solve them as a single model. In order to provide some comparison of the computational effort that arises from such an effort, after solving the overall problem via incrementally solving submodels described above, we then solve the entire problem.

The smallest problem instances for this example is based on the 6X6 MT06 jobshop problem. The original problem we solve has 18 jobs of 6 activities each, to be scheduled on discrete resources of capacity 3. The final problem has 24 jobs of 6 activities each. The computation results (running on a Sun UltraSparc10[TM]) are shown in the following table.

We see that finding a solution with the whole problem, not surprisingly, achieves a lower makespan while completely changing the schedule. The incremental solves, however, have incorporated 6 new jobs, that is 36 new activities, while only perturbing the start times of 3 of the existing activities. Also, the results here indicate each job is scheduled in a mean time of 1.26 seconds.

The second problem instance is based on the 10x10, MT10 job shop problem. The original problem has 30 jobs of 10 activities each and the final problem has 40 jobs of 10 activities each. Our computation results are as follows.

These results indicate that resolving the entire problem can substantially decrease the makespan while, again, disturbing almost all of the original activities. The incremental solves have incorporated 10 new jobs (100 activities) while perturbing the start times of only 14 activities. Furthermore, the solve time is on average 2.34 seconds for each job.

Finally, the largest problem instance we look at here is based on the 20X5, MT20 job shop benchmark. The original problem solved contains 60 jobs each with 5 activities and the final problem contains 80 jobs with 5 activities each. Our results are shown in the following table.

Here we find that not only is the incremental solve able to find a solution with fewer changed activities than solving from scratch, but that the incremental solve finds a solution with a smaller makespan as well. Each job is incorporated with a mean solve time of 9.17 seconds.