IBM ILOG Scheduler User's Manual > Local Search in Scheduler > Large Neighborhood Search for the Jobshop Problem with Alternatives > Solving the Problem > Defining a new scheduler large neighborhood: RelocateJobNHood

We define a special neighborhood that can be seen as an extension of the neighborhood IloRelocateActivityNHood but instead of selecting one activity we select all the activities belonging to a job: the size of this neighborhood is the number of jobs in the problem. For this new neighborhood, we will use the same default behavior as IloRelocateActivityNHood.

New class RelocateJobNHoodI

To define a scheduler large neighborhood, the first step is to define a sub-class of the abstract class IloSchedulerLargeNHooI and to define the three virtual member functions: start, getSize, defineSelected:

class RelocateJobNHoodI : public IloSchedulerLargeNHoodI {
protected:
  IloArray<IloActivityArray> _jobs;

public:
  RelocateJobNHoodI(IloEnv env,
                    IloArray<IloActivityArray> jobs,
                    const char* name);
  ~RelocateJobNHoodI();
  // virtuals
  virtual IloInt getSize(IloSolver solver) const;
  virtual IloSolution defineSelected(IloSolver solver, IloInt index);
  virtual void start(IloSolver solver, IloSolution solution);
};

Constructor of class RelocateJobNHoodI

The constructor of this neighborhood takes as a parameter an array of jobs where a job is simply a set of activities. The default behavior of this neighborhood is to restore the successors, the predecessors the resource assignment and the required capacity of all resource constraints but the one selected. This default behavior is specified by using predicates.

The predicates are shown in the following code.

ILOPREDICATE0(IloRCFalsePredicate,
              IloResourceConstraint, rc) {
  return IloFalse;
}
 
ILOCTXPREDICATE0(IloRCTrueIfNotSelectedPredicate,
                 IloResourceConstraint, rc,
                 IloSchedulerLargeNHood, nhood) {
  if (nhood.isSelected(rc))
    return IloFalse;
  else 
    return IloTrue;
}
 
ILOPREDICATE0(IloActivityFalsePredicate,
                IloActivity, activity) {
  return IloFalse;
}
 
RelocateJobNHoodI::RelocateJobNHoodI(IloEnv env,
                                     IloArray<IloActivityArray> jobs,
                                     const char* name)
  : IloSchedulerLargeNHoodI(env, name),
    _jobs(env)
{
  // set default restore policy
  IloPredicate<IloResourceConstraint> rcFalsePredicate = 
    IloRCFalsePredicate(env);
  setRestoreRCNextPredicate(rcFalsePredicate);
  setRestoreRCPrevPredicate(rcFalsePredicate);
  setRestoreRCSetupPredicate(rcFalsePredicate);
  setRestoreRCTeardownPredicate(rcFalsePredicate);
  IloPredicate<IloResourceConstraint> rcTrueIfNotSelectedPredicate = 
    IloRCTrueIfNotSelectedPredicate(env);
  setRestoreRCDirectSuccessorPredicate(rcTrueIfNotSelectedPredicate);
  setRestoreRCDirectPredecessorPredicate(rcTrueIfNotSelectedPredicate);
  setRestoreRCCapacityPredicate(rcTrueIfNotSelectedPredicate);
  setRestoreRCSelectedPredicate(rcTrueIfNotSelectedPredicate);
 
  IloPredicate<IloActivity> activityFalsePredicate =
    IloActivityFalsePredicate(env);
  setRestoreActivityStartPredicate(activityFalsePredicate);
  setRestoreActivityEndPredicate(activityFalsePredicate);
  setRestoreActivityDurationPredicate(activityFalsePredicate);
  setRestoreActivityProcessingTimePredicate(activityFalsePredicate);
  setRestoreActivityExternalPredicate(activityFalsePredicate);
  
  for (IloInt j=0; j<jobs.getSize(); ++j) {
    IloInt nbActivities = jobs[j].getSize();
    IloActivityArray job(env);
    for (IloInt a=0; a<nbActivities; ++a) {
      IloActivity activity = jobs[j][a];
      job.add(activity);
    }
    _jobs.add(job);
  }
}
 
 

Overriding virtual method start

The method start simply calls the corresponding method of its parent class: this allows registration the scheduler solution solution as the current solution.

void 
RelocateJobNHoodI::start(IloSolver solver, IloSolution solution) 
{
  IloSchedulerLargeNHoodI::start(solver, solution);
}

Overriding virtual method getSize

The size of this neighborhood is the simply the number of jobs in the jobshop problem.

IloInt 
RelocateJobNHoodI::getSize(IloSolver solver) const
{
  IloInt size = _jobs.getSize();
  
  return size;
}

Overriding virtual method defineSelected

The role of this method is to define a scheduler solution that represents the set of scheduler objects that are selected for the given index. Here the index of the neighborhood is simply used as the index in the array of jobs: all activities and all resource constraints corresponding to that job are added to the set.

IloSolution
RelocateJobNHoodI::defineSelected(IloSolver solver, IloInt index)
{
  IloEnv env = solver.getEnv();
  
  IloActivityArray job;
  job = _jobs[index];
  
  IloSchedulerSolution selected(env);
  
  IloSchedulerSolution currentSolution = getCurrentSolution();
  
  // add in selected all activities of selected job and their
  // resource constraints
  IloInt nbActivities = job.getSize();
  for (IloInt a=0; a<nbActivities; a++) {
    IloActivity activity = job[a];
    selected.add(activity);
    IloSchedulerSolution::ResourceConstraintIterator 
      rcIter(currentSolution, activity);
    for (; rcIter.ok(); ++rcIter) {
      IloResourceConstraint rc = *rcIter;
      selected.add(rc);
    }
  }
  
  return selected;
}

Defining a Wrapper

The last step consists in writing a function that wraps an instance of RelocateJobNHoodI in a IloSchedulerLargeNHood handle.

IloSchedulerLargeNHood 
RelocateJobNHood(IloEnv env, 
                 IloArray<IloActivityArray> jobs,
                 const char* name = 0)
{
  return new (env) RelocateJobNHoodI(env, 
                                     jobs,
                                     name);
}

The following line creates an instance of RelocateJobNHood with the default behavior described above.

  IloSchedulerLargeNHood relocateJobNHood = RelocateJobNHood(env, jobs);