IBM ILOG Scheduler User's Manual > Advanced Concepts > Scheduling with Discrete Resources: the Ship-loading Problem, Second Version > Complete Program and Output

You can see the entire program shipdec.cpp here or view it online in the standard distribution.

#include <ilsched/iloscheduler.h>
 
ILOSTLBEGIN
 
IloInt Capacity = 8;
IloInt NumberOfActivities = 34; 
IloInt ProcessingTimes [] = {3, 4, 4, 6, 5, 2, 3, 4, 3, 2, 
                       3, 2, 1, 5, 2, 3, 2, 2, 1, 1,
                       1, 2, 4, 5, 2, 1, 1, 2, 1, 3,
                       2, 1, 2, 2};
IloInt Demands [] = {4, 4, 3, 4, 5, 5, 4, 3, 4, 8,
                     4, 5, 4, 3, 3, 3, 6, 7, 4, 4,
                     4, 4, 7, 8, 8, 3, 3, 6, 8, 3,
                     3, 3, 3, 3};
IloInt Precedences [] = {1, 2, 1, 4,
                         2, 3,
                         3, 5, 3, 7,
                         4, 5,
                         5, 6,
                         6, 8,
                         7, 8,
                         8, 9,
                         9, 10, 9, 14,
                         10, 11, 10, 12,
                         11, 13,
                         12, 13,
                         13, 15, 13, 16,
                         14, 15,
                         15, 18,
                         16, 17,
                         17, 18,
                         18, 19, 18, 20, 18, 21,
                         19, 23,
                         20, 23,
                         21, 22,
                         22, 23,
                         23, 24,
                         24, 25,
                         25, 26, 25, 30, 25, 31, 25, 32,
                         26, 27,
                         27, 28,
                         28, 29,
                         30, 28,
                         31, 28,
                         32, 33,
                         33, 34,
                         0, 0};
 
typedef IloArray<IloModel>    IloModelArray;
typedef IloArray<IloActivity> IloActivityArray;
 
///////////////////////////////////////////////////////////////////////////////
//
// DEFINITION OF THE ACTIVITY CLASS
//
///////////////////////////////////////////////////////////////////////////////
class Activity {
private:
  IloActivity _act;
  IloBool     _critical;
  IloInt      _subProblem;
 
public:
  Activity(IloEnv env,
           IloInt number,
           IloInt processingTime);
  ~Activity();
  IloActivity getActivity() const {
    return _act;
  }
  void setCritical(IloBool critical) {
    _critical = critical;
  }
  IloBool isCritical() const {
    return _critical;
  }
  void setSubProblem(IloInt subProblem) {
    _subProblem = subProblem;
  }
  IloInt getSubProblem() const {
    return _subProblem;
  }
};
 
Activity::Activity(IloEnv env,
                   IloInt number,
                   IloInt processingTime)
  :_act        (env, processingTime),
   _critical   (IloFalse),
   _subProblem (0)
{
  _act.setObject(this);
  char buffer[128];
  sprintf(buffer, "Activity %ld ", number);
  _act.setName(buffer);
}
 
Activity::~Activity() {}
 
///////////////////////////////////////////////////////////////////////////////
//
// PROBLEM DEFINITION
//
///////////////////////////////////////////////////////////////////////////////
void
DefineProblem(IloModel          model,
              IloInt            numberOfActivities,
              IloInt*           processingTimes,
              IloInt*           demands,
              IloInt            capacity,
              IloInt*           precedences,
              IloActivityArray& activities,
              IloNumVar&        makespan)
{
  IloEnv env = model.getEnv();
 
  /* CREATE THE MAKESPAN VARIABLE. */
  IloInt horizon = 0;
  IloInt i = 0;
  for (i = 0; i < numberOfActivities; i++)
    horizon += processingTimes[i];
  makespan = IloNumVar(env, 0, horizon, IloNumVar::Int);
 
  /* CREATE THE RESOURCE. */
  IloDiscreteResource resource(env, capacity);
  resource.setPrecedenceEnforcement(IloExtended);
 
  /* CREATE THE ACTIVITIES. */
  activities = IloActivityArray(env,numberOfActivities);
  for (i = 0; i < numberOfActivities; i++) {
    Activity* act = new (env) 
      Activity(env, i + 1, processingTimes[i]);
    activities[i] = act->getActivity();
    model.add(activities[i].requires(resource, demands[i]));
  }
 
  /* POST THE PRECEDENCE CONSTRAINTS. */
  IloInt precedenceIndex;
  for (precedenceIndex = 0; ; precedenceIndex = precedenceIndex + 2) {
    IloInt predNumber = precedences[precedenceIndex] - 1;
    if (predNumber == -1)
      break;
    IloInt succNumber = precedences[precedenceIndex + 1] - 1;
    model.add(activities[succNumber].startsAfterEnd(activities[predNumber]));
  }
}
 
///////////////////////////////////////////////////////////////////////////////
//
// PROBLEM DECOMPOSITION
//
///////////////////////////////////////////////////////////////////////////////
void
DecomposeProblem(IloModel            model,
                 IloActivityArray    activities, 
                 IloNumVar           makespan,
                 IloModelArray&      subModels)
{
  // 1. CREATE DECOMPOSITION ALGORITHM AND SET SUBPROBLEMS
  IloEnv env = model.getEnv();
  IloSchedulerEnv schedEnv(env);
 
  schedEnv.setPrecedenceEnforcement(IloMediumHigh);
 
  IloSolver solver(model);
  solver.solve(IloGoalTrue(env));
 
  IloInt numberOfActivities = activities.getSize();
  IloInt nbSubProblems = 0;
  IloInt i;
  IlcScheduler schedr(solver);
  for (i = 0; i < numberOfActivities; i++) {
    Activity* act = ((Activity*) activities[i].getObject());
    if (schedr.getActivity(activities[i]).isRanked())
      act->setCritical(IloTrue);
    IloInt subProblem = 0;
    for (IloInt j = 0; j < numberOfActivities; j++)
      if ((i != j) &&
          schedr.getActivity(activities[j]).isRanked() && 
          schedr.getActivity(activities[j]).isSucceededBy
                            (schedr.getActivity(activities[i])))
        subProblem++;
    act->setSubProblem(subProblem);
    if (subProblem >= nbSubProblems)
      nbSubProblems = subProblem + 1;
  }
 
  schedEnv.setPrecedenceEnforcement(IloBasic);
  // 2. CREATE SUB-MODELS
  subModels = IloModelArray(env,nbSubProblems); 
  for (i = 0; i < nbSubProblems; i++) {
    subModels[i] = IloModel(env);
  }
 
  // 2.1 DECOMPOSE RESOURCE CONSTRAINTS
  for(IloIterator<IloResourceConstraint> iterct(env);
      iterct.ok();
      ++iterct) {
    IloResourceConstraint rct(*iterct);
    Activity* act = ((Activity*) rct.getActivity().getObject());
    subModels[act->getSubProblem()].add(rct);
  } 
 
  // 2.2 DECOMPOSE PRECEDENCE CONSTRAINTS
  for(IloIterator<IloPrecedenceConstraint> itepct(env);
      itepct.ok();
      ++itepct) {
    IloPrecedenceConstraint pct(*itepct);
    Activity* precAct = ((Activity*) pct.getPrecedingActivity().getObject());
    Activity* follAct = ((Activity*) pct.getFollowingActivity().getObject());
    if ((precAct->getSubProblem() == follAct->getSubProblem()) ||
        ((precAct->getSubProblem() == follAct->getSubProblem() - 1) &&
         (precAct->isCritical())))
      subModels[follAct->getSubProblem()].add(pct);
  } 
 
  // 2.3 SET SUB-MODELS MAKESPAN VARIABLES
  for (i = 0; i < numberOfActivities; i++) {
    Activity* act = ((Activity*) activities[i].getObject());
    if (act->isCritical()) {
      IloNumExpr subModelMakespan = activities[i].getEndExpr();
      subModels[act->getSubProblem()].add(IloMinimize(env, subModelMakespan)); 
    }
    if (act->getSubProblem() == nbSubProblems - 1) {
      subModels[act->getSubProblem()].add(activities[i].endsBefore(makespan)); 
    }
  }
  subModels[nbSubProblems-1].add(IloMinimize(env, makespan));
}
 
///////////////////////////////////////////////////////////////////////////////
//
// SOLVE SUB-MODELS
//
///////////////////////////////////////////////////////////////////////////////
void
SolveSubProblem(IloModel subModel,
                IloInt   s,
                IloActivityArray& activities,
                const IloSchedulerSolution& solution,
                IloBool lastSubProblem,
                IloNumVar makespan
                ) {
  IloEnv env = subModel.getEnv();
  IloSolver solver(env);
  solver.extract(subModel);
  IlcScheduler scheduler(solver);
 
  IloInt i = 0;
  IloInt numberOfActivities = activities.getSize();
  
  IloGoal goal;
  // Instantiate the  start- and end-time of the critical activities
  // in this sub-model based on the saved solution.
  for (i = 0; i < numberOfActivities; i++) {
    Activity* act = ((Activity*) activities[i].getObject());
    if ((act->getSubProblem() == s-1) && act->isCritical())  {
      IlcActivity ilcAct = scheduler.getActivity(activities[i]);
      ilcAct.setStartTime((IlcInt)solution.getStartMin(activities[i]));
      ilcAct.setEndTime((IlcInt)solution.getEndMax(activities[i]));
    }
    if ((act->getSubProblem() == s) && act->isCritical())  {
      assert(goal.getImpl() == 0);
      IloNumVar endVar(env, 0, IloInfinity, ILOINT);
      subModel.add(activities[i].endsAt(endVar));
      goal = IloSetTimesForward(env, endVar,
                                IloSelFirstActMinEndMin);
    }
  }
  
  if (!lastSubProblem) {
    solver.solve(goal);
  } else {
    assert(goal.getImpl() == 0);
    solver.solve(IloSetTimesForward(env, makespan, IloSelFirstActMinEndMin));
  }
 
  // Store the sub-model results in the global solution
  for (i = 0; i < numberOfActivities; i++) {
    Activity* act = ((Activity*) activities[i].getObject());
    if (act->getSubProblem() == s) 
      solution.store(activities[i], scheduler);
  }
}
 
///////////////////////////////////////////////////////////////////////////////
//
// PRINTING OF SOLUTIONS
//
///////////////////////////////////////////////////////////////////////////////
 
void
PrintSolution(IloActivityArray& activities,
              const IloSchedulerSolution& solution)
{
  IloInt numberOfActivities = activities.getSize();
  for (IloInt i = 0; i < numberOfActivities; i++) {
    IloActivity act = activities[i];
    solution.getEnv().out() << act.getName() << "  ["
                            << solution.getStartMin(act) 
                            << " -- "
                            << solution.getProcessingTimeMin(act)
                            << " --> "
                            << solution.getEndMin(act)
                            << "]" << endl; 
  }   
}
 
///////////////////////////////////////////////////////////////////////////////
//
// MAIN FUNCTION
//
///////////////////////////////////////////////////////////////////////////////
int main() {
  try {
    IloEnv env;
    IloModel model(env);
    IloNumVar makespan;
    
    IloActivityArray activities(env);
    
    DefineProblem(model,
                  NumberOfActivities,
                  ProcessingTimes,
                  Demands,
                  Capacity,
                  Precedences,
                  activities,
                  makespan);
    
    /** Decompose the problem in a set of independent subproblems. */
    IloModelArray  subModels(env);
    DecomposeProblem(model, activities, makespan, subModels);
    
    /** Solve each sub-problem independently. */
    IloSchedulerSolution solution(env);
    IloInt nbSubProblems = subModels.getSize();
    for (IloInt i=0; i < nbSubProblems; i++) {
      IloModel subModel = subModels[i];
      SolveSubProblem(subModel, i, activities, solution, 
                      i==nbSubProblems-1, makespan);
    }
    
    PrintSolution(activities, solution); 
    solution.end();
    env.end();
 
  } catch (IloException& exc) {
    cout << exc << endl;
  }
 
  return 0;
}
 
///////////////////////////////////////////////////////////////////////////////
//
// RESULTS
//
///////////////////////////////////////////////////////////////////////////////
 
/* shipdec
   Activity 1    [0 -- 3 --> 3]
   Activity 2    [3 -- 4 --> 7]
   Activity 3    [7 -- 4 --> 11]
   Activity 4    [3 -- 6 --> 9]
   Activity 5    [14 -- 5 --> 19]
   Activity 6    [19 -- 2 --> 21]
   Activity 7    [11 -- 3 --> 14]
   Activity 8    [21 -- 4 --> 25]
   Activity 9    [25 -- 3 --> 28]
   Activity 10   [28 -- 2 --> 30]
   Activity 11   [32 -- 3 --> 35]
   Activity 12   [30 -- 2 --> 32]
   Activity 13   [35 -- 1 --> 36]
   Activity 14   [30 -- 5 --> 35]
   Activity 15   [36 -- 2 --> 38]
   Activity 16   [36 -- 3 --> 39]
   Activity 17   [39 -- 2 --> 41]
   Activity 18   [41 -- 2 --> 43]
   Activity 19   [44 -- 1 --> 45]
   Activity 20   [43 -- 1 --> 44]
   Activity 21   [43 -- 1 --> 44]
   Activity 22   [44 -- 2 --> 46]
   Activity 23   [46 -- 4 --> 50]
   Activity 24   [50 -- 5 --> 55]
   Activity 25   [55 -- 2 --> 57]
   Activity 26   [57 -- 1 --> 58]
   Activity 27   [58 -- 1 --> 59]
   Activity 28   [63 -- 2 --> 65]
   Activity 29   [65 -- 1 --> 66]
   Activity 30   [60 -- 3 --> 63]
   Activity 31   [59 -- 2 --> 61]
   Activity 32   [57 -- 1 --> 58]
   Activity 33   [58 -- 2 --> 60]
   Activity 34   [61 -- 2 --> 63]
*/
 

The decomposition dramatically decreases the number of failures to 38 and the CPU time to 0.2 seconds.