You can see the entire program bridgeov.cpp here or view it online in the standard distribution.
#include <ilsched/iloscheduler.h>
ILOSTLBEGIN
///////////////////////////////////////////////////////////////////////////////
//
// PROBLEM DEFINITION
//
///////////////////////////////////////////////////////////////////////////////
IloInt DueDates [] ={ 8, 5, 12, 12, 18, 24, // A1 -> A6
35, 17, // P1 -> P2
18, 10, 38, 23, 26, 37, // S1 -> S6
19, 11, 43, 20, 28, 38, // B1 -> B6
20, 13, 43, 26, 28, 39, // AB1 -> AB6
33, 22, 60, 53, 44, 80, // M1 -> M6
49, 105, 77, 65, 93, // T1 -> T5
60, 102, // V1 -> V2
32, // L
12, // UE
105, // UA
110}; // PE
const IloInt NumberOfActivities = 43;
IloActivity
MakeActivity(IloModel model,
const char* name,
IloInt duration)
{
IloEnv env = model.getEnv();
IloActivity activity(env, duration, name);
return activity;
}
IloUnaryResource
MakeResource(IloModel model,
const char* name,
IloInt numberOfActivities,
IloActivityArray activities)
{
IloEnv env = model.getEnv();
IloUnaryResource resource(env, name);
for (IloInt i = 0; i < numberOfActivities; i++) {
model.add(activities[i].requires(resource));
}
return resource;
}
IloModel
DefineModel(IloEnv env,
IloInt* dueDates,
IloNumVar& makespan,
IloInt numberOfActivities) {
/* CREATE THE SCHEDULE. */
IloModel model(env);
IloSchedulerEnv schedEnv(env);
schedEnv.getResourceParam().setCapacityEnforcement(IloMediumHigh);
IloInt horizon = 365;
schedEnv.setHorizon(horizon);
/* CREATE ACTIVITIES AND RESOURCES: EXCAVATIONS. */
IloActivity A1 = MakeActivity(model, "A1", 4);
IloActivity A2 = MakeActivity(model, "A2", 2);
IloActivity A3 = MakeActivity(model, "A3", 2);
IloActivity A4 = MakeActivity(model, "A4", 2);
IloActivity A5 = MakeActivity(model, "A5", 2);
IloActivity A6 = MakeActivity(model, "A6", 5);
IloActivityArray A(env,6);
A[0]=A1; A[1]=A2; A[2]=A3; A[3]=A4; A[4]=A5; A[5]=A6;
MakeResource(model, "EXCAVATOR", 6, A);
/* CREATE ACTIVITIES AND RESOURCES: FOUNDATIONS. */
IloActivity P1 = MakeActivity(model, "P1", 20);
IloActivity P2 = MakeActivity(model, "P2", 13);
IloActivityArray P(env,2);
P[0]=P1; P[1]=P2;
MakeResource(model, "PILE DRIVER", 2, P);
/* CREATE ACTIVITIES AND RESOURCES: FORMWORKS. */
IloActivity S1 = MakeActivity(model, "S1", 8);
IloActivity S2 = MakeActivity(model, "S2", 4);
IloActivity S3 = MakeActivity(model, "S3", 4);
IloActivity S4 = MakeActivity(model, "S4", 4);
IloActivity S5 = MakeActivity(model, "S5", 4);
IloActivity S6 = MakeActivity(model, "S6", 10);
IloActivityArray S(env,6);
S[0]=S1; S[1]=S2; S[2]=S3; S[3]=S4; S[4]=S5; S[5]=S6;
MakeResource(model, "CARPENTRY", 6, S);
/* CREATE ACTIVITIES AND RESOURCES: CONCRETE FOUNDATIONS. */
IloActivity B1 = MakeActivity(model, "B1", 1);
IloActivity B2 = MakeActivity(model, "B2", 1);
IloActivity B3 = MakeActivity(model, "B3", 1);
IloActivity B4 = MakeActivity(model, "B4", 1);
IloActivity B5 = MakeActivity(model, "B5", 1);
IloActivity B6 = MakeActivity(model, "B6", 1);
IloActivityArray B(env,6);
B[0]=B1; B[1]=B2; B[2]=B3; B[3]=B4; B[4]=B5; B[5]=B6;
MakeResource(model, "CONCRETE MIXER", 6, B);
/* CREATE ACTIVITIES AND RESOURCES: CONCRETE SETTING TIMES. */
IloActivity AB1 = MakeActivity(model, "AB1", 1);
IloActivity AB2 = MakeActivity(model, "AB2", 1);
IloActivity AB3 = MakeActivity(model, "AB3", 1);
IloActivity AB4 = MakeActivity(model, "AB4", 1);
IloActivity AB5 = MakeActivity(model, "AB5", 1);
IloActivity AB6 = MakeActivity(model, "AB6", 1);
IloActivityArray AB(env,6);
AB[0]=AB1; AB[1]=AB2; AB[2]=AB3; AB[3]=AB4; AB[4]=AB5; AB[5]=AB6;
/* CREATE ACTIVITIES AND RESOURCES: MASONRY. */
IloActivity M1 = MakeActivity(model, "M1", 16);
IloActivity M2 = MakeActivity(model, "M2", 8);
IloActivity M3 = MakeActivity(model, "M3", 8);
IloActivity M4 = MakeActivity(model, "M4", 8);
IloActivity M5 = MakeActivity(model, "M5", 8);
IloActivity M6 = MakeActivity(model, "M6", 20);
IloActivityArray M(env,6);
M[0]=M1; M[1]=M2; M[2]=M3; M[3]=M4; M[4]=M5; M[5]=M6;
MakeResource(model, "BRICKLAYING", 6, M);
/* CREATE ACTIVITIES: POSITIONING. */
IloActivity T1 = MakeActivity(model, "T1", 12);
IloActivity T2 = MakeActivity(model, "T2", 12);
IloActivity T3 = MakeActivity(model, "T3", 12);
IloActivity T4 = MakeActivity(model, "T4", 12);
IloActivity T5 = MakeActivity(model, "T5", 12);
IloActivityArray T(env,5);
T[0]=T1; T[1]=T2; T[2]=T3; T[3]=T4; T[4]=T5;
MakeResource(model, "CRANE", 5, T);
/* CREATE ACTIVITIES: FILLING. */
IloActivity V1 = MakeActivity(model, "V1", 15);
IloActivity V2 = MakeActivity(model, "V2", 10);
IloActivityArray V(env,2);
V[0]=V1; V[1]=V2;
MakeResource(model, "CATERPILLAR", 2, V);
IloActivity PE = MakeActivity(model, "PE", 0);
makespan = IloNumVar(env, 0, IloInfinity, ILOINT);
model.add(PE.endsAt(makespan));
/* CREATE ACTIVITIES: DELIVERY OF THE PREFORMED BEARERS. */
IloActivity L = MakeActivity(model, "L", 2);
/* CREATE ACTIVITIES: REMOVAL OF THE TEMPORARY HOUSINGS. */
IloActivity UE = MakeActivity(model, "UE", 10);
IloActivity UA = MakeActivity(model, "UA", 10);
/* CREATE ACTIVITIES: PROJECT END. THE makespan POINTER IS SET TO
THE END-TIME VARIABLE OF THE PROJECT END. */
/* DELIVERY OF THE PREFORMED BEARERS OCCURS EXACTLY 30 DAYS AFTER
THE BEGINNING OF THE PROJECT. */
L.setStartMin(30);
IloInt k;
for(k = 0; k < 5; k++) {
/* POSITIONING STARTS AFTER THE DELIVERY OF THE PREFORMED BEARERS. */
model.add(T[k].startsAfterEnd(L));
/* MASONRY WORKS M[k] AND M[k + 1] PRECEDE POSITIONING T[k]. */
model.add(T[k].startsAfterEnd(M[k]));
model.add(T[k].startsAfterEnd(M[k + 1]));
}
for(k = 0; k < 6; k++) {
/* FORMWORKS Sk PRECEDE CONCRETE FOUNDATIONS Bk. */
model.add(B[k].startsAfterEnd(S[k]));
/* CONCRETE FOUNDATIONS Bk PRECEDE CONCRETE SETTING TIMES ABk. */
model.add(AB[k].startsAfterEnd(B[k]));
/* CONCRETE SETTING TIMES ABk PRECEDE MASONRIES Mk. */
model.add(M[k].startsAfterEnd(AB[k]));
/* THE TIME BETWEEN THE COMPLETION OF A FORMWORK Sk AND THE
COMPLETION OF ITS CORRESPONDING CONCRETE FOUNDATION Bk IS AT
MOST 4 DAYS. */
model.add(S[k].endsAfterEnd(B[k], -4));
/* FORMWORKS Sk MUST BEGIN AT LEAST SIX DAYS AFTER THE BEGINNING
OF ERECTION OF TEMPORARY HOUSING UE. */
model.add(S[k].startsAfterStart(UE, 6));
/* THE REMOVAL OF THE TEMPORARY HOUSING UA CAN START TWO DAYS
BEFORE THE END OF THE LAST MASONRY WORK. */
model.add(UA.startsAfterEnd(M[k], -2));
}
/* EXCAVATIONS PRECEDE FOUNDATIONS. */
model.add(P1.startsAfterEnd(A3));
model.add(P2.startsAfterEnd(A4));
/* EXCAVATIONS AND FOUNDATIONS PRECEDE FORMWORKS. */
model.add(S1.startsAfterEnd(A1));
model.add(S2.startsAfterEnd(A2));
model.add(S3.startsAfterEnd(P1));
model.add(S4.startsAfterEnd(P2));
model.add(S5.startsAfterEnd(A5));
model.add(S6.startsAfterEnd(A6));
/* POSITIONING OF BEARERS PRECEDE FILLING. */
model.add(V1.startsAfterEnd(T1));
model.add(V2.startsAfterEnd(T5));
/* THERE ARE AT MOST THREE DAYS BEFORE THE END OF A PARTICULAR
EXCAVATION (OR FOUNDATION PILES) AND THE BEGINNING OF THE
CORRESPONDING FORMWORK. */
model.add(A1.endsAfterStart(S1, -3));
model.add(A2.endsAfterStart(S2, -3));
model.add(P1.endsAfterStart(S3, -3));
model.add(P2.endsAfterStart(S4, -3));
model.add(A5.endsAfterStart(S5, -3));
model.add(A6.endsAfterStart(S6, -3));
/* PROJECT END. */
model.add(PE.startsAfterEnd(V1));
model.add(PE.startsAfterEnd(T2));
model.add(PE.startsAfterEnd(T3));
model.add(PE.startsAfterEnd(T4));
model.add(PE.startsAfterEnd(V2));
model.add(PE.startsAfterEnd(UA));
IloActivityArray activities(env,numberOfActivities);
activities[0] = A1; activities[1] = A2; activities[2] = A3;
activities[3] = A4; activities[4] = A5; activities[5] = A6;
activities[6] = P1; activities[7] = P2;
activities[8] = S1; activities[9] = S2; activities[10] = S3;
activities[11] = S4; activities[12] = S5; activities[13] = S6;
activities[14] = B1; activities[15] = B2; activities[16] = B3;
activities[17] = B4; activities[18] = B5; activities[19] = B6;
activities[20] = AB1; activities[21] = AB2; activities[22] = AB3;
activities[23] = AB4; activities[24] = AB5; activities[25] = AB6;
activities[26] = M1; activities[27] = M2; activities[28] = M3;
activities[29] = M4; activities[30] = M5; activities[31] = M6;
activities[32] = T1; activities[33] = T2; activities[34] = T3;
activities[35] = T4; activities[36] = T5;
activities[37] = V1; activities[38] = V2; activities[39] = L;
activities[40] = UE; activities[41] = UA; activities[42] = PE;
/* DUE DATES */
IloInt i;
for (i = 0 ; i < numberOfActivities ; i++) {
activities[i].setEndMax(dueDates[i]);
activities[i].setObject(&(dueDates[i]));
}
/* RETURN THE CREATED SCHEDULE. */
return model;
}
///////////////////////////////////////////////////////////////////////////////
//
// PRINTING OF SOLUTIONS
//
///////////////////////////////////////////////////////////////////////////////
void
PrintSolution(const IloSolver& solver)
{
IlcScheduler scheduler(solver);
IloEnv env = solver.getEnv();
for(IloIterator<IloActivity> ite(env); ite.ok(); ++ite) {
IloActivity act = *ite;
solver.out() << scheduler.getActivity(act);
IloInt dueDate = *((IloInt *)act.getObject());
if (scheduler.getActivity(act).getEndMin() > dueDate) {
solver.out() << " <- violated due date: " << dueDate;
}
solver.out() << endl;
}
}
void
PrintOverlappingActivities(const IloSolver& solver)
{
IlcScheduler scheduler(solver);
for (IlcResourceIterator resIter(scheduler); resIter.ok() ; ++resIter) {
for (IlcResourceConstraintIterator RCiter(*resIter);
RCiter.ok();
++RCiter) {
IlcActivity act = RCiter.getActivity();
for (IlcResourceConstraintIterator RCiter2(*resIter);
RCiter2.ok();
++RCiter2) {
IlcActivity act2 = RCiter2.getActivity();
if (act == act2)
break;
IlcInt endMin1 = act.getEndMin();
IlcInt startMax1 = act.getStartMax();
if (endMin1 > startMax1) {
IlcInt endMin2 = act2.getEndMin();
IlcInt startMax2 = act2.getStartMax();
if (endMin2 > startMax2)
if ((startMax1 < endMin2) && (startMax2 < endMin1))
solver.out() << act << " and " << act2 << " overlap " << endl;
}
}
}
}
}
///////////////////////////////////////////////////////////////////////////////
//
// MAIN FUNCTION
//
///////////////////////////////////////////////////////////////////////////////
int main()
{
try {
IloEnv env;
IloNumVar makespan;
IloModel model = DefineModel(env,
DueDates,
makespan,
NumberOfActivities);
IloSolver solver(model);
IloGoal goal = IloRankForward(env, makespan);
IlcScheduler scheduler(solver);
/* FIRST TRY: TARGETED DUE DATES */
solver.out() << endl << "----------------------------------------" << endl;
solver.out() << "First try: targeted due dates" << endl;
if (solver.solve(goal)) {
solver.out() << "current value of makespan: "
<< solver.getMin(makespan) << endl;
PrintSolution(solver);
}
else
solver.out() << "No solution! " << endl;
/* SECOND TRY: RELAXED CAPACITIES */
IloSchedulerEnv schedEnv(env);
IloResourceParam resParam = schedEnv.getResourceParam();
resParam.ignoreCapacityConstraints(IloTrue);
solver.out() << endl << "----------------------------------------" << endl;
solver.out() << "Second try: relaxed capacities" << endl;
if (solver.solve(goal)) {
solver.out() << "current value of makespan: " << solver.getMin(makespan)
<< endl;
solver.out() << "Overlapping activities: " << endl;
PrintOverlappingActivities(solver);
for(IloIterator<IloActivity> iter(env); iter.ok(); ++iter) {
IloActivity act = *iter;
act.setEndMin(scheduler.getActivity(act).getEndMin());
}
}
else
solver.out() << "No solution! " << endl;
/* THIRD TRY: SOME DUE DATES ARE INCREMENTALLY REMOVED */
resParam.ignoreCapacityConstraints(IloFalse);
solver.out() << endl << "----------------------------------------" << endl;
solver.out() << "Third try: some due dates are incrementally removed "
<< endl;
IloInt j;
for (j=0 ; j < 99 ; j++) {
solver.out() << endl << "Pass number " << j+1 << endl;
for(IloIterator<IloActivity> iter(env); iter.ok(); ++iter) {
IloActivity act = *iter;
IloInt ub = (IloInt)act.getEndMax();
IloInt lb = (IloInt)act.getEndMin();
if (ub - lb <= j) {
solver.out() << "\tRemove [" << act.getName() << " ends before "
<< ub << "]" << endl;
act.setEndMax(IloIntMax);
}
}
if (solver.solve(goal)) {
solver.out() << "\tcurrent value of makespan: "
<< solver.getMin(makespan) << endl;
solver.out() << "\tSolution: " << endl;
PrintSolution(solver);
break;
}
else
solver.out() << "\tNo solution! " << endl;
}
solver.out() << endl << "----------------------------------------" << endl;
solver.out() << "Statistics: " << endl;
solver.printInformation();
env.end();
} catch (IloException& exc) {
cout << exc << endl;
}
return 0;
}
///////////////////////////////////////////////////////////////////////////////
//
// RESULTS
//
///////////////////////////////////////////////////////////////////////////////
/*
----------------------------------------
First try: targeted due dates
No solution!
----------------------------------------
Second try: relaxed capacities
current value of makespan: 60
Overlapping activities:
V1 [44..45 -- 15 --> 59..60] and V2 [50 -- 10 --> 60] overlap
T1 [32..33 -- 12 --> 44..45] and T5 [38 -- 12 --> 50] overlap
M2 [12..14 -- 8 --> 20..22] and M6 [18 -- 20 --> 38] overlap
M1 [16..17 -- 16 --> 32..33] and M6 [18 -- 20 --> 38] overlap
M1 [16..17 -- 16 --> 32..33] and M2 [12..14 -- 8 --> 20..22] overlap
S4 [15 -- 4 --> 19] and S6 [6 -- 10 --> 16] overlap
S2 [6 -- 4 --> 10] and S6 [6 -- 10 --> 16] overlap
S1 [6..7 -- 8 --> 14..15] and S6 [6 -- 10 --> 16] overlap
S1 [6..7 -- 8 --> 14..15] and S2 [6 -- 4 --> 10] overlap
P1 [2..14 -- 20 --> 22..34] and P2 [2 -- 13 --> 15] overlap
A4 [0 -- 2 --> 2] and A6 [0..1 -- 5 --> 5..6] overlap
A1 [0..3 -- 4 --> 4..7] and A6 [0..1 -- 5 --> 5..6] overlap
----------------------------------------
Third try: some due dates are incrementally removed
Pass number 1
Remove [S2 ends before 10]
Remove [B2 ends before 11]
Remove [B4 ends before 20]
Remove [L ends before 32]
No solution!
Pass number 2
Remove [AB2 ends before 13]
Remove [M1 ends before 33]
Remove [V1 ends before 60]
No solution!
Pass number 3
Remove [A2 ends before 5]
Remove [P2 ends before 17]
Remove [M2 ends before 22]
Remove [UE ends before 12]
No solution!
Pass number 4
No solution!
Pass number 5
Remove [A1 ends before 8]
Remove [S1 ends before 18]
Remove [S4 ends before 23]
Remove [B1 ends before 19]
Remove [AB1 ends before 20]
No solution!
Pass number 6
Remove [AB4 ends before 26]
Remove [T1 ends before 49]
current value of makespan: 104
Solution:
A1 [4..6 -- 4 --> 8..10]
A2 [2..4 -- 2 --> 4..6]
A3 [0..1 -- 2 --> 2..3]
A4 [8..10 -- 2 --> 10..12]
A5 [13..16 -- 2 --> 15..18]
A6 [18..19 -- 5 --> 23..24]
P1 [2..3 -- 20 --> 22..23]
P2 [22..25 -- 13 --> 35..38] <- violated due date: 17
S1 [10 -- 8 --> 18]
S2 [6 -- 4 --> 10]
S3 [22..23 -- 4 --> 26..27]
S4 [36..38 -- 4 --> 40..42] <- violated due date: 23
S5 [18..19 -- 4 --> 22..23]
S6 [26..27 -- 10 --> 36..37]
B1 [18 -- 1 --> 19]
B2 [10 -- 1 --> 11]
B3 [26..30 -- 1 --> 27..31]
B4 [40..42 -- 1 --> 41..43] <- violated due date: 20
B5 [22..26 -- 1 --> 23..27]
B6 [36..37 -- 1 --> 37..38]
AB1 [19 -- 1 --> 20]
AB2 [11 -- 1 --> 12]
AB3 [27..42 -- 1 --> 28..43]
AB4 [41..43 -- 1 --> 42..44] <- violated due date: 26
AB5 [23..27 -- 1 --> 24..28]
AB6 [37..38 -- 1 --> 38..39]
M1 [20 -- 16 --> 36] <- violated due date: 33
M2 [12 -- 8 --> 20]
M3 [52 -- 8 --> 60]
M4 [44 -- 8 --> 52]
M5 [36 -- 8 --> 44]
M6 [60 -- 20 --> 80]
T1 [36..41 -- 12 --> 48..53]
T2 [92 -- 12 --> 104]
T3 [64..65 -- 12 --> 76..77]
T4 [52..53 -- 12 --> 64..65]
T5 [80 -- 12 --> 92]
V1 [48..77 -- 15 --> 63..92] <- violated due date: 60
V2 [92 -- 10 --> 102]
PE [104 -- 0 --> 104]
L [30..39 -- 2 --> 32..41]
UE [0 -- 10 --> 10]
UA [78..94 -- 10 --> 88..104]
*/
PREVIOUS
NEXT