IBM ILOG Scheduler User's Manual > Advanced Concepts > Using Strong Propagation on Reservoirs: the Balance Constraint > Complete Program and Output |
Complete Program and Output |
INDEX
![]() |
You can see the entire program balpos.cpp
here or view it in the standard distribution.
#include <ilsched/iloscheduler.h> ILOSTLBEGIN IloInt NumberOfActivities = 15; //---------------------------- PROBLEM 1 ------------------------------------ IloInt Durations01 [] = { 5, 5, 5, 5, 5, 7, 7, 8, 8, 9, 14, 14, 14, 14, 15 }; IloInt NumberOfConstraints01 = 7; IloInt Constraints01 [] = { 14, 15, 5, 4, 6, 24, 0, 3, 38, 1, 11, 117, 1, 8, 83, 4, 8, 50, 8, 14, 59 }; //---------------------------- PROBLEM 2 ------------------------------------ IloInt Durations02 [] = { 5, 7, 7, 8, 8, 8, 8, 10, 10, 10, 11, 11, 13, 14, 15 }; IloInt NumberOfConstraints02 = 7; IloInt Constraints02 [] = { 3, 11, 88, 6, 8, 27, 1, 6, 48, 5, 8, 38, 9, 15, 55, 1, 3, 17, 1, 4, 27 }; //---------------------------- PROBLEM 3 ------------------------------------ IloInt Durations03 [] = { 5, 6, 6, 7, 7, 7, 8, 9, 9, 9, 10, 11, 14, 14, 15 }; IloInt NumberOfConstraints03 = 7; IloInt Constraints03 [] = { 2, 3, 15, 5, 7, 17, 1, 7, 71, 2, 5, 44, 2, 6, 49, 2, 4, 29, 0, 3, 34 }; //----------------------- COMPUTE MAX MAKESPAN ---------------------------- IloNum getMakespanMax(const IloEnv& env, IloInt numberOfActivities, IloInt numberOfConstraints, IloInt* durations, IloInt* constraints) { // THIS FUNCTION COMPUTES AN UPPER BOUND ON THE MAKESPAN BY ASSUMING // ALL THE ACTIVITIES HAVE A DURATION EQUAL TO THE LONGEST ACTIVITY // OF THE PROBLEM. IloModel model(env); IloNumVar makespan(env, 0, IloInfinity, ILOINT); IloInt i, j, k, t; // COMPUTE MAXIMAL DURATION OF ACTIVITIES IloInt dmax = 0; for (i=0; i < numberOfActivities; i++) if (durations[i] > dmax) dmax = durations[i]; IloActivity lact; IloNumExprArray times(env, numberOfActivities+1); for (i=0; i < numberOfActivities; i++) { // USE ACTIVITIES WITH MAXIMAL DURATION IloActivity act(env, dmax); times[i] = act.getStartExpr(); if (i > 0) model.add(act.startsAfterEnd(lact)); lact = act; } model.add(lact.endsBefore(makespan)); times[numberOfActivities] = makespan; // ADD MINIMAL DELAY CONSTRAINTS for (k=0; k < numberOfConstraints; k++) { i = constraints[3*k]; j = constraints[(3*k) + 1]; t = constraints[(3*k) + 2]; model.add(times[j]-times[i] >= t); } // JUST PROPAGATE THE PERT IloSolver solver(model); IlcSearch s = solver.newSearch(IloGoalTrue(env)); s.next(); IloNum makespanMax = solver.getMin(makespan); solver.end(); return makespanMax; } //----------------------------- MODEL ------------------------------------- IloModel DefineModel(const IloEnv& env, IloInt numberOfActivities, IloInt numberOfConstraints, IloInt* durations, IloInt* constraints, IloNumVar& makespan) { IloModel model(env); IloUnaryResource ures(env); // THIS ENFORCEMENT LEVEL WILL POST THE BALANCE CONSTRAINT ures.setCapacityEnforcement(IloExtended); // THIS ENFORCEMENT LEVEL WILL POST THE PRECEDENCE GRAPH CONSTRAINT ures.setPrecedenceEnforcement(IloExtended); IloReservoir reserv(env, 2, 0); // THIS ENFORCEMENT LEVEL WILL POST THE BALANCE CONSTRAINT reserv.setCapacityEnforcement(IloExtended); // COMPUTES UPPER BOUND ON MAKESPAN IloNum makespanMax = getMakespanMax(env, numberOfActivities, numberOfConstraints, durations, constraints); makespan = IloNumVar(env, 0, makespanMax, ILOINT); IloNumExprArray times(env, numberOfActivities + 1); IloActivityArray acts(env, numberOfActivities); // COMPUTE DURATION OF SHORTEST ACTIVITY IloInt dmin = IloIntMax; IloInt i, j, k, t; for (i=0; i < numberOfActivities; i++) if (durations[i] < dmin) dmin = durations[i]; IloActivity lprod; for (i=0; i < numberOfActivities; i++) { acts[i]= IloActivity(env, durations[i]); model.add(acts[i].requires(ures)); model.add(acts[i].requires(reserv, 1, IloAfterEnd)); model.add(acts[i].requires(reserv, 1, IloAfterStart)); model.add(acts[i].endsBefore(makespan)); IloActivity prod(env, 1); model.add(prod.provides(reserv, 2, IloAfterStart)); times[i] = prod.getStartExpr(); if (i > 0) // BUILD CHAIN OF PRODUCERS model.add(prod.startsAfterStart(lprod, dmin)); lprod = prod; } times[numberOfActivities] = makespan; model.add(times[numberOfActivities-1] + dmin <= makespan); // BREAK EVIDENT SYMMETRIES BETWEEN ACTIVITIES WITH SAME DURATION for (i=0; i < numberOfActivities - 1; i++) for (j=i+1; j < numberOfActivities; j++) if (durations[i] == durations[j]) { model.add(acts[j].startsAfterEnd(acts[i])); break; } // ADD DELAY CONSTRAINTS for (k=0; k < numberOfConstraints; k++) { i = constraints[3*k]; j = constraints[(3*k) + 1]; t = constraints[(3*k) + 2]; model.add(times[j]-times[i] >= t); } return model; } //-------------------------- DISPLAY SOLUTION ----------------------------- void PrintSolution(const IloSolver& solver) { IlcScheduler sched(solver); IlcUnaryResource res = *(IlcUnaryResourceIterator(sched)); for(IlcResourceConstraintIterator ite(res); ite.ok(); ++ite) solver.out() << (*ite).getActivity() << endl; } //---------------------- INITIALIZE PARAMETERS ----------------------------- void InitParameters(int argc, char** argv, IloInt& numberOfConstraints, IloInt*& durations, IloInt*& constraints) { IloInt p = 1; if (argc > 1) p = atol(argv[1]); switch (p) { case (1): numberOfConstraints = NumberOfConstraints01; durations = Durations01; constraints = Constraints01; break; case (2): numberOfConstraints = NumberOfConstraints02; durations = Durations02; constraints = Constraints02; break; case (3): numberOfConstraints = NumberOfConstraints03; durations = Durations03; constraints = Constraints03; break; } } //------------------------- SOLVE PROBLEM ---------------------------------- int main(int argc, char* argv[]) { try { IloEnv env; IloInt numberOfActivities = NumberOfActivities; IloInt numberOfConstraints; IloInt* durations; IloInt* constraints; InitParameters(argc, argv, numberOfConstraints, durations, constraints); IloNumVar makespan; IloModel model = DefineModel(env, numberOfActivities, numberOfConstraints, durations, constraints, makespan); model.add(IloMinimize(env, makespan)); IloSolver solver(model); IlcSearch search = solver.newSearch(IloRankForward(env, makespan)); IloInt sumd = 0; for (IloInt i=0; i < numberOfActivities; i++) sumd += durations[i]; while (search.next()) { solver.out() << "SOLUTION WITH SLACK = " << solver.getIntVar(makespan).getMin() - sumd << endl; PrintSolution(solver); } solver.printInformation(); solver.end(); env.end(); } catch (IloException& exc) { cout << exc << endl; } return 0; }
An optimal solution for the first problem is described in Figure 22.4. It corresponds to a slack duration of 22 (5 between t0 and t1, 2 between t5 and t6, 6 between t7 and t8, 8 between t10 and t11 and 1 between t13 and t14) for an optimal makespan of 157.
This optimal solution is quickly found after 2 iterations and 28 backtracks.
© Copyright IBM Corp. 1987, 2009. Legal terms. | PREVIOUS NEXT |