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]
*/