Heuristic Overview

IBM ILOG Scheduler User's Manual > Integrated Applications > Scheduling with Alternative Resources: Interleaving Resource Allocation and Scheduling Decisions > Solving the Problem > Heuristic Overview

Heuristic Overview

INDEX

PREVIOUS NEXT

At a search state, the heuristic decision is structured as follows:

Select a resource, R.
Identify a pair of unsequenced resource constraints on resource R.
Identify an alternative resource constraint on resource R.
Choose between one of the two following choice points:

a) Constrain one of the pair of resource constraints to be before the other with the alternative being the opposite sequence.

b) Constrain the alternative resource constraint to not execute on this resource with the alternative being that it must execute on this resource.

Selecting a Resource

A resource is chosen simply by selecting the one with the maximum criticality at any time point. Ties are broken arbitrarily.

Selecting a Pair of Resource Constraints

Given the critical resource, a pair of resource constraints are identified. These resource constraints:

Are not alternative resource constraints.
Have a non-zero maximum possible requirement for the resource at its most critical time point.
Are not already sequenced with each other.

  IlcRCTextureArray rcTextures = 
    texture.getCriticalityOrderedRCTextures();
  IlcInt nbRCTextures = rcTextures.getSize();
 
  IlcInt i;
  for(i = 0; i < nbRCTextures - 1;  ++i) {
 
    IlcFloat c = rcTextures[i].getCriticalContribution();
    if (c == 0)
      return IlcFalse;
 
    if (!rcTextures[i].hasAlternatives()) {
      rctA = rcTextures[i].getResourceConstraint();
      maxCriticality = c;
 
      IlcInt j;
      for(j = i+1;
          (j < nbRCTextures) &&
           (rcTextures[j].getCriticalContribution() > 0); ++j) {
 
        if (!rcTextures[j].hasAlternatives()) {
          rctB = rcTextures[j].getResourceConstraint();
 
        if (!rctA.isSucceededBy(rctB) && 
            !rctB.isSucceededBy(rctA)) {
            // found the pair to sequence
            return IlcTrue;
          }
        }
      }
    }
  }
 
  return IlcFalse;

The rcTextures array in the above code is an array of IlcRCTexture for each activity on the resource. The array is sorted in descending order of the contribution that the activity has for the texture curve at the critical time point. Recall that each activity has an individual texture curve and that these texture curves are aggregated to form the resource texture curve. The ordering of this array means that the pair of resource constraints that is selected consists of:

The resource constraint, A, with the highest contribution to the critical time point that meets the first two criteria above.
The resource constraint, B, with the highest contribution to the critical point that meets the first two criteria above and which is not equal to A nor already sequenced with A.

This code only selects the pair of resource constraints, A and B, not the actual sequence, A before B or B before A. The sequence is selected only after it is determined that a precedence constraint will be added at this search node. See Interleaving Resource Allocation and Scheduling.

Selecting an Alternative Resource Constraint

The alternative resource constraint that is chosen is simply the one that has the highest contribution of all alternative resource constraints to the critical time point of the resource.

  IlcRCTextureArray rcTextures =
    texture.getCriticalityOrderedRCTextures();
  IlcInt nbRCTextures = rcTextures.getSize();
 
  for(IlcInt i = 0; i < nbRCTextures; ++i) {
    IlcFloat c = rcTextures[i].getCriticalContribution();
    if (c == 0)
      return IlcFalse;
    if (rcTextures[i].hasAlternatives()) {
      // rcTextures is sorted in descending order of
      // criticality so the first rct we find with
      // alternatives is the one with the highest crit.
      altRC = rcTextures[i].getResourceConstraint();
      criticality = c;
      return IlcTrue;
    }
  }
 
  return IlcFalse;

Interleaving Resource Allocation and Scheduling

The final decision is to choose whether the scheduling decision (that is, sequencing of the pair of resource constraints) or the resource allocation decision (constraining the alternative resource constraint to execute on another resource) should be made. This is done by comparing the maximum criticality of a resource constraint in the pair with that of the alternative resource constraint. The decision accompanying the resource constraint with higher criticality is chosen.

    IlcBool pairFound = choosePair(selectedTexture, 
                                   rctA, rctB, maxPairCriticality);
    IlcBool altFound = chooseAlternative(selectedTexture, 
                                         rctC, altCriticality);
 
    if (!pairFound && !altFound) {
      // If neither a pair nor an alternative is found, then
      // there are no commitments that this goal can make at
      // the critical point.
      selectedTexture.setNoCommitmentsAtCriticalPoint();
      selectedTexture = chooseResource();
    }
    else {
      if (!pairFound || 
          (altFound && (maxPairCriticality <= altCriticality))) 
        return IlcAnd(IlcTryNotPossible(rctC.getResource(), 
                                        rctC.getAlternative()),
                      this);
      else {
        IlcResourceConstraint before, after;
        IlcBool sequenceOK = chooseSequence(before, after,
                                            rctA, rctB);
        assert(sequenceOK);
 
        return IlcAnd(IlcTrySetSuccessor(before, after), this);
      }
    }

The chooseSequence function chooses the actual sequence of the two resource constraints which will be tried in the first branch of the OR-goal. This calculation is done based on an analysis of the slack time that results from the two possible sequences. Further information can be found in the paper that is referenced in the full code of the example.

The Possibility of No Commitments

The previous code sample accounts for the possibility that neither an alternative resource constraint nor a pair of unsequenced resource constraints could be found.

This can happen because the texture measurement is an estimate of the criticality of the resource. The fact that no possible commitments could be found at the critical time point means that all resource constraints that can possibly execute at that time point have no alternatives and are completely sequenced. Therefore, the criticality of the resource at the time point is actually 0. This fact can be communicated to the texture measurement data structure using the setNoCommitmentsAtCriticalPoint() method. This method identifies the largest temporal interval for which the set of possible resource constraints is equal to the set of possible resource constraints at the critical time point. The criticality of that interval is set to 0.

PREVIOUS NEXT