Using a randomized strategy does not mean that everything ought to be done randomly. Indeed, the goal that is pursued at each iteration is still to compute a solution to the scheduling problem with a makespan less than the best makespan found so far. Constraint propagation helps in this process as it identifies activities that cannot be first to execute on the corresponding resource. The basic structure of an algorithm aimed at finding a new solution is consequently very similar to the basic structure of the preceding algorithms.

What is going to differ most is the heuristic we use to select which activity to schedule first. In the context of the preceding algorithms, it was very important to avoid bad decisions about that point. This pressure lead us to schedule the most critical resource first. However, avoiding bad decisions is not that important here, so two other heuristics appear useful:

The following function, SelectResourceConstraint, integrates these two heuristics.

IlcInt
GetEndMin(IlcSchedule& schedule)
{
  /* COMPUTE THE SMALLEST MINIMAL END TIME OF UNRANKED ACTIVITIES. */
  IlcInt endMin = schedule.getTimeMax() + 1;
  for(IlcUnaryResourceIterator resIte(schedule);
      resIte.ok();
      ++resIte) {
    for (IlcResourceConstraintIterator ite(*resIte,
                                           IlcFromStartToEnd);
         ite.ok(); ++ite) {
      IlcResourceConstraint constraint = *ite;
      if ((constraint.isPossibleFirst())
          && (constraint.getActivity().getEndMin() < endMin))
        endMin = constraint.getActivity().getEndMin();
    }
  }
  return endMin;
}
 
IlcBool
SelectResourceConstraint(IlcResourceConstraint& constraint,
                         IlcSchedule& schedule,
                         IloRandom rand)
{
  IlcInt endMin = GetEndMin(schedule);
  if (schedule.getTimeMax() < endMin)
    return IlcFalse;
  IlcInt chosenNumberOfCandidates = schedule.getNumberOfActivities() +
    1;
  for(IlcUnaryResourceIterator resIte(schedule);
      resIte.ok();
      ++resIte) {
    IlcResourceConstraint bestConstraint;
    IloNum bestValue = -1.0;
    IlcInt numberOfCandidates = 0;
    for (IlcResourceConstraintIterator ite(*resIte,
                                           IlcFromStartToEnd);
         ite.ok(); ++ite) {
      IlcResourceConstraint ct = *ite;
      if (ct.isPossibleFirst()
          && (ct.getActivity().getStartMin() < endMin)) {
        numberOfCandidates++;
        IloNum value = rand.getFloat();
        if (bestValue < value) {
          bestConstraint = ct;
          bestValue = value;
        }
      }
    }
    if ((0 < numberOfCandidates)
        && (numberOfCandidates < chosenNumberOfCandidates)) {
      /* resource IS THE RESOURCE WITH THE SMALLEST NUMBER OF
         CANDIDATES. THE CHOSEN CONSTRAINT BECOMES THE BEST CONSTRAINT
         OF resource. */
      chosenNumberOfCandidates = numberOfCandidates;
      constraint = bestConstraint;
    }
  }
  return IlcTrue;
}
   

The function SelectResourceConstraint selects the resource constraint that corresponds to the chosen activity. The function returns IlcTrue if it succeeded in selecting a resource constraint, and IlcFalse otherwise.