IBM ILOG Scheduler User's Manual > Advanced Concepts > Scheduling with Discrete Resources: the Ship-loading Problem, Second Version > Complete Program and Output |
Complete Program and Output |
INDEX
![]() |
You can see the entire program shipdec.cpp
here or view it online in the standard distribution.
#include <ilsched/iloscheduler.h> ILOSTLBEGIN IloInt Capacity = 8; IloInt NumberOfActivities = 34; IloInt ProcessingTimes [] = {3, 4, 4, 6, 5, 2, 3, 4, 3, 2, 3, 2, 1, 5, 2, 3, 2, 2, 1, 1, 1, 2, 4, 5, 2, 1, 1, 2, 1, 3, 2, 1, 2, 2}; IloInt Demands [] = {4, 4, 3, 4, 5, 5, 4, 3, 4, 8, 4, 5, 4, 3, 3, 3, 6, 7, 4, 4, 4, 4, 7, 8, 8, 3, 3, 6, 8, 3, 3, 3, 3, 3}; IloInt Precedences [] = {1, 2, 1, 4, 2, 3, 3, 5, 3, 7, 4, 5, 5, 6, 6, 8, 7, 8, 8, 9, 9, 10, 9, 14, 10, 11, 10, 12, 11, 13, 12, 13, 13, 15, 13, 16, 14, 15, 15, 18, 16, 17, 17, 18, 18, 19, 18, 20, 18, 21, 19, 23, 20, 23, 21, 22, 22, 23, 23, 24, 24, 25, 25, 26, 25, 30, 25, 31, 25, 32, 26, 27, 27, 28, 28, 29, 30, 28, 31, 28, 32, 33, 33, 34, 0, 0}; typedef IloArray<IloModel> IloModelArray; typedef IloArray<IloActivity> IloActivityArray; /////////////////////////////////////////////////////////////////////////////// // // DEFINITION OF THE ACTIVITY CLASS // /////////////////////////////////////////////////////////////////////////////// class Activity { private: IloActivity _act; IloBool _critical; IloInt _subProblem; public: Activity(IloEnv env, IloInt number, IloInt processingTime); ~Activity(); IloActivity getActivity() const { return _act; } void setCritical(IloBool critical) { _critical = critical; } IloBool isCritical() const { return _critical; } void setSubProblem(IloInt subProblem) { _subProblem = subProblem; } IloInt getSubProblem() const { return _subProblem; } }; Activity::Activity(IloEnv env, IloInt number, IloInt processingTime) :_act (env, processingTime), _critical (IloFalse), _subProblem (0) { _act.setObject(this); char buffer[128]; sprintf(buffer, "Activity %ld ", number); _act.setName(buffer); } Activity::~Activity() {} /////////////////////////////////////////////////////////////////////////////// // // PROBLEM DEFINITION // /////////////////////////////////////////////////////////////////////////////// void DefineProblem(IloModel model, IloInt numberOfActivities, IloInt* processingTimes, IloInt* demands, IloInt capacity, IloInt* precedences, IloActivityArray& activities, IloNumVar& makespan) { IloEnv env = model.getEnv(); /* CREATE THE MAKESPAN VARIABLE. */ IloInt horizon = 0; IloInt i = 0; for (i = 0; i < numberOfActivities; i++) horizon += processingTimes[i]; makespan = IloNumVar(env, 0, horizon, IloNumVar::Int); /* CREATE THE RESOURCE. */ IloDiscreteResource resource(env, capacity); resource.setPrecedenceEnforcement(IloExtended); /* CREATE THE ACTIVITIES. */ activities = IloActivityArray(env,numberOfActivities); for (i = 0; i < numberOfActivities; i++) { Activity* act = new (env) Activity(env, i + 1, processingTimes[i]); activities[i] = act->getActivity(); model.add(activities[i].requires(resource, demands[i])); } /* POST THE PRECEDENCE CONSTRAINTS. */ IloInt precedenceIndex; for (precedenceIndex = 0; ; precedenceIndex = precedenceIndex + 2) { IloInt predNumber = precedences[precedenceIndex] - 1; if (predNumber == -1) break; IloInt succNumber = precedences[precedenceIndex + 1] - 1; model.add(activities[succNumber].startsAfterEnd(activities[predNumber])); } } /////////////////////////////////////////////////////////////////////////////// // // PROBLEM DECOMPOSITION // /////////////////////////////////////////////////////////////////////////////// void DecomposeProblem(IloModel model, IloActivityArray activities, IloNumVar makespan, IloModelArray& subModels) { // 1. CREATE DECOMPOSITION ALGORITHM AND SET SUBPROBLEMS IloEnv env = model.getEnv(); IloSchedulerEnv schedEnv(env); schedEnv.setPrecedenceEnforcement(IloMediumHigh); IloSolver solver(model); solver.solve(IloGoalTrue(env)); IloInt numberOfActivities = activities.getSize(); IloInt nbSubProblems = 0; IloInt i; IlcScheduler schedr(solver); for (i = 0; i < numberOfActivities; i++) { Activity* act = ((Activity*) activities[i].getObject()); if (schedr.getActivity(activities[i]).isRanked()) act->setCritical(IloTrue); IloInt subProblem = 0; for (IloInt j = 0; j < numberOfActivities; j++) if ((i != j) && schedr.getActivity(activities[j]).isRanked() && schedr.getActivity(activities[j]).isSucceededBy (schedr.getActivity(activities[i]))) subProblem++; act->setSubProblem(subProblem); if (subProblem >= nbSubProblems) nbSubProblems = subProblem + 1; } schedEnv.setPrecedenceEnforcement(IloBasic); // 2. CREATE SUB-MODELS subModels = IloModelArray(env,nbSubProblems); for (i = 0; i < nbSubProblems; i++) { subModels[i] = IloModel(env); } // 2.1 DECOMPOSE RESOURCE CONSTRAINTS for(IloIterator<IloResourceConstraint> iterct(env); iterct.ok(); ++iterct) { IloResourceConstraint rct(*iterct); Activity* act = ((Activity*) rct.getActivity().getObject()); subModels[act->getSubProblem()].add(rct); } // 2.2 DECOMPOSE PRECEDENCE CONSTRAINTS for(IloIterator<IloPrecedenceConstraint> itepct(env); itepct.ok(); ++itepct) { IloPrecedenceConstraint pct(*itepct); Activity* precAct = ((Activity*) pct.getPrecedingActivity().getObject()); Activity* follAct = ((Activity*) pct.getFollowingActivity().getObject()); if ((precAct->getSubProblem() == follAct->getSubProblem()) || ((precAct->getSubProblem() == follAct->getSubProblem() - 1) && (precAct->isCritical()))) subModels[follAct->getSubProblem()].add(pct); } // 2.3 SET SUB-MODELS MAKESPAN VARIABLES for (i = 0; i < numberOfActivities; i++) { Activity* act = ((Activity*) activities[i].getObject()); if (act->isCritical()) { IloNumExpr subModelMakespan = activities[i].getEndExpr(); subModels[act->getSubProblem()].add(IloMinimize(env, subModelMakespan)); } if (act->getSubProblem() == nbSubProblems - 1) { subModels[act->getSubProblem()].add(activities[i].endsBefore(makespan)); } } subModels[nbSubProblems-1].add(IloMinimize(env, makespan)); } /////////////////////////////////////////////////////////////////////////////// // // SOLVE SUB-MODELS // /////////////////////////////////////////////////////////////////////////////// void SolveSubProblem(IloModel subModel, IloInt s, IloActivityArray& activities, const IloSchedulerSolution& solution, IloBool lastSubProblem, IloNumVar makespan ) { IloEnv env = subModel.getEnv(); IloSolver solver(env); solver.extract(subModel); IlcScheduler scheduler(solver); IloInt i = 0; IloInt numberOfActivities = activities.getSize(); IloGoal goal; // Instantiate the start- and end-time of the critical activities // in this sub-model based on the saved solution. for (i = 0; i < numberOfActivities; i++) { Activity* act = ((Activity*) activities[i].getObject()); if ((act->getSubProblem() == s-1) && act->isCritical()) { IlcActivity ilcAct = scheduler.getActivity(activities[i]); ilcAct.setStartTime((IlcInt)solution.getStartMin(activities[i])); ilcAct.setEndTime((IlcInt)solution.getEndMax(activities[i])); } if ((act->getSubProblem() == s) && act->isCritical()) { assert(goal.getImpl() == 0); IloNumVar endVar(env, 0, IloInfinity, ILOINT); subModel.add(activities[i].endsAt(endVar)); goal = IloSetTimesForward(env, endVar, IloSelFirstActMinEndMin); } } if (!lastSubProblem) { solver.solve(goal); } else { assert(goal.getImpl() == 0); solver.solve(IloSetTimesForward(env, makespan, IloSelFirstActMinEndMin)); } // Store the sub-model results in the global solution for (i = 0; i < numberOfActivities; i++) { Activity* act = ((Activity*) activities[i].getObject()); if (act->getSubProblem() == s) solution.store(activities[i], scheduler); } } /////////////////////////////////////////////////////////////////////////////// // // PRINTING OF SOLUTIONS // /////////////////////////////////////////////////////////////////////////////// void PrintSolution(IloActivityArray& activities, const IloSchedulerSolution& solution) { IloInt numberOfActivities = activities.getSize(); for (IloInt i = 0; i < numberOfActivities; i++) { IloActivity act = activities[i]; solution.getEnv().out() << act.getName() << " [" << solution.getStartMin(act) << " -- " << solution.getProcessingTimeMin(act) << " --> " << solution.getEndMin(act) << "]" << endl; } } /////////////////////////////////////////////////////////////////////////////// // // MAIN FUNCTION // /////////////////////////////////////////////////////////////////////////////// int main() { try { IloEnv env; IloModel model(env); IloNumVar makespan; IloActivityArray activities(env); DefineProblem(model, NumberOfActivities, ProcessingTimes, Demands, Capacity, Precedences, activities, makespan); /** Decompose the problem in a set of independent subproblems. */ IloModelArray subModels(env); DecomposeProblem(model, activities, makespan, subModels); /** Solve each sub-problem independently. */ IloSchedulerSolution solution(env); IloInt nbSubProblems = subModels.getSize(); for (IloInt i=0; i < nbSubProblems; i++) { IloModel subModel = subModels[i]; SolveSubProblem(subModel, i, activities, solution, i==nbSubProblems-1, makespan); } PrintSolution(activities, solution); solution.end(); env.end(); } catch (IloException& exc) { cout << exc << endl; } return 0; } /////////////////////////////////////////////////////////////////////////////// // // RESULTS // /////////////////////////////////////////////////////////////////////////////// /* shipdec Activity 1 [0 -- 3 --> 3] Activity 2 [3 -- 4 --> 7] Activity 3 [7 -- 4 --> 11] Activity 4 [3 -- 6 --> 9] Activity 5 [14 -- 5 --> 19] Activity 6 [19 -- 2 --> 21] Activity 7 [11 -- 3 --> 14] Activity 8 [21 -- 4 --> 25] Activity 9 [25 -- 3 --> 28] Activity 10 [28 -- 2 --> 30] Activity 11 [32 -- 3 --> 35] Activity 12 [30 -- 2 --> 32] Activity 13 [35 -- 1 --> 36] Activity 14 [30 -- 5 --> 35] Activity 15 [36 -- 2 --> 38] Activity 16 [36 -- 3 --> 39] Activity 17 [39 -- 2 --> 41] Activity 18 [41 -- 2 --> 43] Activity 19 [44 -- 1 --> 45] Activity 20 [43 -- 1 --> 44] Activity 21 [43 -- 1 --> 44] Activity 22 [44 -- 2 --> 46] Activity 23 [46 -- 4 --> 50] Activity 24 [50 -- 5 --> 55] Activity 25 [55 -- 2 --> 57] Activity 26 [57 -- 1 --> 58] Activity 27 [58 -- 1 --> 59] Activity 28 [63 -- 2 --> 65] Activity 29 [65 -- 1 --> 66] Activity 30 [60 -- 3 --> 63] Activity 31 [59 -- 2 --> 61] Activity 32 [57 -- 1 --> 58] Activity 33 [58 -- 2 --> 60] Activity 34 [61 -- 2 --> 63] */
The decomposition dramatically decreases the number of failures to 38 and the CPU time to 0.2 seconds.
© Copyright IBM Corp. 1987, 2009. Legal terms. | PREVIOUS NEXT |