Creating the Submodels

IBM ILOG Scheduler User's Manual > Integrated Applications > Incremental Scheduling: Using Scheduler with Multiple Problem Sub-models > Designing the Models > Creating the Submodels

Creating the Submodels

INDEX

PREVIOUS NEXT

Given the solution to the temporal model, we now create a series of submodels each of which contain one resource and the activities that require that resource within a specific time window. The process is as follows:

Using the temporal solution, identify a submodel for the ith activity in the new job. (Initially i = 1.)
Solve the submodel. If we cannot find a solution, stop trying to incorporate this job and return the default solution.
Add a subset of the constraints found in solving the submodel to the temporal model.
Solve the temporal model.
Return to step 1 until all activities in the new job are scheduled.

We schedule the activities in the new job in chronological order, starting with a submodel that contains the first activity in the new job, then moving to a second submodel that contains the second activity, and so on.

Identifying a Submodel

To identify the first submodel, we examine the first activity in the new job and in particular, we use its earliest start time and latest end time as defined by the solution to the temporal model. This activity and its time window are added to the submodel.

  IloActivity newAct = newRC.getActivity();
  IloDiscreteResource reschedRes = newRC.getResource();

  // GET THE TIME BOUNDS OF THE TO-BE-ADDED ACTIVITY
  IloNum minTime = temporalSolution.getStartMin(newAct);
  IloNum maxTime = temporalSolution.getEndMax(newAct);

  env.out() << "Resource " << reschedRes.getName() 
	    << " on interval: [" << minTime << ".." << maxTime << "]"
	    << endl;

  // ADD THE NEW TIME BOUNDS AND RESOURCE CONSTRAINT
  subModel.add(newAct.startsAfter(minTime));
  subModel.add(newAct.endsBefore(maxTime));
  subModel.add(newRC);
  subSolution.add(newAct);
  env.out() << "Adding " << newAct.getName() << endl;

We then iterate over all the resource constraints and identify those which both require the same resource as the new activity and have a time window completely within the time window of the new activity. These activities are also added to the submodel and constrained to execute between their earliest start time and latest end time as defined by the temporal model. They are also constrained to end before the variable representing the maximum end time for all activities in the submodel.

We do not add to the submodel those activities whose time window partially overlaps the time window of the new activity. Instead, we specify that the initial occupation of the resource in the submodel includes the resource capacity used by these activities. This ensures that a solution to the submodel will respect the resource reservations of those activities that are not in the submodel. This use of the initial occupation of a resource is similar in spirit to that which is done with durable resources (see Scheduling with Durable Resources).

It is important to understand the contents of a submodel. It contains:

One activity from the new job.
The resource required by that new activity.
All the other activities that execute on this resource fully within the time window fully of the new activity.
The resource occupation of all those activities on this resource that partially overlap the time window of the new activity.

The contents of the submodel can, perhaps, be better understood with Figure 37.1 , Adding Activities Between EST and LFT. The figure demonstrates that we have one activity from the new job. The earliest start time (est) and the latest finish time (lft) of the new activity are the temporal boundaries of the submodel. All existing activities whose time window is wholly within the temporal boundaries are added to the model. Those activities that overlap the temporal boundary are added as initial occupation on the resource.

Figure 37.1 Adding Activities Between EST and LFT

As shown in Solving the Submodels, we limit the search that is done in solving each submodel. We are not, therefore, guaranteed that we will find a solution to each submodel. If we fail to find a solution to any submodel within the resource limits, we abandon the attempt to intelligently schedule the new job and simply incorporate it using the default solution: the activities of the new job are simply placed as the last activity on each resource. We hope, obviously, that we will not have to do this, as the default solution is not of high quality. However, the ability to respond to time limitations is critical in many applications and in many cases more critical than finding the optimal solution.

Incorporating the Submodel Solution into the Temporal Model

If the submodel is solved, we incorporate the solution into the temporal model by adding the minimum start time found for each activity in the submodel solution as the actual start time in the temporal model.

  for(IloSchedulerSolution::ActivityIterator iter(subSolution); 
      iter.ok(); ++iter) {
    IloActivity act = *iter;
    tModel.add(act.startsAt(subSolution.getStartMin(act)));
  }

  if (!tSolver.solve(IloGoalTrue(tSolver.getEnv())
  		     , IloSynchronizeAndContinue
		     )
      )
    throw IloSchedulerException( "No solution for temporal model" );
  IlcScheduler scheduler(tSolver);
  tSolution.store(scheduler);

Solving the temporal model again (with the new constraints) results in a set of time windows for the non-assigned activities. We can then create the next submodel with the next activity in the new job.

This loop of creating and solving a submodel followed by adding the submodel solution to the temporal model, and then creating and solving the next submodel continues until all the activities in the new job are scheduled.

At that point, the solution to the temporal model is also a solution to the current evolving model. We therefore update the evolving solution by copying the temporal solution and return to await the arrival of the next job.

PREVIOUS NEXT