IBM ILOG Scheduler User's Manual > Integrated Applications > A Randomizing Algorithm: the Job-Shop Problem > Complete Program and Output

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

#include <ilsched/iloscheduler.h>
 
ILOSTLBEGIN
 
IloInt ResourceNumbers06 [] = {2, 0, 1, 3, 5, 4,
                               1, 2, 4, 5, 0, 3,
                               2, 3, 5, 0, 1, 4,
                               1, 0, 2, 3, 4, 5,
                               2, 1, 4, 5, 0, 3,
                               1, 3, 5, 0, 4, 2};
 
IloInt Durations06 [] = { 1,  3,  6,  7,  3,  6,
                          8,  5, 10, 10, 10,  4,
                          5,  4,  8,  9,  1,  7,
                          5,  5,  5,  3,  8,  9,
                          9,  3,  5,  4,  3,  1,
                          3,  3,  9, 10,  4,  1};
 
IloInt ResourceNumbers10 [] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9,
                               0, 2, 4, 9, 3, 1, 6, 5, 7, 8,
                               1, 0, 3, 2, 8, 5, 7, 6, 9, 4,
                               1, 2, 0, 4, 6, 8, 7, 3, 9, 5,
                               2, 0, 1, 5, 3, 4, 8, 7, 9, 6,
                               2, 1, 5, 3, 8, 9, 0, 6, 4, 7,
                               1, 0, 3, 2, 6, 5, 9, 8, 7, 4,
                               2, 0, 1, 5, 4, 6, 8, 9, 7, 3,
                               0, 1, 3, 5, 2, 9, 6, 7, 4, 8,
                               1, 0, 2, 6, 8, 9, 5, 3, 4, 7};
 
IloInt Durations10 [] = {29, 78,  9, 36, 49, 11, 62, 56, 44, 21,
                         43, 90, 75, 11, 69, 28, 46, 46, 72, 30,
                         91, 85, 39, 74, 90, 10, 12, 89, 45, 33,
                         81, 95, 71, 99,  9, 52, 85, 98, 22, 43,
                         14,  6, 22, 61, 26, 69, 21, 49, 72, 53,
                         84,  2, 52, 95, 48, 72, 47, 65,  6, 25,
                         46, 37, 61, 13, 32, 21, 32, 89, 30, 55,
                         31, 86, 46, 74, 32, 88, 19, 48, 36, 79,
                         76, 69, 76, 51, 85, 11, 40, 89, 26, 74,
                         85, 13, 61,  7, 64, 76, 47, 52, 90, 45};
 
IloInt ResourceNumbers20 [] = {0, 1, 2, 3, 4,
                               0, 1, 3, 2, 4,
                               1, 0, 2, 4, 3,
                               1, 0, 4, 2, 3,
                               2, 1, 0, 3, 4,
                               2, 1, 4, 0, 3,
                               1, 0, 2, 3, 4,
                               2, 1, 0, 3, 4,
                               0, 3, 2, 1, 4,
                               1, 2, 0, 3, 4,
                               1, 3, 0, 4, 2,
                               2, 0, 1, 3, 4,
                               0, 2, 1, 3, 4,
                               2, 0, 1, 3, 4,
                               0, 1, 4, 2, 3,
                               1, 0, 3, 4, 2,
                               0, 2, 1, 3, 4,
                               0, 1, 4, 2, 3,
                               1, 2, 0, 3, 4,
                               0, 1, 2, 3, 4};
 
IloInt Durations20 [] = {29,  9, 49, 62, 44,
                         43, 75, 69, 46, 72,
                         91, 39, 90, 12, 45,
                         81, 71,  9, 85, 22,
                         14, 22, 26, 21, 72,
                         84, 52, 48, 47,  6,
                         46, 61, 32, 32, 30,
                         31, 46, 32, 19, 36,
                         76, 76, 85, 40, 26,
                         85, 61, 64, 47, 90,
                         78, 36, 11, 56, 21,
                         90, 11, 28, 46, 30,
                         85, 74, 10, 89, 33,
                         95, 99, 52, 98, 43,
                          6, 61, 69, 49, 53,
                          2, 95, 72, 65, 25,
                         37, 13, 21, 89, 55,
                         86, 74, 88, 48, 79,
                         69, 51, 11, 89, 74,
                         13,  7, 76, 52, 45};
 
///////////////////////////////////////////////////////////////////////////////
//
// PROBLEM DEFINITION
//
///////////////////////////////////////////////////////////////////////////////
 
IloModel
DefineModel(IloEnv& env,
            IloInt numberOfJobs,
            IloInt numberOfResources,        
            IloInt* resourceNumbers,
            IloInt* durations,
            IloNumVar& makespan,
            IloSchedulerSolution& solution)
{
  IloModel model(env);
 
  /* CREATE THE MAKESPAN VARIABLE. */
  IloInt numberOfActivities = numberOfJobs * numberOfResources;
  IloInt horizon = 0;
  IloInt k;
 
  for (k = 0; k < numberOfActivities; k++)
    horizon += durations[k];
 
  makespan = IloNumVar(env, 0, horizon, ILOINT);
  solution = IloSchedulerSolution(env);
 
  /* CREATE THE RESOURCES. */
  IloSchedulerEnv schedEnv(env);
  schedEnv.getResourceParam().setCapacityEnforcement(IloMediumHigh);
 
  IloInt j;
  IloUnaryResource *resources = 
    new (env) IloUnaryResource[numberOfResources];
  for (j = 0; j < numberOfResources; j++)
    resources[j] = IloUnaryResource(env);
 
  /* CREATE THE ACTIVITIES. */
  char buffer[128];
  k = 0;
  IloInt i;
  for (i = 0; i < numberOfJobs; i++) {
    IloActivity previousActivity;
    for (j = 0; j < numberOfResources; j++) {
      IloActivity activity(env, durations[k]);
      sprintf(buffer, "J%ldS%ldR%ld", i, j, resourceNumbers[k]);
      activity.setName(buffer);
      model.add(activity.requires(resources[resourceNumbers[k]]));
      if (j != 0)
        model.add(activity.startsAfterEnd(previousActivity));
      solution.add(activity);
      previousActivity = activity;
      k++;
    }
    model.add(previousActivity.endsBefore(makespan));
  }
 
  /* RETURN THE MODEL. */
  return model;
}
 
 
///////////////////////////////////////////////////////////////////////////////
//
// PRINTING OF SOLUTIONS
//
///////////////////////////////////////////////////////////////////////////////
 
void
PrintSolution(const IloSchedulerSolution& solution)
{
  IloEnv env = solution.getEnv();
  for(IloSchedulerSolution::ActivityIterator ite(solution); 
  ite.ok(); ++ite) {
    IloActivity act = *ite;
    env.out() << act.getName() << " [";
    env.out() << solution.getStartMin(act) << " -- ";
    env.out() << solution.getDurationMin(act) << " -- ";
    env.out() << solution.getEndMin(act) << "]" << endl;
  }
}
 
///////////////////////////////////////////////////////////////////////////////
//
// PROBLEM SOLVING
//
///////////////////////////////////////////////////////////////////////////////
 
IlcInt
GetEndMin(IlcSchedule& schedule)
{
  /* COMPUTE THE SMALLEST MINIMAL END TIME OF UNRANKED ACTIVITIES. */
  IlcInt endMin = schedule.getTimeMax() + 1;
  for(IlcUnaryResourceIterator resIte(schedule);
      resIte.ok();
      ++resIte) {
    for (IlcResourceConstraintIterator ite(*resIte,
                                           IlcFromStartToEnd);
         ite.ok(); ++ite) {
      IlcResourceConstraint constraint = *ite;
      if ((constraint.isPossibleFirst())
          && (constraint.getActivity().getEndMin() < endMin))
        endMin = constraint.getActivity().getEndMin();
    }
  }
  return endMin;
}
 
IlcBool
SelectResourceConstraint(IlcResourceConstraint& constraint,
                         IlcSchedule& schedule,
                         IloRandom rand)
{
  IlcInt endMin = GetEndMin(schedule);
  if (schedule.getTimeMax() < endMin)
    return IlcFalse;
  IlcInt chosenNumberOfCandidates = schedule.getNumberOfActivities() +
    1;
  for(IlcUnaryResourceIterator resIte(schedule);
      resIte.ok();
      ++resIte) {
    IlcResourceConstraint bestConstraint;
    IloNum bestValue = -1.0;
    IlcInt numberOfCandidates = 0;
    for (IlcResourceConstraintIterator ite(*resIte,
                                           IlcFromStartToEnd);
         ite.ok(); ++ite) {
      IlcResourceConstraint ct = *ite;
      if (ct.isPossibleFirst()
          && (ct.getActivity().getStartMin() < endMin)) {
        numberOfCandidates++;
        IloNum value = rand.getFloat();
        if (bestValue < value) {
          bestConstraint = ct;
          bestValue = value;
        }
      }
    }
    if ((0 < numberOfCandidates)
        && (numberOfCandidates < chosenNumberOfCandidates)) {
      /* resource IS THE RESOURCE WITH THE SMALLEST NUMBER OF
         CANDIDATES. THE CHOSEN CONSTRAINT BECOMES THE BEST CONSTRAINT
         OF resource. */
      chosenNumberOfCandidates = numberOfCandidates;
      constraint = bestConstraint;
    }
  }
  return IlcTrue;
}
ILCGOAL1(SolveProblemIlc, IloRandom, rand) {
  IloSolver s = getSolver();
  IlcScheduler scheduler = IlcScheduler(s);
  IlcResourceConstraint constraint;
  if (SelectResourceConstraint(constraint, scheduler, rand)) {
    return IlcAnd(IlcTryRankFirst(constraint),
                  this);
  }
  return 0;
}
 
ILOCPGOALWRAPPER1(SolveProblem, solver, IloRandom, rand) {
  return SolveProblemIlc(solver, rand);
}
 
void
MinimizeRandom(IloSolver& solver,
               IloNumVar& makespan,
               IloSchedulerSolution& solution,
               IloInt numberOfIterations,
               IloInt numberOfFailsPerIteration)
{
  IloEnv env = solver.getEnv();
  IlcScheduler sched(solver);
  IloRandom randGen(env);
  IloGoal goal;
 
  /* GENERATE AN INITIAL SOLUTION. */
  goal = IloGoalTrue(solver.getEnv());
  solver.solve(goal);
  IloNum min = solver.getMin(makespan);
  makespan.setLB(min);
 
  goal = SolveProblem(env, randGen);
  solver.solve(goal);
  IloNum max = solver.getMin(makespan);
 
  /* OPTIMIZE. */
  IloInt iteration = 0;
 
  goal = IloLimitSearch(env,
                        SolveProblem(env, randGen),
                        IloFailLimit(env, numberOfFailsPerIteration));
  
  while ((min != max) && (iteration < numberOfIterations)) {
    iteration++;
    IloNum value = IloTrunc((min + iteration * max) / (iteration + 1));
    makespan.setUB(value);
 
    solver.out() << "Trying makespan: " << value << endl;
    if (solver.solve(goal)) {
      max = solver.getMin(makespan);
      solver.out() << "Solution with makespan " << max << endl;
      solution.store(sched);
    }
 
    else if (solver.getNumberOfFails() < numberOfFailsPerIteration) {
      /* ACTUAL FAILURE NOT DUE TO THE LIMITED NUMBER OF FAILS. */
      solver.out() << "Failure with makespan " << value << endl;
      min = value + 1;
    }
    else 
      solver.out() << "Failure from fail limit" << endl;
  }
}
 
///////////////////////////////////////////////////////////////////////////////
//
// MAIN FUNCTION
//
///////////////////////////////////////////////////////////////////////////////
 
void
InitParameters(int argc,
               char** argv,
               IloInt& numberOfJobs,
               IloInt& numberOfResources,                    
               IloInt*& resourceNumbers,
               IloInt*& durations,
               IloInt& numberOfIterations,
               IloInt& numberOfFailsPerIteration)
{
  if (argc > 1) {
    IloInt number = atol(argv[1]);
    if (number == 10) {
      numberOfJobs = 10;
      numberOfResources = 10;
      resourceNumbers = ResourceNumbers10;
      durations = Durations10;
    }
    else if (number == 20) {
      numberOfJobs = 20;
      numberOfResources = 5;
      resourceNumbers = ResourceNumbers20;
      durations = Durations20;
    }
  }
  if (argc > 2)
    numberOfIterations = atol(argv[2]);
  if (argc > 3)
    numberOfFailsPerIteration = atol(argv[3]);
}
 
int main(int argc, char** argv)
{
  try {
    IloEnv env;
 
    IloInt numberOfJobs = 6;
    IloInt numberOfResources = 6;
    IloInt* resourceNumbers = ResourceNumbers06;
    IloInt* durations = Durations06;
    IloInt numberOfIterations = 100;
    IloInt numberOfFailsPerIteration = 10;
    InitParameters(argc,
                   argv,
                   numberOfJobs,
                   numberOfResources,
                   resourceNumbers,
                   durations,
                   numberOfIterations,
                   numberOfFailsPerIteration);
    IloNumVar makespan;
    IloSchedulerSolution solution;
    IloModel model = DefineModel(env,
                                 numberOfJobs,
                                 numberOfResources,
                                 resourceNumbers,
                                 durations,
                                 makespan,
                                 solution);
    IloSolver solver(model);
    MinimizeRandom(solver,
                   makespan,
                   solution,
                   numberOfIterations,
                   numberOfFailsPerIteration);
    PrintSolution(solution);
    solver.printInformation();
    env.end();
  }
  catch (IloException& exc) {
    cout << exc << endl;
  }
 
  return 0;
}
 
///////////////////////////////////////////////////////////////////////////////
//
// RESULTS
//
///////////////////////////////////////////////////////////////////////////////
/*
jobshopr 6
Trying makespan: 61
Solution with makespan 61
Trying makespan: 56
Solution with makespan 56
Trying makespan: 53
Failure with makespan 53
Trying makespan: 55
Solution with makespan 55
Trying makespan: 54
Failure with makespan 54
J0S0R2 [5 -- 1 -- 6]
J0S1R0 [6 -- 3 -- 9]
J0S2R1 [16 -- 6 -- 22]
J0S3R3 [30 -- 7 -- 37]
J0S4R5 [38 -- 3 -- 41]
J0S5R4 [49 -- 6 -- 55]
J1S0R1 [0 -- 8 -- 8]
J1S1R2 [8 -- 5 -- 13]
J1S2R4 [13 -- 10 -- 23]
J1S3R5 [28 -- 10 -- 38]
J1S4R0 [38 -- 10 -- 48]
J1S5R3 [48 -- 4 -- 52]
J2S0R2 [0 -- 5 -- 5]
J2S1R3 [5 -- 4 -- 9]
J2S2R5 [9 -- 8 -- 17]
J2S3R0 [18 -- 9 -- 27]
J2S4R1 [27 -- 1 -- 28]
J2S5R4 [30 -- 7 -- 37]
J3S0R1 [8 -- 5 -- 13]
J3S1R0 [13 -- 5 -- 18]
J3S2R2 [22 -- 5 -- 27]
J3S3R3 [27 -- 3 -- 30]
J3S4R4 [37 -- 8 -- 45]
J3S5R5 [45 -- 9 -- 54]
J4S0R2 [13 -- 9 -- 22]
J4S1R1 [22 -- 3 -- 25]
J4S2R4 [25 -- 5 -- 30]
J4S3R5 [41 -- 4 -- 45]
J4S4R0 [48 -- 3 -- 51]
J4S5R3 [52 -- 1 -- 53]
J5S0R1 [13 -- 3 -- 16]
J5S1R3 [16 -- 3 -- 19]
J5S2R5 [19 -- 9 -- 28]
J5S3R0 [28 -- 10 -- 38]
J5S4R4 [45 -- 4 -- 49]
J5S5R2 [49 -- 1 -- 50]
*/