| 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
PREVIOUS
NEXT
|
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 |