A submodel shares some of the characteristics of the original problem. Therefore, we are able to use the same approach to search as was used to solve the original problem. The major difference in solving the submodel is the definition of the optimization criteria. Recall that we want to incorporate the new activity so as to minimize the makespan of the overall schedule, but also to minimize the changes from the original solution. This suggests that the optimization criteria for a submodel should be some combination of minimization of the makespan of the submodel (which will tend to reduce the makespan of the overall schedule) and of minimization of the number of activities whose start time is changed. Therefore, we define the optimization criteria as follows:

  optCriteria = IloNumVar(env, 0, IloIntMax, ILOINT);
  subModel.add(optCriteria == 1000 * maxEnd + IloSum(hasChanged));
  subModel.add(IloMinimize(env,  optCriteria));

In that code, maxEnd is an IloNumVar that is greater than or equal to the end times of all the activities in the submodel and hasChanged is an array of variables, one for each activity (except for the activity of the new job). A variable in the hasChanged array will be equal to 1 only if the activity to which it corresponds is not equal to its start time in the previous temporal model. Otherwise it will be equal to 0.

Note that the makespan is multiplied by 1000 in the optimization criteria. While this indicates that the makespan is more important than the number of changes, it should be noted that the definition of the model is constrained in such a way that the makespan for a submodel will never be less than it was before the new activity was added. This is because the activity start times in the previous iteration are used as lower bounds on the activity start times in the submodel and temporal model. In other words, even though the makespan is much more important in the optimization criteria, the submodel is constrained such that the start times of activities will not be changed simply to decrease the local makespan. Activity start times may be changed to incorporate the new activity, but they will not be changed otherwise.

The role of the texture-based heuristic should also be noted in the solving of the submodel. The texture measurements are built assuming that the activities will execute at their earliest start time. If such a start time assignment satisfies the resource constraints, then the search does nothing. Furthermore, because the earliest start times are based on an existing solution, we know that they are close to a solution. Incorporation of the new activity may therefore be as simple as assigning it to its earliest start time; all the other activities are likely to be consistent with each other. We cannot, of course, depend on this to be the case, especially in tightly constrained problems. However, in many cases the submodel can be solved to (local) optimality with no search whatsoever due to the combination of its highly constrained definition, the role of the optimization criteria, and the role of the texture based heuristics.