The objective of the function SetMakespanInitialBounds is to find a smaller initial domain for the makespan variable.

The lower bound is easily computed by propagating the constraints of the problem, without executing any search goal. The makespan lower bound is then set with the Concert Technology function IloNumVar::setLb.

Finding a good value for the upper bound is more complex. We need to implement a goal, SolveConflicts, that generates a good first solution. This goal is executed and the makespan of the solution is taken as upper bound for the domain of the optimal makespan variable.

Here is the corresponding code.

void
SetMakespanInitialBounds(IloSolver& solver, 
                         IloNumVar& makespan)
{
  IloGoal goal;
  /* SET MAKESPAN LOWER BOUND AND RESTART */
  goal = IloGoalTrue(solver.getEnv());
  solver.solve(goal);
  makespan.setLB(solver.getMin(makespan));
 
  /* SOLVE WITH GOAL SOLVECONFLICTS */
  goal = SolveConflicts(solver.getEnv());
  solver.solve(goal);
 
  /* SET MAKESPAN UPPER BOUND */
  makespan.setUB(solver.getMin(makespan));
  solver.out() << "Solution with makespan " << makespan.getUB() << endl;
}
 

Now, let's look in detail at the goal SolveConflicts.

Now, the critical point of the goal is the selection of the pair of resource constraints (srct1,srct2). This selection is done by the function SelectMostOpportunisticConflict.

 
ILCGOAL0(SolveConflictsIlc) {
  IloSolver s = getSolver();
  IlcScheduler scheduler = IlcScheduler(s);
 
  IlcResourceConstraint srct1;
  IlcResourceConstraint srct2;
  if (SelectMostOpportunisticConflict(scheduler, srct1, srct2))
    return IlcAnd(IlcTrySetSuccessor(srct1, srct2), this);
 
  return 0;
}
 
ILOCPGOALWRAPPER0(SolveConflicts, solver) {
  return SolveConflictsIlc(solver);
}
 

If {srct1,srct2} is a pair of unranked resource constraints, we define a criterion impact(srct1, srct2) that approximates the impact on the schedule of the decision of ordering srct1 before srct2. The impact of a decision on the schedule is a quantity that is proportional to the domain reduction of the start and end variables of activities due to the propagation of the decision.

Suppose that act1 and act2 are the activities of srct1 and srct2, and that:

When adding the precedence relation srct1 < srct2:

If a choice exists between ordering srct1 before srct2 or srct2 before srct1, we will always choose the order of minimal impact. Indeed, in such a way the domain reduction for the start and end variables of activities will be smaller. Therefore:

In all the solutions, all the pairs {srct1,srct2} will have to be ranked. As our goal is to minimize the impact of all the decisions taken until a solution is found, a good strategy is to select in priority those potential conflicts {srct1, srct2} for which the choice of the decision between srct1.setSuccessor(srct2) and srct2.setSuccessor(srct1) is the most evident; that is, the potential conflicts that maximize IlcAbs(impact(srct1,srct2) - impact(srct2,srct1)).

Suppose we have two pairs of unranked resource constraints {srctA,srctB} and {srctC,srctD} such that:

impact(srctA,srctB) = 10, impact(srctB,srctA) = 10; and
impact(srctC,srctD) = 20, impact(srctD,srctC) = 100

This means that we would first select the pair {srctC,srctD} and choose the decision srctC.setSuccessor(srctD). After this decision has been propagated, it may be that it will be easier to choose between srctA.setSuccessor(srctB) and srctB.setSuccessor(srctA).

Until this point, our criterion to select a potential conflict has been very local. A way to improve this is to prefer the potential conflicts that belong to a part of the schedule where there are still a lot of unresolved potential conflicts. This strategy has a double advantage.

The criterion used to estimate the potential conflict around a pair (srct1, srct2) is the minimum between the number of resource constraints that are unranked with respect to srct1 (nbUnranked(srct1)), and the number of resource constraints that are unranked with respect to srct2 (nbUnranked(srct2)).

Therefore the criterion:

IlcMin(nbUnranked(srct1), nbUnranked(srct2)) * 
IlcAbs(impact(srct1,srct2) - impact(srct2,srct1)) 

is used as a measure of the opportunity of the potential conflict {srct1,srct2}.

The corresponding code follows. Note that a class NbUnrankedExt is attached as an object to the resource constraints in order to avoid the recomputation of the number of unranked resource constraints for each potential conflict {srct1, srct2}.

class NbUnrankedExt {
private:
  IlcInt _nbOfUnranked;
 
public:
  NbUnrankedExt() :_nbOfUnranked(0) {};
  ~NbUnrankedExt(){};
  void setValue(IlcInt nbOfUnranked) {
    _nbOfUnranked = nbOfUnranked;
  }
  IlcInt getValue() const {
    return _nbOfUnranked;
  }
};
 
IlcInt GetNumberOfUnranked(const IlcResourceConstraint& rct) {
  /* RETURN NUMBER OF UNRANKED W.R.T. RCT */
  IlcInt nb = 0;
  for (IlcResourceConstraintIterator ite(rct, IlcUnranked);
       ite.ok(); ++ite)
    nb++;
  return nb;
}
 
IlcInt GetOpportunity(const IlcScheduler& scheduler,
                      const IlcResourceConstraint& srct1,
                      const IlcResourceConstraint& srct2) {
 
  IlcActivity act1 = srct1.getActivity();
  IlcActivity act2 = srct2.getActivity();
 
  IlcInt smin1 = act1.getStartMin();
  IlcInt smax1 = act1.getStartMax();
  IlcInt emin1 = act1.getEndMin();
  IlcInt emax1 = act1.getEndMax();
  IlcInt smin2 = act2.getStartMin();
  IlcInt smax2 = act2.getStartMax();
  IlcInt emin2 = act2.getEndMin();
  IlcInt emax2 = act2.getEndMax();
 
  /* DOMAIN DELTA WHEN RCT1 RANKED BEFORE RCT2 */
  IlcInt deltaEnd12   = ((emax1 < smax2) ? OL : emax1 - smax2);
  IlcInt deltaStart12 = ((smin2 > emin1) ? OL : emin1 - smin2);
  IlcInt delta12      = deltaEnd12 + deltaStart12;
 
  /* DOMAIN DELTA WHEN RCT2 RANKED BEFORE RCT1 */
  IlcInt deltaEnd21   = ((emax2 < smax1) ? OL : emax2 - smax1);
  IlcInt deltaStart21 = ((smin1 > emin2) ? OL : emin2 - smin1);
  IlcInt delta21      = deltaEnd21 + deltaStart21;
 
  /* MINIMAL NUMBER OF UNRANKED RESOURCE CONSTRAINTS */
  IlcInt nbUrkd1   = ((NbUnrankedExt*)(scheduler.getExtractable(srct1).getObject()))->getValue();
  IlcInt nbUrkd2   = ((NbUnrankedExt*)(scheduler.getExtractable(srct2).getObject()))->getValue();
  IlcInt minNbUrkd = (nbUrkd1 <= nbUrkd2) ? nbUrkd1 : nbUrkd2;
  
  /* RETURN MEASURE OF OPPORTUNITY */
  return (minNbUrkd * (delta12 - delta21));
}
 
IlcBool 
SelectMostOpportunisticConflict(IlcScheduler& schedule,
                                IlcResourceConstraint& selectedRct1,
                                IlcResourceConstraint& selectedRct2) {
  
  IlcBool existsConflict = IlcFalse;
 
  IlcInt oppMaxAbs = -1;
  IlcInt oppMax = 0;
  IlcInt opp;
  
  for (IlcUnaryResourceIterator ires(schedule); ires.ok(); ++ires) {
    IlcUnaryResource resource = (*ires);
    if (resource.hasPrecedenceGraphConstraint() &&
        !resource.isRanked()) {
 
      /* FOR EACH RESOURCE CONSTRAINT, COMPUTE AND STORE THE NUMBER OF
         RESOURCE CONSTRAINTS UNRANKED W.R.T. IT */
      for (IlcResourceConstraintIterator irct(resource); 
           irct.ok(); ++irct) {
        IlcResourceConstraint rct = (*irct);
        if (!rct.isRanked())
          ((NbUnrankedExt*)schedule.getExtractable(rct).getObject())->
            setValue(GetNumberOfUnranked(rct));
     }
      
      /* SELECT MOST OPPORTUNISTIC PAIR OF RESOURCE CONSTRAINT */
      for (IlcResourceConstraintIterator isrct1(resource); 
           isrct1.ok(); ++isrct1) {
        IlcResourceConstraint srct1 = (*isrct1);
        if (!srct1.isRanked()) {
          for (IlcResourceConstraintIterator isrct2(srct1, IlcUnranked);
               isrct2.ok(); ++isrct2) {
            IlcResourceConstraint srct2 = (*isrct2);
      opp = GetOpportunity(schedule, srct1, srct2);
      if (oppMaxAbs < IloAbs(opp)) {
              existsConflict = IlcTrue;
              oppMaxAbs      = IlcAbs(opp);
              oppMax         = opp;
              selectedRct1   = srct1;
              selectedRct2   = srct2;
            }
          }
        }
      }
    }
  }
  
  /* SELECT WHICH BRANCH WILL BE CHOSEN FIRST AMONG RCT1 << RCT2 AND
     RCT2 << RCT1 */
  if (existsConflict && (0 < oppMax)) {
    IlcResourceConstraint tmpRct = selectedRct1;
    selectedRct1 = selectedRct2;
    selectedRct2 = tmpRct;
  }
  
  return existsConflict;
}