IBM ILOG Scheduler User's Manual > Advanced Concepts > Scheduling with Discrete Resources: the Ship-loading Problem, Second Version > Solving the Problem: Exploiting the Decomposition |
Solving the Problem: Exploiting the Decomposition |
INDEX
![]() |
The function SolveSubProblem
assigns the start and end times of the activities within each subproblem, and stores them in the global solution given as argument.
As critical activities play a pivotal role between subproblems, each critical activity belongs to two submodels (the one it is the last activity of and the one it is the first activity of). When solving a subproblem i, the start and end times of the critical activity that starts subproblem i are already known as this critical activity was scheduled in subproblem i-1. Those start and end times are extracted from the solution.
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); } }
The final code creates an empty solution which is updated with the submodel solutions computed from SolveSubProblem
.
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; }
© Copyright IBM Corp. 1987, 2009. Legal terms. | PREVIOUS NEXT |