The initial problem is to schedule a set of jobs on a set of discrete resources so as to minimize the overall makespan. After this initial problem is solved, new jobs are added, one at a time, simulating the arrival of new orders in a factory. When each new job arrives, it is integrated into the existing schedule with the twin optimization criteria of minimizing the changes that must be made to the existing schedule while also minimizing the overall makespan.

An obvious approach to this problem would be to reschedule from scratch each time a new job is added. It would be possible to explicitly deal with the two optimization criteria by cleverly expressing the fact that the solution to the expanded problem should, as much as possible, retain the start times assigned in the existing schedule. To add a further level of verisimilitude, however, we further assume that due to time and memory limitations, we cannot solve a single monolithic model of the expanded scheduling problem. Rather, we must process the model of the expanded problem to create a number of inter-related sub-models with a fraction of the resources and activities in the whole problem. We can then solve each of these sub-models in sequence and combine the solutions into a solution to the whole problem.

It should be noted that the actual problem instances that we solve in this chapter are not really too big for the expanded model to be solved as a whole problem without sub-models. Indeed, as we will see, in order to compare the performance of the sub-model approach with the single model approach, at the end of the example we solve the final problem as a single model. The size of the problem instances reflects the desire to keep the example to a manageable size for the reader.

In real applications of IBM® ILOG® Scheduler, with hundreds of resources, thousands of activities, and tight time requirements, problem decomposition into sub-models is a very important and often-used technique. This chapter is designed to present an example of this technique so that users can then extend it to problem instances where it is necessary.