IBM ILOG Scheduler User's Manual > Advanced Concepts > Scheduling with State Resources: the Trolley Problem > Complete Program and Output

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

#include <ilsched/iloscheduler.h>
 
ILOSTLBEGIN
const IloInt MACH1 = 1; // Machine 1 area
const IloInt MACH2 = 2; // Machine 2 area
const IloInt MACH3 = 3; // Machine 3 area
const IloInt AREAA = 4; // Arrival area
const IloInt AREAS = 5; // Stock area
const IloNum loadDuration = 20;
const IloInt numberOfJobs = 6;
 
const char*  JobNames [] = { "J1",   "J2",   "J3",   "J4",   "J5",   "J6"};
IloInt Machines1      [] = { 1,      2,      2,      1,      3,      2   };
IloNum Durations1     [] = { 80,     120,    80,     160,    180,    140 };
IloInt Machines2      [] = { 2,      3,      1,      3,      2,      3   };
IloNum Durations2     [] = { 60,     80,     60,     100,    80,     60  };
///////////////////////////////////////////////////////////////////////////////
//
// DEFINITION OF THE JOB CLASS
//
///////////////////////////////////////////////////////////////////////////////
class Job {
private:
  const char* _name;
  IloActivity _loadA;
  IloActivity _unload1;
  IloActivity _process1;
  IloActivity _load1;
  IloActivity _unload2;
  IloActivity _process2;
  IloActivity _load2;
  IloActivity _unloadS;
  IloInt      _area1;
  IloInt      _area2;
  IloUnaryResource _machine1;
  IloUnaryResource _machine2;
public:
  Job(IloEnv env,
      const char*,
      IloNum,
      IloUnaryResource, IloNum, IloInt,
      IloUnaryResource, IloNum, IloInt);
  ~Job();
  void addToModel(IloModel model,
                  IloStateResource trolley,
                  IloNumVar makespan);
  void printSolution(IlcScheduler scheduler, ILOSTD(ostream)& out);
  const char* getName() const { return  _name;}
 
  IloActivity getLoadA() const { return _loadA;}
  IloActivity getUnload1() const { return _unload1;}
  IloActivity getProcess1() const { return _process1;}
  IloActivity getLoad1() const { return _load1;}
  IloActivity getUnload2() const { return _unload2;}
  IloActivity getProcess2() const { return _process2;}
  IloActivity getLoad2() const { return _load2;}
  IloActivity getUnloadS() const { return _unloadS;}
 
};
 
Job::Job(IloEnv env,
         const char*  name,
         IloNum loadDuration,
         IloUnaryResource machine1, IloNum duration1, IloInt area1,
         IloUnaryResource machine2, IloNum duration2, IloInt area2)
  : _name(name),
    _loadA(   env,loadDuration),
    _unload1( env,loadDuration),
    _process1(env,duration1),
    _load1(   env,loadDuration),
    _unload2( env,loadDuration),
    _process2(env,duration2),
    _load2(   env,loadDuration),
    _unloadS( env,loadDuration),
    _area1(area1),
    _area2(area2),
    _machine1(machine1),
    _machine2(machine2)
{
  char buffer[256];
 
  sprintf(buffer, "arrival_load_%s", name);
  _loadA.setName(buffer);
 
  sprintf(buffer, "area%ld_unload_%s", area1, name);
  _unload1.setName(buffer);
 
  sprintf(buffer, "machine%ld_%s", area1, name);
  _process1.setName(buffer);
 
  sprintf(buffer, "area%ld_load_%s", area1, name);
  _load1.setName(buffer);
 
  sprintf(buffer, "area%ld_unload_%s", area2, name);
  _unload2.setName(buffer);
 
  sprintf(buffer, "machine%ld_%s", area2, name);
  _process2.setName(buffer);
 
  sprintf(buffer, "area%ld_load_%s", area2, name);
  _load2.setName(buffer);
  
  sprintf(buffer, "stock_load_%s", name);
  _unloadS.setName(buffer);
 
}
 
Job::~Job()
{}
 
void Job::addToModel(IloModel model, 
                     IloStateResource trolley,
                     IloNumVar makespan) 
{
  /* ADD MACHINE REQUIREMENT CONSTRAINTS */
  model.add(_process1.requires(_machine1));
  model.add(_process2.requires(_machine2));
 
  /* ADD TEMPORAL CONSTRAINTS BETWEEN ACTIVITIES */
  model.add(_unload1.startsAfterEnd(_loadA));
  model.add(_process1.startsAfterEnd(_unload1));
  model.add(_load1.startsAfterEnd(_process1));
  model.add(_unload2.startsAfterEnd(_load1));
  model.add(_process2.startsAfterEnd(_unload2));
  model.add(_load2.startsAfterEnd(_process2));
  model.add(_unloadS.startsAfterEnd(_load2));
 
  /* ADD TROLLEY POSITION REQUIREMENTS  */
  model.add(_loadA.requires(trolley, (IloAny)AREAA));
  model.add(_unload1.requires(trolley, (IloAny)_area1));
  model.add(_load1.requires(trolley, (IloAny)_area1));
  model.add(_unload2.requires(trolley, (IloAny)_area2));
  model.add(_load2.requires(trolley, (IloAny)_area2));
  model.add(_unloadS.requires(trolley, (IloAny)AREAS));
 
  /* ADD MAKESPAN CONSTRAINT */
  model.add(_unloadS.endsBefore(makespan));
}
 
void Job::printSolution(IlcScheduler scheduler, ILOSTD(ostream)& out) 
{
  /* PRINT JOB */
  out
    << "JOB " << _name << endl
    << "\t Load at area A: " 
    << scheduler.getActivity( _loadA ) << endl
    << "\t Unload at area " << (long)_area1 << ": " 
    << scheduler.getActivity( _unload1 )   << endl
    << "\t Process on machine " << (long)_area1 << ": " 
    << scheduler.getActivity( _process1 )  << endl
    << "\t Load at area "   << (long)_area1 << ": " 
    << scheduler.getActivity( _load1 )     << endl
    << "\t Unload at area " << (long)_area2 << ": " 
    << scheduler.getActivity( _unload2 )   << endl
    << "\t Process on machine " << (long)_area2 << ": " 
    << scheduler.getActivity( _process2 )  << endl
    << "\t Load at area "   << (long)_area2 << " : " 
    << scheduler.getActivity( _load2 )     << endl
    << "\t Unload at area S: "
    << scheduler.getActivity( _unloadS )   << endl;
}
 
///////////////////////////////////////////////////////////////////////////////
//
// PROBLEM DEFINITION
//
///////////////////////////////////////////////////////////////////////////////
 
#if defined(ILO_SDXLOUTPUT)
#include "sdxltrolley.h"
#endif
 
IloModel DefineModel(IloEnv env,
                     const char** jobNames,
                     IloInt*      machines1,
                     IloNum*      durations1,
                     IloInt*      machines2,
                     IloNum*      durations2,
                     IloAnyArray&  jobs,
                     IloStateResource& trolley,
                     IloArray<IloUnaryResource>& machines,
                     IloNumVar&   makespan)
{
  IloInt i;
  IloModel model(env);
  /* CREATE THE MAKESPAN VARIABLE. */  
  makespan = IloNumVar(env,0,10000,ILOINT);
  /* CREATE THE TROLLEY POSITION RESOURCE */
  IloAnyArray arrayOfPossibleAreas(env,
                                   5,
                                   (IloAny)AREAA,
                                   (IloAny)MACH1,
                                   (IloAny)MACH2,
                                   (IloAny)MACH3,
                                   (IloAny)AREAS);
  IloAnySet setOfPossibleAreas(env,arrayOfPossibleAreas);
  trolley = IloStateResource(env,setOfPossibleAreas, "trolley");
  /* CREATE THE MACHINES RESOURCES */
  char buffer[256];
  machines = IloArray<IloUnaryResource>(env, 3);
  for (i = 0; i < 3; i++) {
    sprintf(buffer, "machine%ld", i + 1);
    machines[i] = IloUnaryResource(env, buffer);
  }
  /* CREATION OF JOB INSTANCES */
  jobs = IloAnyArray(env, numberOfJobs);
  for (i = 0; i < numberOfJobs; i++) {
    Job* job = new (env) Job(env,
                             jobNames[i],
                             loadDuration,
                             machines[machines1[i] - 1], 
                             durations1[i], machines1[i], 
                             machines[machines2[i] - 1], 
                             durations2[i], machines2[i]);
    jobs[i] = job;
    job->addToModel(model, trolley, makespan);
  }
  /* WE LOOK FOR AN OPTIMAL SOLUTION */
  model.add(IloMinimize(env, makespan));
  /* RETURN THE CREATED MODEL */
  return model;
}
        
 
///////////////////////////////////////////////////////////////////////////////
//
// PRINTING OF SOLUTIONS
//
///////////////////////////////////////////////////////////////////////////////
 
void PrintSolution(IloSolver solver,
                   IloAnyArray jobs,
                   IloStateResource trolley,
                   IloArray<IloUnaryResource> machines,
                   IloNumVar makespan)
{
  IlcScheduler scheduler(solver);
 
  solver.out() << "Solution with makespan " << solver.getMin(makespan) << endl;
  IloInt numberOfJobs = jobs.getSize();
  for (IloInt i = 0; i < numberOfJobs; i++)
    ((Job*) jobs[i])->printSolution(scheduler, solver.out());
 
  // Output from algorithm
  solver.out() << "TROLLEY POSITIONS: " << endl;
 
  IlcAnyTimetable tt = scheduler.getStateResource(trolley).getTimetable();
  for (IlcAnyTimetableCursor cr(tt,0); cr.ok(); ++cr)
    if (cr.isBound())
      solver.out() << "\t [" << cr.getTimeMin()
                   << "," << cr.getTimeMax() 
                   << "): Position " << (long)cr.getValue()
                   << endl;
  solver.printInformation();
 
#if defined(ILO_SDXLOUTPUT)
  IloSDXLTrolleyOutput output(solver.getEnv());
  ofstream outFile("trolley1.xml");
  output.writeTrolley(scheduler, 
                      outFile, 
                      jobs, 
                      trolley,
                      (IloInt) 1000,
                      machines, 
                      makespan);
  outFile.close();
#endif 
  
}
///////////////////////////////////////////////////////////////////////////////
//
// MAIN FUNCTION
//
///////////////////////////////////////////////////////////////////////////////
 
int main() {
  try {
    IloEnv env;
    IloAnyArray jobs;
    IloStateResource trolley;
    IloArray<IloUnaryResource> machines;
    IloNumVar makespan;
    IloModel model = DefineModel(env,
        JobNames,
        Machines1, Durations1,
        Machines2, Durations2,
        jobs,
        trolley,
        machines,
        makespan);
 
     IloSolver solver(model);
     IlcScheduler scheduler(solver);
     IloGoal goal = IloSetTimesForward(env, makespan);
 
     if (solver.solve(goal)) {
       PrintSolution(solver,jobs,trolley,machines,makespan);
     }
     else
       solver.out() << "No Solution" << endl;
 
     env.end();
 
  } catch (IloException& exc) {
    cout << exc << endl;
  }
  return 0;
}
 
 
///////////////////////////////////////////////////////////////////////////////
//
// RESULTS
//
///////////////////////////////////////////////////////////////////////////////
 
/*
  Solution with makespan 560
  JOB J1
         Load at area A: [0 -- 20 --> 20]
         Unload at area 1: [60 -- 20 --> 80]
         Process on machine 1: [240 -- 80 --> 320]
         Load at area 1: [320 -- 20 --> 340]
         Unload at area 2: [360 -- 20 --> 380]
         Process on machine 2: [460 -- 60 --> 520]
         Load at area 2 : [520 -- 20 --> 540]
         Unload at area S: [540 -- 20 --> 560]
  JOB J2
         Load at area A: [0 -- 20 --> 20]
         Unload at area 2: [20 -- 20 --> 40]
         Process on machine 2: [40 -- 120 --> 160]
         Load at area 2: [160 -- 20 --> 180]
         Unload at area 3: [180 -- 20 --> 200]
         Process on machine 3: [240 -- 80 --> 320]
         Load at area 3 : [340 -- 20 --> 360]
         Unload at area S: [440 -- 20 --> 460]
  JOB J3
         Load at area A: [0 -- 20 --> 20]
         Unload at area 2: [20 -- 20 --> 40]
         Process on machine 2: [300 -- 80 --> 380]
         Load at area 2: [380 -- 20 --> 400]
         Unload at area 1: [400 -- 20 --> 420]
         Process on machine 1: [420 -- 60 --> 480]
         Load at area 1 : [500 -- 20 --> 520]
         Unload at area S: [540 -- 20 --> 560]
  JOB J4
         Load at area A: [0 -- 20 --> 20]
         Unload at area 1: [60 -- 20 --> 80]
         Process on machine 1: [80 -- 160 --> 240]
         Load at area 1: [240 -- 20 --> 260]
         Unload at area 3: [260 -- 20 --> 280]
         Process on machine 3: [320 -- 100 --> 420]
         Load at area 3 : [420 -- 20 --> 440]
         Unload at area S: [440 -- 20 --> 460]
  JOB J5
         Load at area A: [0 -- 20 --> 20]
         Unload at area 3: [40 -- 20 --> 60]
         Process on machine 3: [60 -- 180 --> 240]
         Load at area 3: [260 -- 20 --> 280]
         Unload at area 2: [280 -- 20 --> 300]
         Process on machine 2: [380 -- 80 --> 460]
         Load at area 2 : [460 -- 20 --> 480]
         Unload at area S: [540 -- 20 --> 560]
  JOB J6
         Load at area A: [0 -- 20 --> 20]
         Unload at area 2: [20 -- 20 --> 40]
         Process on machine 2: [160 -- 140 --> 300]
         Load at area 2: [300 -- 20 --> 320]
         Unload at area 3: [340 -- 20 --> 360]
         Process on machine 3: [420 -- 60 --> 480]
         Load at area 3 : [480 -- 20 --> 500]
         Unload at area S: [540 -- 20 --> 560]
  TROLLEY POSITIONS: 
         [0,20): Position 4
         [20,40): Position 2
         [40,60): Position 3
         [60,80): Position 1
         [160,180): Position 2
         [180,200): Position 3
         [240,260): Position 1
         [260,280): Position 3
         [280,320): Position 2
         [320,340): Position 1
         [340,360): Position 3
         [360,400): Position 2
         [400,420): Position 1
         [420,440): Position 3
         [440,460): Position 5
         [460,480): Position 2
         [480,500): Position 3
         [500,520): Position 1
         [520,540): Position 2
         [540,560): Position 5
*/
         

This optimal solution is represented in Figure 23.2. The bottom line of the figure shows the positions of the trolley over time.

schedulingStateRes1bn2.gif

Figure 23.2 An Optimal Solution for the First Version of the Trolley Problem