The N1 neighborhood is a commonly used neighborhood from the Operations Research literature for local search in job shop scheduling. The neighborhood consists of the swapping of all pairs of adjacent activities that are both on the same resource and on the same randomly selected critical path. As noted above, we make use of the CriticalPath object introduced in the previous chapter to select a critical path.

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

class N1NHoodI : public IloNHoodI {
private:
  IloSchedulerSolution _solution;

  CriticalPath *_cp;

  IloArray<SwapRC*> _moves;
  IloInt _nbMoves;

  void addMove(IloSolver solver, 
               IloResourceConstraint rc, IloResourceConstraint after);

public:
  N1NHoodI(IloEnv env, CriticalPath *cp, const char *name = 0 ) :
    IloNHoodI (env, name), _cp(cp), _moves(env), _nbMoves(0) {}
  ~N1NHoodI() {}

  void start(IloSolver solver, IloSolution soln);

  IloSolution define(IloSolver solver, IloInt i) {
    return (_moves[i])->createDelta(solver.getEnv(), _solution);
  }

  IloInt getSize(IloSolver) const { return _nbMoves; }

  void reset() { _solution = 0; _nbMoves = 0; }
};

The data members of N1NHoodI are the current solution (_solution), a pointer to the CriticalPath object (_cp), an array of pointers to SwapRC instances (_moves), and the number of elements currently in that array (_nbMoves).

Given the SwapRC class discussed above, three of the four neighborhood functions are very simple.

The main computation of the neighborhood is performed in the start method where, after some initialization, the previous pointers are set and the critical path is calculated by the CalculatePrevs function and CriticalPath class discussed above.

  IloInt cpSize = 0;
  IloArray<IloResourceConstraint> cpArray = _cp->computeCP(_solution, cpSize);

Then the moves are created. Consecutive elements on the critical path are examined and if they share a next relation, a move is created.

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

    if ((_solution.getNextRC(rc).getImpl() != 0) &&
        (after.getImpl() == _solution.getNextRC(rc).getImpl())) {
        
      addMove(solver, rc, after);
    }
  }