The problem presented in this chapter is to solve an initial scheduling problem and then to incorporate new jobs into the existing schedule. The constraints on this incorporation are that:

1) The makespan of the overall schedule should be as small as possible.

2) The changes from the original schedule should be as small as possible.

3) The computational resources taken to incorporate a new job are critical. We cannot attempt to solve the whole problem (original problem plus new jobs).

In order to achieve these goals, a significant effort is spent in forming a series of submodels, each of which contains only one resource from the original problem, a subset of activities, and one activity from the new job. Solving the subproblem makes use of a texture-based heuristic and an optimization criteria that tend to both minimize the makespan of the submodel and the number of changes from the original schedule. This heuristic is part of an incomplete, stochastic search whose goal is to find a good, but not optimal solution in a very short period of time.

Using a temporal model of the whole problem (which does not include any resources or resource constraints), the solution to each submodel is sequentially incorporated to ensure that a solution to the overall problem is found.