You can see the entire program jobshopt.cpp here or view it online in the standard distribution.
#include <ilsched/iloscheduler.h>
#include <ilsolver/iimls.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 TransTimes06 [] = { 0, 2, 7, 3, 1, 3,
3, 0, 4, 7, 8, 8,
4, 2, 0, 5, 3, 6,
3, 6, 4, 0, 4, 7,
2, 1, 5, 5, 0, 1,
6, 4, 6, 9, 4, 0};
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 TransTimes10 [] = {0, 9, 8, 1, 4, 3, 9, 2, 3, 7,
6, 0, 7, 5, 6, 1, 2, 1, 2, 3,
2, 3, 0, 3, 4, 3, 1, 9, 2, 2,
2, 7, 3, 0, 8, 7, 6, 4, 2, 1,
8, 3, 9, 8, 0, 5, 4, 9, 2, 3,
3, 2, 1, 3, 2, 0, 3, 2, 3, 9,
9, 8, 7, 4, 3, 8, 0, 6, 3, 4,
8, 7, 2, 1, 5, 3, 1, 0, 8, 2,
3, 9, 8, 5, 7, 1, 3, 2, 0, 9,
4, 8, 1, 2, 6, 4, 7, 2, 3, 0};
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};
IloInt TransTimes20 [] = {0, 3, 2, 9, 7,
3, 0, 2, 9, 5,
6, 4, 0, 5, 4,
1, 2, 3, 0, 7,
1, 9, 6, 4, 0};
///////////////////////////////////////////////////////////////////////////////
//
// PROBLEM DEFINITION
//
///////////////////////////////////////////////////////////////////////////////
class NbUnrankedExt {
private:
IlcInt _nbOfUnranked;
public:
NbUnrankedExt() :_nbOfUnranked(0) {};
~NbUnrankedExt(){};
void setValue(IlcInt nbOfUnranked) {
_nbOfUnranked = nbOfUnranked;
}
IlcInt getValue() const {
return _nbOfUnranked;
}
};
IloModel
DefineModel(IloEnv& env,
IloInt numberOfJobs,
IloInt numberOfResources,
IloInt* resourceNumbers,
IloInt* durations,
IloInt* transTimes,
IloNumVar& makespan)
{
IloModel model(env);
/* CREATE THE MAKESPAN VARIABLE. */
IloInt numberOfActivities = numberOfJobs * numberOfResources;
IloInt horizon = 0;
IloInt k;
IloInt maxTransTime = 0;
for (k = 0; k < numberOfResources*numberOfResources; k++)
if (maxTransTime < transTimes[k])
maxTransTime = transTimes[k];
for (k = 0; k < numberOfActivities; k++)
horizon += durations[k] + maxTransTime;
makespan = IloNumVar(env, 0, horizon, ILOINT);
/* CREATE THE TRANSITION TIMES */
IloTransitionParam ttParam(env, numberOfResources, IloFalse);
IloInt i, j;
for (i = 0; i < numberOfResources; i++)
for (j = 0; j < numberOfResources; j++)
ttParam.setValue(i, j, transTimes[j + (numberOfResources * i)]);
/* CREATE THE RESOURCES. */
IloSchedulerEnv schedEnv(env);
schedEnv.getResourceParam().setCapacityEnforcement(IloMediumHigh);
schedEnv.getResourceParam().setPrecedenceEnforcement(IloMediumHigh);
IloUnaryResource *resources =
new (env) IloUnaryResource[numberOfResources];
for (j = 0; j < numberOfResources; j++) {
IloUnaryResource res = IloUnaryResource(env);
IloTransitionTime( res, ttParam );
resources[j] = res;
}
/* CREATE THE ACTIVITIES. */
char buffer[128];
k = 0;
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);
activity.setTransitionType(j);
IloResourceConstraint rct =
activity.requires(resources[resourceNumbers[k]]);
NbUnrankedExt* nbOfUnranked =
new (env) NbUnrankedExt();
rct.setObject(nbOfUnranked);
model.add(rct);
if (j != 0)
model.add(activity.startsAfterEnd(previousActivity));
previousActivity = activity;
k++;
}
model.add(previousActivity.endsBefore(makespan));
}
/* RETURN THE MODEL. */
return model;
}
///////////////////////////////////////////////////////////////////////////////
//
// PRINTING OF SOLUTIONS
//
///////////////////////////////////////////////////////////////////////////////
void
PrintSolution(IloSolver& solver)
{
IlcScheduler scheduler(solver);
IloEnv env = solver.getEnv();
for(IloIterator<IloActivity> ite(env); ite.ok(); ++ite)
solver.out() << scheduler.getActivity(*ite) << endl;
}
///////////////////////////////////////////////////////////////////////////////
//
// PROBLEM SOLVING
//
///////////////////////////////////////////////////////////////////////////////
IlcInt GetNumberOfUnranked(const IlcResourceConstraint& rct) {
/* RETURN NUMBER OF UNRANKED W.R.T. RCT */
IlcInt nb = 0;
for (IlcResourceConstraintIterator ite(rct, IlcUnranked);
ite.ok(); ++ite)
nb++;
return nb;
}
IlcInt GetOpportunity(
const IlcScheduler& scheduler,
const IlcResourceConstraint& srct1,
const IlcResourceConstraint& srct2) {
IlcActivity act1 = srct1.getActivity();
IlcActivity act2 = srct2.getActivity();
IlcInt smin1 = act1.getStartMin();
IlcInt smax1 = act1.getStartMax();
IlcInt emin1 = act1.getEndMin();
IlcInt emax1 = act1.getEndMax();
IlcInt smin2 = act2.getStartMin();
IlcInt smax2 = act2.getStartMax();
IlcInt emin2 = act2.getEndMin();
IlcInt emax2 = act2.getEndMax();
/* DOMAIN DELTA WHEN RCT1 RANKED BEFORE RCT2 */
IlcInt deltaEnd12 = ((emax1 < smax2) ? OL : emax1 - smax2);
IlcInt deltaStart12 = ((smin2 > emin1) ? OL : emin1 - smin2);
IlcInt delta12 = deltaEnd12 + deltaStart12;
/* DOMAIN DELTA WHEN RCT2 RANKED BEFORE RCT1 */
IlcInt deltaEnd21 = ((emax2 < smax1) ? OL : emax2 - smax1);
IlcInt deltaStart21 = ((smin1 > emin2) ? OL : emin2 - smin1);
IlcInt delta21 = deltaEnd21 + deltaStart21;
/* MINIMAL NUMBER OF UNRANKED RESOURCE CONSTRAINTS */
IlcInt nbUrkd1 = ((NbUnrankedExt*)(scheduler.getExtractable(srct1).getObject()))->getValue();
IlcInt nbUrkd2 = ((NbUnrankedExt*)(scheduler.getExtractable(srct2).getObject()))->getValue();
IlcInt minNbUrkd = (nbUrkd1 <= nbUrkd2) ? nbUrkd1 : nbUrkd2;
/* RETURN MEASURE OF OPPORTUNITY */
return (minNbUrkd * (delta12 - delta21));
}
IlcBool
SelectMostOpportunisticConflict(IlcScheduler& schedule,
IlcResourceConstraint& selectedRct1,
IlcResourceConstraint& selectedRct2) {
IlcBool existsConflict = IlcFalse;
IlcInt oppMaxAbs = -1;
IlcInt oppMax = 0;
IlcInt opp;
for (IlcUnaryResourceIterator ires(schedule); ires.ok(); ++ires) {
IlcUnaryResource resource = (*ires);
if (resource.hasPrecedenceGraphConstraint() &&
!resource.isRanked()) {
/* FOR EACH RESOURCE CONSTRAINT, COMPUTE AND STORE THE NUMBER OF
RESOURCE CONSTRAINTS UNRANKED W.R.T. IT */
for (IlcResourceConstraintIterator irct(resource);
irct.ok(); ++irct) {
IlcResourceConstraint rct = (*irct);
if (!rct.isRanked())
((NbUnrankedExt*)schedule.getExtractable(rct).getObject())->
setValue(GetNumberOfUnranked(rct));
}
/* SELECT MOST OPPORTUNISTIC PAIR OF RESOURCE CONSTRAINT */
for (IlcResourceConstraintIterator isrct1(resource);
isrct1.ok(); ++isrct1) {
IlcResourceConstraint srct1 = (*isrct1);
if (!srct1.isRanked()) {
for (IlcResourceConstraintIterator isrct2(srct1, IlcUnranked);
isrct2.ok(); ++isrct2) {
IlcResourceConstraint srct2 = (*isrct2);
opp = GetOpportunity(schedule, srct1, srct2);
if (oppMaxAbs < IloAbs(opp)) {
existsConflict = IlcTrue;
oppMaxAbs = IlcAbs(opp);
oppMax = opp;
selectedRct1 = srct1;
selectedRct2 = srct2;
}
}
}
}
}
}
/* SELECT WHICH BRANCH WILL BE CHOSEN FIRST AMONG RCT1 << RCT2 AND
RCT2 << RCT1 */
if (existsConflict && (0 < oppMax)) {
IlcResourceConstraint tmpRct = selectedRct1;
selectedRct1 = selectedRct2;
selectedRct2 = tmpRct;
}
return existsConflict;
}
ILCGOAL0(SolveConflictsIlc) {
IloSolver s = getSolver();
IlcScheduler scheduler = IlcScheduler(s);
IlcResourceConstraint srct1;
IlcResourceConstraint srct2;
if (SelectMostOpportunisticConflict(scheduler, srct1, srct2))
return IlcAnd(IlcTrySetSuccessor(srct1, srct2), this);
return 0;
}
ILOCPGOALWRAPPER0(SolveConflicts, solver) {
return SolveConflictsIlc(solver);
}
void
SetMakespanInitialBounds(IloSolver& solver,
IloNumVar& makespan)
{
/* SET MAKESPAN LOWER BOUND AND RESTART */
solver.solve(IloGoalTrue(solver.getEnv()));
makespan.setLB(solver.getMin(makespan));
/* SOLVE WITH GOAL SOLVECONFLICTS */
IloGoal solveConflicts = SolveConflicts(solver.getEnv());
solver.solve(solveConflicts);
/* SET MAKESPAN UPPER BOUND */
makespan.setUB(solver.getMin(makespan));
solver.out() << "Solution with makespan " << makespan.getUB() << endl;
}
void
Dichotomize(IloModel& model,
IloSolver& solver,
const IloNumVar& makespan)
{
/* GET MAKESPAN INITIAL BOUNDS */
IloNum min = makespan.getLB();
IloNum max = makespan.getUB();
/* OPTIMIZE. */
IloGoal goal = IloRankForward(solver.getEnv(),
makespan,
IloSelResMinLocalSlack,
IloSelFirstRCMinStartMax);
while(min < max) {
IloNum value = IloFloor((min + max) / 2);
IloConstraint ct = (makespan <= value);
model.add(ct);
if (solver.solve(goal)) {
max = solver.getMin(makespan);
solver.out() << "Solution with makespan " << max << endl;
}
else {
solver.out() << "Failure with makespan " << value << endl;
min = value + 1;
}
model.remove(ct);
}
/* RECOMPUTE THE OPTIMAL SOLUTION. THIS STEP COULD BE AVOIDED IF
SOLUTIONS WERE STORED AS PART OF THE OPTIMIZATION PROCESS. */
model.add(makespan == max);
solver.solve(goal);
}
///////////////////////////////////////////////////////////////////////////////
//
// MAIN FUNCTION
//
///////////////////////////////////////////////////////////////////////////////
void
InitParameters(int argc,
char** argv,
IloInt& numberOfJobs,
IloInt& numberOfResources,
IloInt*& resourceNumbers,
IloInt*& durations,
IloInt*& transTimes)
{
if (argc > 1) {
IloInt number = atol(argv[1]);
if (number == 10) {
numberOfJobs = 10;
numberOfResources = 10;
resourceNumbers = ResourceNumbers10;
durations = Durations10;
transTimes = TransTimes10;
}
else if (number == 20) {
numberOfJobs = 20;
numberOfResources = 5;
resourceNumbers = ResourceNumbers20;
durations = Durations20;
transTimes = TransTimes20;
}
}
}
int main(int argc, char** argv)
{
try {
IloEnv env;
IloInt numberOfJobs = 6;
IloInt numberOfResources = 6;
IloInt* resourceNumbers = ResourceNumbers06;
IloInt* durations = Durations06;
IloInt* transTimes = TransTimes06;
InitParameters(argc,
argv,
numberOfJobs,
numberOfResources,
resourceNumbers,
durations,
transTimes);
IloNumVar makespan;
IloModel model = DefineModel(env,
numberOfJobs,
numberOfResources,
resourceNumbers,
durations,
transTimes,
makespan);
IloSolver solver(model);
SetMakespanInitialBounds(solver, makespan);
Dichotomize(model, solver, makespan);
PrintSolution(solver);
solver.printInformation();
env.end();
}
catch (IloException& exc) {
cout << exc << endl;
}
return 0;
}
///////////////////////////////////////////////////////////////////////////////
//
// RESULTS
//
///////////////////////////////////////////////////////////////////////////////
/* jobshopt 6
Solution with makespan 71
Failure with makespan 59
Solution with makespan 65
Failure with makespan 62
Failure with makespan 64
J0S0R2 [14..16 -- 1 --> 15..17]
J0S1R0 [15..17 -- 3 --> 18..20]
J0S2R1 [25..39 -- 6 --> 31..45]
J0S3R3 [34..45 -- 7 --> 41..52]
J0S4R5 [50..52 -- 3 --> 53..55]
J0S5R4 [59 -- 6 --> 65]
J1S0R1 [8 -- 8 --> 16]
J1S1R2 [17..21 -- 5 --> 22..26]
J1S2R4 [26 -- 10 --> 36]
J1S3R5 [36..38 -- 10 --> 46..48]
J1S4R0 [48..50 -- 10 --> 58..60]
J1S5R3 [58..60 -- 4 --> 62..64]
J2S0R2 [9..11 -- 5 --> 14..16]
J2S1R3 [14..17 -- 4 --> 18..21]
J2S2R5 [18..21 -- 8 --> 26..29]
J2S3R0 [35..37 -- 9 --> 44..46]
J2S4R1 [44..51 -- 1 --> 45..52]
J2S5R4 [52 -- 7 --> 59]
J3S0R1 [3 -- 5 --> 8]
J3S1R0 [8..12 -- 5 --> 13..17]
J3S2R2 [26..31 -- 5 --> 31..36]
J3S3R3 [31..36 -- 3 --> 34..39]
J3S4R4 [39 -- 8 --> 47]
J3S5R5 [54..56 -- 9 --> 63..65]
J4S0R2 [0..2 -- 9 --> 9..11]
J4S1R1 [18 -- 3 --> 21]
J4S2R4 [21 -- 5 --> 26]
J4S3R5 [31..34 -- 4 --> 35..38]
J4S4R0 [58..61 -- 3 --> 61..64]
J4S5R3 [62..64 -- 1 --> 63..65]
J5S0R1 [0 -- 3 --> 3]
J5S1R3 [3..9 -- 3 --> 6..12]
J5S2R5 [6..12 -- 9 --> 15..21]
J5S3R0 [25..27 -- 10 --> 35..37]
J5S4R4 [47 -- 4 --> 51]
J5S5R2 [51..64 -- 1 --> 52..65]
*/
PREVIOUS
NEXT