One common way to model a solution to a job shop scheduling problem is as a set of nodes, corresponding to each activity, and a set of edges, corresponding to next relations in the precedence graph and to the precedence constraints in the original problem definition. The weight of each edge is the duration of the preceding activity. In such a model any path from a virtual source node to a virtual sink node of maximum length corresponds to a critical path of the solution.

Rather than making use of the graph representation, we calculate the critical path directly on the IloActivity instances stored in the IloSchedulerSolution. To do this we make use of the fact that any activity that is on the critical path must have its start time assigned when the makespan variable is assigned. We can easily identify all of these activities, sort them into an array in non-descending order of start time, and then, with a single pass through the array, pick a single critical path.

To implement this critical path calculation, we introduce a CriticalPath class, defined in the following code.

class CriticalPath {
private:
  IloInt _cpSize;
  IloArray<IloResourceConstraint> _cpArray;

  IloRandom _randGen;

  RCSortElement *getCriticalRCs(IloSchedulerSolution, IloInt&);
  void pickRandomCP(RCSortElement *, IloSchedulerSolution,IloInt);
  void addCPElement(IloResourceConstraint);

public:
  CriticalPath(IloEnv env) :
    _cpSize(0), _cpArray(env), _randGen(env, 98998) {}
  ~CriticalPath() {}

  IloArray<IloResourceConstraint>& computeCP(IloSchedulerSolution, IloInt&);
};

We proceed step-by-step, through the methods of this class. First, the primary public method is the computeCP method defined in the following code.

IloArray<IloResourceConstraint>& CriticalPath::computeCP(
				       IloSchedulerSolution solution,
				       IloInt& cpSize) {
  IloInt nbCriticalRCs = 0;
  RCSortElement *sortArray = getCriticalRCs(solution, nbCriticalRCs);
  
  // Pick the RCs in one (randomly selected) critical path
  pickRandomCP(sortArray, solution, nbCriticalRCs);
  delete [] sortArray;

  cpSize = _cpSize;
  return _cpArray;
}

The first call in this function, getCriticalRCs, returns an array of IloResourceConstraint instances sorted in non-descending order of start time. As this makes use of standard C++ techniques, we will not describe it in-depth (see the complete code for details).

The second function call, pickRandomCP, assigns the member data _cpArray to a randomly selected critical path. This function uses the sorted array of resource constraints to construct such a path. The code for pickRandomCP follows.

void CriticalPath::pickRandomCP(RCSortElement *sortArray,
				IloSchedulerSolution solution,
				IloInt nbCriticalRCs) {
  _cpSize = 0;
  IloNum endRC = 0;
  IloInt i = -1;
  while(i < nbCriticalRCs - 1) {
    // skip elements not on the same critical path as rc
    IloInt nextIndexStart = i + 1;
    while((nextIndexStart < nbCriticalRCs) &&
          (sortArray[nextIndexStart].getStartValue() < endRC))
      nextIndexStart++;
    
    // gather elements that are successors of rc on the critical
    // path. There may be more than one

    IloInt nextIndexEnd = nextIndexStart + 1;
    while((nextIndexEnd < nbCriticalRCs) &&
          (sortArray[nextIndexEnd].getStartValue() == endRC))
      nextIndexEnd++;
      
    if (nextIndexStart < nbCriticalRCs) {

      // At this point the elements between sortArray[nextIndexStart]
      // and sortArray[nextIndexEnd-1] inclusive are all successors to
      // rc on some critical path. 
      // We randomly pick one of them.

      IloInt randIndex = nextIndexStart;
      IloInt indexDiff = nextIndexEnd - nextIndexStart;
      if (indexDiff > 1)
        randIndex += _randGen.getInt(indexDiff);
            
      IloResourceConstraint next = sortArray[randIndex].getRC();
      addCPElement(next);

      i = randIndex;
      endRC = solution.getEndMin(next.getActivity());
    }
    else
      i = nbCriticalRCs;
  }
}

Each iteration of the outer while-loop in pickRandomCP selects a single resource constraint from the sortArray to be a member of the randomly selected critical path. Essentially, given a resource constraint rc that has already been selected as part of the critical path, we skip all the other resource constraints that start before the end time of rc. Clearly, these resource constraints cannot be on a critical path containing rc.

    IloInt nextIndexStart = i + 1;
    while((nextIndexStart < nbCriticalRCs) &&
          (sortArray[nextIndexStart].getStartValue() < endRC))
      nextIndexStart++;

We then gather the elements that have start times equal to the end time of rc.

    IloInt nextIndexEnd = nextIndexStart + 1;
    while((nextIndexEnd < nbCriticalRCs) &&
          (sortArray[nextIndexEnd].getStartValue() == endRC))
      nextIndexEnd++;

Finally, we randomly choose a resource constraint from those that start at the end of rc. This is the next resource constraint in the critical path.

      IloInt randIndex = nextIndexStart;
      IloInt indexDiff = nextIndexEnd - nextIndexStart;
      if (indexDiff > 1)
        randIndex += _randGen.getInt(indexDiff);
            
      IloResourceConstraint next = sortArray[randIndex].getRC();
      addCPElement(next);

The outer while-loop then continues using the most recently selected resource constraint. We make use of the critical path to construct the moves in our neighborhood.