The original model is simply a variation of the job shop scheduling problem with resources of capacity 3 (instead of unary resources) and with 3 instantiations of each job. The optimization criteria is the minimization of the makespan.

As with any non-deterministic search using the Scheduler Engine, there are three components to solving the problem:

1) The level of constraint propagation, defined by the enforcement levels of the model.

2) The heuristic used to guide the non-deterministic search.

3) The technique used for backtracking from a search state where we have discovered that there is no solution.

Constraint Propagation

The constraint propagation is defined by the enforcement levels of the problem model. For this problem, we have decided to set the capacity enforcement level to IloHigh and the precedence enforcement level to IloMediumHigh.

  IloSchedulerEnv schedEnv(env);
  schedEnv.getResourceParam().setCapacityEnforcement(IloHigh);
  schedEnv.getResourceParam().setPrecedenceEnforcement(IloMediumHigh);

These levels mean that for capacity enforcement, we use the disjunctive global constraint and the edge-finder, and for the precedence enforcement, we use the precedence graph global constraint. See Resource Enforcement as Global Constraint Declaration in the IBM ILOG Scheduler Reference Manual for more information.

Heuristic Search Guidance

The search goal used to solve the original model is based on the creation of texture measurements on each resource and the dynamic focusing of search interest on resources and time points that the texture measurements reveal to be critical. See Texture Measurements in the IBM ILOG Scheduler Reference Manual for more information on texture measurements.

By setting a random number generator in the texture parameter, we specify that the critical time point on a resource should be randomly selected from all those time points with maximal criticality. Without the random number generator, the critical time point is arbitrarily chosen from the time points of maximal criticality. This inserts a stochastic element into our heuristic as, given an identical configuration of activities, different critical time points will be chosen and therefore different search decisions will be made. We further extend this stochasticity in choosing the overall critical resource (see the following code sample) and use the stochastic nature in the design of our backtracking technique.

At a high level, a single heuristic decision is made with the following code:

IlcGoal TextureGoalI::execute() {

  IlcResourceTexture selectedTexture = chooseResource();
  while(0 != selectedTexture.getImpl()) {

    IlcResourceConstraint rctA, rctB;
    if (!choosePrecedence(selectedTexture, rctA, rctB)) {
      selectedTexture.setNoCommitmentsAtCriticalPoint();
      selectedTexture = chooseResource();
    }
    else
      return IlcAnd(IlcTrySetSuccessor(rctA, rctB), this);
  }

  return 0;
}

The resource is selected by calculating the texture measurements stochastically, and choosing a critical point for each resource (if the resource's maximum criticality is greater than 0). From the set of resources with a non-zero criticality, we then choose one, with uniform probability. This adds another stochastic component to our heuristic

  for(IlcResourceIterator iter(_schedule); iter.ok(); ++iter) {
    if ((*iter).isDiscreteResource()) {
      IlcDiscreteResource res = (IlcDiscreteResource) (*iter);
      IlcResourceTexture texture = res.getTextureMeasurement();
      
      if (texture.getMaxCriticality() > 0) {
	nbNonzero++;
	if ((0 == selectedTexture.getImpl()) || 
	    (_randGen.getFloat() < 1/(IlcFloat) nbNonzero)) {
	  selectedTexture = texture;
	}
      }
    }
  }

Once we have selected a resource, we then select two resource constraints which compete for the critical resource and time point and which are not sequenced with each other. We then post a new precedence constraint between this pair. The heuristic for choosing this pair and the heuristically-preferred precedence constraint is based on a heuristic from the scheduling literature designed to minimize the impact of the new precedence constraint. The reverse precedence constraint is used upon backtracking.

Note that it is possible that a suitable precedence constraint on the critical resource cannot be found. This is because the texture measurement is only an estimate of the competition for the resource. In such a case the member function setNoCommitmentsAtCriticalPoint can be used to inform the texture measurement that there are no commitments and therefore the critical point has been falsely identified. See IlcResourceTexture in the IBM ILOG Scheduler Reference Manual for details.

The choice point created here does not lead to a complete search. We create a binary choice point dealing with two activities, A and B. The choice point specifies: (A --> B) OR (B --> A). However, because we are dealing with discrete resources with capacity greater than 1, there is a third possibility. It may be that in an optimal solution, no precedence constraint exists: rather A and B overlap execution. Therefore, a search using this heuristic is not guaranteed to find a solution if one exists. Such a search cannot be used (by itself) to prove the optimality of a solution.

This is a design decision. The hope is that such an incomplete technique will be useful in quickly finding good solutions and that in this application quick generation of good solutions is more important than proving optimality. If there is more computation time available after a good solution has been found by an incomplete technique, we can switch to a complete search technique to prove optimality (and perhaps find even better solutions).

Backtracking

Because of the incompleteness and stochasticity of the heuristic search, it does not appear useful to perform standard chronological backtracking. Such an approach would limit the effect of stochastically on the search and, even if we completely explored the backtrack tree, we cannot guarantee that no better solutions exist. Therefore, we specify a limited number of fails to be expended in the search for a solution and use a backtracking technique that combines restart with some chronological backtracking.

Recall that because of our stochastic heuristic search, restarting the search is likely to move us to a very different area of the search space. While this diversity is often very useful, it may also be counterproductive: with a good heuristic and strong propagators, we might expect that we could find better solutions in the same area of the search space as our current best solution. Restarting immediately draws the search away from such an area. With these intuitions in mind, we use a search that combines restart with chronological backtracking. That is, we initially start chronological backtracking with a very low limit on the number of fails allows (such as 1). When the fail limit is reached, search is restarted and the fail limit is increased. In our case, we double the fail limit each time we restart up to a predefined limit on the total number of fails. This search technique attempts to balance the effort spent in searching in one area of the search space (by increasing the fail limit) with the effort spent exploring new areas of the search space (through restart). Further details about this backtracking technique can be found in the scheduling literature.

To implement our backtracking technique we make use of the IloLimitSearch goal in IBM ILOG Solver. Each time we find a solution, we store it in an IloSchedulerSolution object.

    IloGoal limitedGoal = IloLimitSearch(env, goal, 
					 IloFailLimit(env, localFailLimit));

    solver.startNewSearch(limitedGoal);

    while(!foundOpt && solver.next()) {
      bestOptVal = solver.getIntVar(optVar).getValue();
      solver.out() << "Solution with optimization value: " 
		   <<  bestOptVal << endl; 
      solution.store(scheduler);

      if (bestOptVal == minOpt) {
	solver.out() << "Locally optimal solution" << endl;
	foundOpt = IloTrue;
      }
      solved = IloTrue;
    }

As noted above, every time we exhaust the fail limit, we double it up to the specified failLimit. We create a new limited goal, with the higher limit, and continue search.

    nbOfFails += solver.getNumberOfFails();
    localFailLimit *= 2;
    IloInt failsLeft = failLimit - nbOfFails;
    if (localFailLimit > failsLeft)
      localFailLimit = failsLeft;

While we are doing an incomplete search, there is a condition under which we can soundly conclude that we have an optimal solution. Before starting the search, we simply propagate all constraints and save the minimal value of the optimization criteria. This value is clearly a lower-bound on the optimization criteria. At any time during search, if we discover a solution whose optimization criteria is equal to this lower-bound, we can immediately stop the search and conclude that we have an optimal solution.

  solver.solve(IloGoalTrue(env));
  IlcInt minOpt = solver.getIntVar(optVar).getMin();
  solver.out() << "Initial propagation lower-bound optimization value: " 
	       << minOpt << endl;