Solve the Problem

IBM ILOG Scheduler User's Manual > Advanced Concepts > Using Scheduler with Solver > Solve the Problem

Solve the Problem

The difference in this solution is that rather than using one of the predefined Concert Technology goals to implement search, we will implement our own goal to perform the search.

The following algorithm will be used: while some activity is unscheduled (that is, does not have a fixed start time), select the most urgent unscheduled activity (that is, the activity with the minimal latest start time) and schedule it as early as possible (that is, fix its start time to its earliest start time, as obtained with respect to the activities already scheduled).

We use an iterator (an instance of IlcActivityIterator) to step through the activities in the schedule. Scheduler guarantees the update, after each scheduling decision, of the earliest and latest start times of all the activities.

Note that the code of the goal and the activity selector are written using the Solver classes and the extracted Scheduler classes rather than Concert Technology classes. This is due to the fact that the goal and the activity selector are executed during the search for a solution which is controlled by the non-deterministic goal functionality of Solver. To make our activity selection, for example, we need the updated earliest start and latest end times of each activity given the current state of search. If we were to try to directly access these values from the IloActivity objects in the model, we would simply get the earliest start and latest end times from the model. These values are not updated during search, therefore we need to explicitly access the values from the IlcActivity objects.

IlcBool 
SelFirstActStartMax(IlcActivity& selection, const IlcScheduler& scheduler) 
{
 
  /* IF A NOT BOUNDED ACTIVITY EXISTS IN THE SCHEDULE, RETURN ILCTRUE 
     AND SET SELECTION AS THE ACTIVITY WITH THE MINIMAL LATEST START TIME. */
  IlcInt startmax = IlcIntMax;
  IlcBool selected = IlcFalse;
  for (IlcActivityIterator iterator(scheduler); 
       iterator.ok();
       ++iterator)
  {
    IlcActivity activity = *iterator;
    if (!activity.getStartVariable().isBound() 
        && (activity.getStartMax() <= startmax))
    {
      startmax = activity.getStartMax();
      selection = activity;
      selected = IlcTrue;
    }
  }
  return selected;
} 
 
ILCGOAL0(SolveIlc) {
  IloSolver solver = getSolver();
  IlcActivity chosenActivity;
  if (SelFirstActStartMax(chosenActivity, IlcScheduler(solver))) {
    chosenActivity.setStartTime(chosenActivity.getStartMin());
    return this;
  }
  else 
    return 0;
}
 
ILOCPGOALWRAPPER0(Solve, solver) {
  return SolveIlc(solver);
}

At each step in the problem solving, the activity selector SelFirstActStartMax is used to select an activity with the minimal possible latest start time (result of the activity.getStartMax() statement) among those activities which are still unscheduled (that is, for which the Boolean statement activity.getStartVariable().isBound() is false). The chosen activity is then scheduled at its earliest possible start time. This choice automatically and transparently triggers constraint propagation, which results in the update of the earliest and latest start times to be used in the next iteration.

The iterative process terminates when all the activities have been scheduled, that is, when the activity selector SelFirstActStartMax returns IlcFalse.

PREVIOUS NEXT