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