The primary part of implementing a local search technique in Scheduler is the creation of the appropriate neighborhood class (or classes) to describe the local search moves. The shuffle neighborhood is quite simple as it does not concern itself with making new search decisions, but rather with removing some of the decisions that define the critical path of the existing solution. Actually, in our implementation we take the opposite decision: we identify the set of next relations that we will preserve in the next search. This set defines a partial solution from which a constructive search will be done.

To construct the ShuffleNHoodI we subclass from the IBM ILOG Solver class IloNHoodI.

class ShuffleNHoodI : public IloNHoodI {
private:
  IloNumVar _costVar;
  IloNum _prob;

  CriticalPath _cp;

  IloSchedulerSolution _delta;
  IloRandom _randGen;

public:
  ShuffleNHoodI(IloEnv env, IloNumVar cost, 
		IloNum probability, const char *name = 0)
    : IloNHoodI (env, name),
      _costVar(cost), _prob(probability),
      _cp(env), _delta(0), _randGen(env, 98998) {}
  ~ShuffleNHoodI() {}

  void        start       (IloSolver solver, IloSolution soln);

  IloSolution define      (IloSolver solver, IloInt) {
    assert(_delta.getImpl() != 0);
    assert(_delta.getSolution().getImpl() != 0);
    return _delta.getSolution().makeClone(solver.getEnv());
  }

  IloInt      getSize     (IloSolver) const { return 1; }
};

As we have a relatively simple neighborhood, we only override three of the virtual functions of IloNHoodI.

The define method is called by the local search protocol and must return an IloSolution representing the move that should be performed. It is a good idea to make this function as small and as fast as possible as it is called many times during the local search. In our case, we simply return a clone of the _delta solution, which we previously computed (in start; code follows).

The other function is getSize which returns the number of neighbors in the neighborhood. In our case, we have only one neighbor.

Most of the work in ShuffleNHoodI is done in the start method. The method begins by calculating the critical path, using the CriticalPath object presented above.

  IloInt cpSize = 0;
  IloArray<IloResourceConstraint> cpArray = _cp.computeCP(solution, cpSize);

The second step is to create an IloSchedulerSolution to represent the move that will be investigated. We do this simply by cloning the current solution.

  if (_delta.getImpl() != 0)
    _delta.end();
  _delta = solution.makeClone(env);

The critical path is represented as an array of IloResourceConstraint objects such that adjacent elements of the array are adjacent elements of the critical path. Recall, however, that there are two ways in which a pair of resource constraints can be adjacent on the critical path: they may execute consecutively on the same resource or they may correspond to consecutive activities in the same job. Clearly, we cannot remove edges of the latter type as they are part of the original problem definition. Therefore, we examine an adjacent pair of resource constraints on the critical path and ensure that they are also an adjacent pair on a resource. Then, based on a probability, we decide whether to preserve this adjacent pair in the next solution.

  for(IloInt i = 0; i < cpSize - 1; ++i) {
    IloResourceConstraint before = cpArray[i];
    IloResourceConstraint after = cpArray[i + 1];

    if (solution.hasNextRC(before) &&
	(after.getImpl() == solution.getNextRC(before).getImpl()) &&
	(_randGen.getFloat() > _prob)) {
      // Remove resource constraint from delta. This has the effect of
      // ensuring that this edge will be in the next solution
      _delta.remove(before);
    }
  }

Finally, all the other resource constraints in the solution, regardless of whether they are on the critical path or not, have their next relations removed from delta.

  for(IloSchedulerSolution::ResourceConstraintIterator iter3(_delta);
      iter3.ok(); ++iter3) {
    IloResourceConstraint rc = *iter3;
    if (_delta.hasNextRC(rc))
      _delta.unsetNext(rc, _delta.getNextRC(rc));      
  }

It is important to understand the difference between removing the resource constraint from _delta and removing the next relation from a resource constraint in _delta. With the local search protocol, removing the resource constraint means that the values in the current solution for that resource constraint will be restored. Removing the next relation means that no next relation is restored. This is a critical distinction and can be best understood from the perspective of the local search protocol, which is faced with two solution objects: one containing the previous solution and the other containing the changes (the "delta") that must be done to the previous solution to visit a specific neighbor. The protocol first restores the elements of the previous solution that are not in the delta. It then restores the objects in the delta. So the resource constraints that are not in the delta are restored to their previous values. The resource constraints that are in the delta, but have no specified next relation are restored without specifying the next relations. Because the next relations are not defined, we have space to subsequently search for a new solution.

Finally, since the delta contains the variable representing the cost, it is necessary to reset its lower bound to 0 or else no improved solution will be found. Note that we leave the upper bound of the cost variable as it is: this means that the subsequent constructive search goals are constrained to find solutions that are as good as or better than the current solution.

  _delta.setMin(_costVar, 0);