You can see the entire program relgreed.cpp here or view it in the standard distribution.
#include <ilsched/iloscheduler.h>
ILOSTLBEGIN
const IloInt NumberOfJobsA = 20;
const IloInt NumberOfJobsB = 12;
IloInt DeadlinesA [] = { 5, 15, 7, 24, 9, 10, 25, 17, 8, 15,
29, 2, 15, 17, 24, 7, 10, 28, 17, 10};
IloInt DeadlinesB [] = { 7, 18, 9, 27, 7, 10,
21, 8, 18, 16, 26, 17};
const IloInt DeadlineExtension = 5;
/////////////////////////////////////////
//
// JOB CLASSES
//
/////////////////////////////////////////
class Job {
private:
IloModel _jobModel;
IloIntVar _deadline;
IloBool _isDeadlineRelaxed;
public:
Job(const IloEnv env, const char* name, IloInt deadline);
void addToModel(IloModel model) { model.add(_jobModel); }
void removeFromModel(IloModel model) { model.remove(_jobModel); }
void relaxDeadline();
IloBool isDeadlineRelaxed() const { return _isDeadlineRelaxed; }
const char* getName() const { return _jobModel.getName(); }
protected:
IloIntVar getDeadlineVar() const { return _deadline; }
IloModel getJobModel() const { return _jobModel; }
};
Job::Job(const IloEnv env,
const char* name,
IloInt deadline)
: _jobModel(env, name),
_deadline(env),
_isDeadlineRelaxed(IlcFalse)
{
_deadline.setLB(deadline);
_deadline.setUB(deadline);
}
void Job::relaxDeadline() {
if (!_isDeadlineRelaxed) {
IloInt deadline = (IloInt)_deadline.getUB() + DeadlineExtension;
_isDeadlineRelaxed = IlcTrue;
_deadline.setLB(deadline);
_deadline.setUB(deadline);
}
}
Job* getJob(IloActivity act) {
return (Job*)act.getObject();
}
Job* getJob(IlcActivity act) {
return (Job*)act.getObject();
}
// JOB A CLASS
class JobA : public Job {
public:
JobA(const IloEnv env, const char* name, IloInt deadline,
IloSchedulerSolution solution, IloUnaryResource* workers);
};
JobA::JobA(const IloEnv env, const char* name, IloInt deadline,
IloSchedulerSolution solution, IloUnaryResource* workers)
: Job(env, name, deadline) {
IloInt i;
IloModel jobModel = getJobModel();
IloInt numberOfActivities = 4;
IloActivity* act = new (env) IloActivity[numberOfActivities];
char buffer[128];
for(i=0; i < numberOfActivities; i++) {
sprintf(buffer, "%s(Act%ld)", name, i);
act[i] = IloActivity(env, 1, buffer);
act[i].setObject(this);
IloResourceConstraint ct = act[i].requires(workers[i]);
jobModel.add(ct);
solution.add(act[i]);
solution.add(ct);
}
jobModel.add(act[3].endsBefore(getDeadlineVar()));
jobModel.add(act[1].startsAfterEnd(act[0]));
jobModel.add(act[2].startsAfterEnd(act[0]));
jobModel.add(act[3].startsAfterEnd(act[1]));
jobModel.add(act[3].startsAfterEnd(act[2]));
}
// JOB B CLASS
class JobB : public Job {
public:
JobB(const IloEnv env, const char* name, IloInt deadline,
IloSchedulerSolution solution, IloAltResSet* teams);
};
JobB::JobB(const IloEnv env, const char* name, IloInt deadline,
IloSchedulerSolution solution, IloAltResSet* teams)
: Job(env, name, deadline) {
IloInt i;
IloModel jobModel = getJobModel();
IloInt numberOfActivities = 2;
IloActivity* act = new (env) IloActivity[numberOfActivities];
char buffer[128];
for(i=0; i < numberOfActivities; i++) {
sprintf(buffer, "%s(Act%ld)", name, i);
act[i] = IloActivity(env, 2, buffer);
act[i].setObject(this);
IloResourceConstraint ct = act[i].requires(teams[i]);
jobModel.add(ct);
solution.add(act[i]);
solution.add(ct);
}
jobModel.add(act[1].endsBefore(getDeadlineVar()));
jobModel.add(act[1].startsAfterEnd(act[0]));
}
/////////////////////////////////////////
//
// PROBLEM DEFINITION
//
/////////////////////////////////////////
IloModel DefineModel(IloEnv& env,
IloInt numberOfJobsA,
IloInt numberOfJobsB,
IloInt* deadlinesA,
IloInt* deadlinesB,
IloSchedulerSolution solution) {
IloInt i;
IloModel model(env);
/* DEFINING THE RESOURCES */
IloSchedulerEnv schedEnv(env);
schedEnv.getResourceParam().
setPrecedenceEnforcement(IloMediumHigh);
IloUnaryResource* workers = new (env) IloUnaryResource[4];
workers[0] = IloUnaryResource(env, "Jim");
workers[1] = IloUnaryResource(env, "Joe");
workers[2] = IloUnaryResource(env, "Jack");
workers[3] = IloUnaryResource(env, "John");
for(i=0; i<4; i++) {
solution.add(workers[i]);
}
/* DEFINING THE INITIAL OCCUPATION */
workers[0].setInitialOccupation(3,6,1);
workers[1].setInitialOccupation(22,23,1);
workers[2].setInitialOccupation(12,17,1);
workers[3].setInitialOccupation(7,11,1);
IloAltResSet* teams = new (env) IloAltResSet[2];
teams[0] = IloAltResSet(env, 2, workers[0], workers[1]);
teams[0].setName("Jim or Joe");
teams[1] = IloAltResSet(env, 2, workers[2], workers[3]);
teams[1].setName("Jack or John");
/* DEFINING THE JOBS */
char buffer[128];
for(i=0; i < numberOfJobsA; i++) {
sprintf(buffer, "JobA%ld", i);
JobA* job = new (env) JobA(env, buffer, deadlinesA[i],
solution, workers);
job->addToModel(model);
}
for(i=0; i < numberOfJobsB; i++) {
sprintf(buffer, "JobB%ld", i);
JobB* job = new (env) JobB(env, buffer, deadlinesB[i],
solution, teams);
job->addToModel(model);
}
return model;
}
/////////////////////////////////////////
//
// MODIFYING THE MODEL
//
/////////////////////////////////////////
void NewModelFromPartialSolution(const IloSchedulerSolution& solution) {
for(IloSchedulerSolution::ResourceIterator ite(solution);
ite.ok();
++ite) {
IloResource resource = *ite;
if (resource.isUnaryResource() &&
solution.hasPrecedenceInformation(resource)) {
if (solution.hasSetupRC(resource)) {
IloResourceConstraint rct = solution.getSetupRC(resource);
for(;;) {
IloActivity act = rct.getActivity();
IloNum t = solution.getStartMin(act);
act.setStartMax(t);
if (solution.hasNextRC(rct))
rct = solution.getNextRC(rct);
else break;
}
}
}
}
}
/////////////////////////////////////////
//
// TRACE BASED FAIL DETECTION
//
/////////////////////////////////////////
class FailAnalysisResult {
IloSchedulerSolution _solution;
Job* _guiltyJob;
public:
FailAnalysisResult(IloEnv env) : _solution(env), _guiltyJob(0) {}
void setGuiltyJob(Job* job) { _guiltyJob = job; }
void reset() { _guiltyJob = 0; }
IloSchedulerSolution getSolution() const { return _solution; }
IlcBool hasGuiltyJob() const { return _guiltyJob != 0; }
Job* getGuiltyJob() const { return _guiltyJob; }
};
class FailAnalysisI : public IlcSchedulerTraceI {
IloSolver _solver;
IlcScheduler _schedule;
FailAnalysisResult& _analysisResult;
public:
FailAnalysisI(IlcScheduler sched,
FailAnalysisResult& analysisResult)
: IlcSchedulerTraceI(sched.getImpl()),
_solver(sched.getSolver()),
_schedule(sched),
_analysisResult(analysisResult) {}
virtual void failManager(IlcInt);
};
void FailAnalysisI::failManager(IlcInt) {
IlcActivity act = getCurrentActivity1();
if (act.getImpl() == 0) {
IlcResourceConstraint rct = getCurrentResourceConstraint1();
if (rct.getImpl())
act = rct.getActivity();
else {
IlcAltResConstraint altRct = getCurrentAltResConstraint();
if (altRct.getImpl()) {
act = altRct.getActivity();
}
else {
if (getCurrentResource().getImpl() == 0) return;
IlcInt t1 = getCurrentTimeMin();
IlcInt t2 = getCurrentTimeMax();
IloTranslator<IlcActivity, IlcResourceConstraint> ac =
IlcActivityResourceConstraintTranslator(_solver);
IloPredicate<IlcResourceConstraint> containsTimePeriod =
(IlcActivityStartMinEvaluator(_solver) << ac) <= t1 &&
(IlcActivityEndMaxEvaluator(_solver) << ac) >= t2;
IloEvaluator<IlcResourceConstraint> slackEval =
(IlcActivityEndMaxEvaluator(_solver) -
IlcActivityStartMinEvaluator(_solver) -
IlcActivityDurationMinEvaluator(_solver)) << ac;
IloBestSelector<IlcResourceConstraint, IlcResource>
sel1(containsTimePeriod, slackEval.makeLessThanComparator());
if (sel1.select(rct, getCurrentResource().getImpl())) {
act = rct.getActivity();
} else {
IloPredicate<IlcResourceConstraint> intersectsTimePeriod =
(IlcActivityEndMaxEvaluator(_solver) << ac) >= t1 ||
(IlcActivityStartMinEvaluator(_solver) << ac) <= t2;
IloBestSelector<IlcResourceConstraint,IlcResource>
sel2(intersectsTimePeriod, slackEval.makeLessThanComparator());
if (sel2.select(rct, getCurrentResource().getImpl())) {
act = rct.getActivity();
}
}
}
}
}
if (act.getImpl())
_analysisResult.setGuiltyJob(getJob(act));
_analysisResult.getSolution().store(_schedule);
}
IlcSchedulerTrace FailAnalysis(IlcScheduler schedule,
FailAnalysisResult& analysisResult) {
IloSolver solver = schedule.getSolver();
analysisResult.reset();
return new (solver.getHeap()) FailAnalysisI(schedule,
analysisResult);
}
/////////////////////////////////////////
//
// LIST SCHEDULING
//
/////////////////////////////////////////
ILOPREDICATE0(IsInUnselectedAltRCPredicate,
IlcActivity, act) {
for(IlcAltResConstraintIterator ite(act); ite.ok(); ++ite) {
if (!(*ite).isResourceSelected())
return IlcTrue;
}
return IlcFalse;
}
ILCGOAL0(ListScheduling) {
IloSolver solver = getSolver();
IlcScheduler schedule(solver);
IloSelector<IlcActivity,IlcSchedule> actSelector =
IloBestSelector<IlcActivity,IlcSchedule>
(!IlcActivityStartVarBoundPredicate(solver) || IsInUnselectedAltRCPredicate(solver),
IloComposeLexical(IlcActivityStartMinEvaluator(solver).makeLessThanComparator(),
IlcActivityEndMaxEvaluator(solver).makeLessThanComparator()));
IlcActivity act;
if (actSelector.select(act, schedule)) {
act.setStartTime(act.getStartMin());
for(IlcAltResConstraintIterator ite(act); ite.ok(); ++ite) {
IlcAltResConstraint altResCt = *ite;
IlcAltResSet altResSet = altResCt.getAltResSet();
IlcInt i;
for(i=0; i<altResSet.getSize(); ++i) {
IlcResource resource = altResSet[i];
if (altResCt.isPossible(resource)) {
altResCt.setSelected(resource);
break;
}
}
}
return this;
}
else return 0;
}
ILOCPGOALWRAPPER0(IloListScheduling, solver) {
return ListScheduling(solver);
}
ILOCPTRACEWRAPPER1(ListSchedulingWithFailAnalysis, solver,
FailAnalysisResult&, analysisResult) {
IlcScheduler sched(solver);
solver.setTraceMode(IlcTrue);
IlcSchedulerTrace analysis = FailAnalysis(sched, analysisResult);
analysis.traceAllFailures();
analysis.traceAllActivities();
analysis.traceAllResources();
}
/////////////////////////////////////////
//
// PRINTING OF SOLUTIONS
//
/////////////////////////////////////////
void
PrintSolution(const IloSolver& solver)
{
IlcScheduler scheduler(solver);
for(IlcActivityIterator ite(scheduler); ite.ok(); ++ite) {
IlcActivity act = *ite;
solver.out() << act;
for(IlcAltResConstraintIterator iteCt(act); iteCt.ok(); ++iteCt) {
IlcAltResConstraint altResCt = *iteCt;
solver.out() << " processed by " << altResCt.getSelected().getName();
}
solver.out() << endl;
}
}
/////////////////////////////////////////
//
// MAIN FUNCTION
//
/////////////////////////////////////////
class Exception : public IloException {
public:
Exception(const char* message) : IloException(message) {}
};
int main() {
try {
IloEnv env;
FailAnalysisResult analysisResult(env);
IloModel model = DefineModel(env,
NumberOfJobsA,
NumberOfJobsB,
DeadlinesA,
DeadlinesB,
analysisResult.getSolution());
IloSolver solver(env);
solver.setFastRestartMode(IloTrue);
solver.extract(model);
IloCPTrace initListSchedulingWithFailAnalysis = ListSchedulingWithFailAnalysis(env, analysisResult);
solver.addTrace(initListSchedulingWithFailAnalysis);
IloGoal goal = IloListScheduling(env);
while (!solver.solve(goal)) {
if (!analysisResult.hasGuiltyJob())
throw Exception("Cannot give a solution to the problem");
NewModelFromPartialSolution(analysisResult.getSolution());
Job* guiltyJob = analysisResult.getGuiltyJob();
if (!guiltyJob->isDeadlineRelaxed()) {
guiltyJob->relaxDeadline();
solver.out() << guiltyJob->getName()
<< " set at late deadline" << endl;
}
else {
guiltyJob->removeFromModel(model);
solver.out() << guiltyJob->getName()
<< " removed from the model" << endl;
}
}
solver.out() << "Solution: " << endl;
PrintSolution(solver);
solver.printInformation();
env.end();
} catch (IloException& exc) {
cout << exc << endl;
}
return 0;
}
//////////////////////////////////////////////
//
// RESULTS
//
/////////////////////////////////////////////
/*
JobA11 set at late deadline
JobB0 set at late deadline
JobA19 set at late deadline
JobA16 set at late deadline
JobA15 set at late deadline
JobA11 removed from the model
JobA8 set at late deadline
JobA5 set at late deadline
JobA4 set at late deadline
JobA2 set at late deadline
JobA15 removed from the model
JobA19 removed from the model
JobA16 removed from the model
JobA12 set at late deadline
JobA9 set at late deadline
JobA5 removed from the model
JobB9 set at late deadline
JobA18 set at late deadline
JobA13 set at late deadline
JobB1 set at late deadline
JobB0 removed from the model
JobA8 removed from the model
JobA4 removed from the model
JobB9 removed from the model
JobB6 set at late deadline
JobB1 removed from the model
JobB6 removed from the model
Solution:
JobB11(Act1) [14 -- 2 --> 16] processed by John
JobB11(Act0) [8 -- 2 --> 10] processed by Joe
JobB10(Act1) [24 -- 2 --> 26] processed by Jack
JobB10(Act0) [17 -- 2 --> 19] processed by Joe
JobB8(Act1) [16 -- 2 --> 18] processed by John
JobB8(Act0) [9 -- 2 --> 11] processed by Jim
JobB7(Act1) [4 -- 2 --> 6] processed by Jack
JobB7(Act0) [1 -- 2 --> 3] processed by Jim
JobB5(Act1) [7 -- 2 --> 9] processed by Jack
JobB5(Act0) [5 -- 2 --> 7] processed by Joe
JobB4(Act1) [2 -- 2 --> 4] processed by Jack
JobB4(Act0) [0 -- 2 --> 2] processed by Joe
JobB3(Act1) [25 -- 2 --> 27] processed by John
JobB3(Act0) [18 -- 2 --> 20] processed by Jim
JobB2(Act1) [5 -- 2 --> 7] processed by John
JobB2(Act0) [3 -- 2 --> 5] processed by Joe
JobA18(Act3) [20 -- 1 --> 21]
JobA18(Act2) [19 -- 1 --> 20]
JobA18(Act1) [14 -- 1 --> 15]
JobA18(Act0) [13 -- 1 --> 14]
JobA17(Act3) [27 -- 1 --> 28]
JobA17(Act2) [26 -- 1 --> 27]
JobA17(Act1) [21 -- 1 --> 22]
JobA17(Act0) [20 -- 1 --> 21]
JobA14(Act3) [22 -- 1 --> 23]
JobA14(Act2) [21 -- 1 --> 22]
JobA14(Act1) [16 -- 1 --> 17]
JobA14(Act0) [15 -- 1 --> 16]
JobA13(Act3) [21 -- 1 --> 22]
JobA13(Act2) [20 -- 1 --> 21]
JobA13(Act1) [15 -- 1 --> 16]
JobA13(Act0) [14 -- 1 --> 15]
JobA12(Act3) [18 -- 1 --> 19]
JobA12(Act2) [17 -- 1 --> 18]
JobA12(Act1) [12 -- 1 --> 13]
JobA12(Act0) [11 -- 1 --> 12]
JobA10(Act3) [28 -- 1 --> 29]
JobA10(Act2) [27 -- 1 --> 28]
JobA10(Act1) [23 -- 1 --> 24]
JobA10(Act0) [21 -- 1 --> 22]
JobA9(Act3) [19 -- 1 --> 20]
JobA9(Act2) [18 -- 1 --> 19]
JobA9(Act1) [13 -- 1 --> 14]
JobA9(Act0) [12 -- 1 --> 13]
JobA7(Act3) [13 -- 1 --> 14]
JobA7(Act2) [10 -- 1 --> 11]
JobA7(Act1) [11 -- 1 --> 12]
JobA7(Act0) [7 -- 1 --> 8]
JobA6(Act3) [24 -- 1 --> 25]
JobA6(Act2) [23 -- 1 --> 24]
JobA6(Act1) [20 -- 1 --> 21]
JobA6(Act0) [17 -- 1 --> 18]
JobA3(Act3) [23 -- 1 --> 24]
JobA3(Act2) [22 -- 1 --> 23]
JobA3(Act1) [19 -- 1 --> 20]
JobA3(Act0) [16 -- 1 --> 17]
JobA2(Act3) [11 -- 1 --> 12]
JobA2(Act2) [9 -- 1 --> 10]
JobA2(Act1) [7 -- 1 --> 8]
JobA2(Act0) [6 -- 1 --> 7]
JobA1(Act3) [12 -- 1 --> 13]
JobA1(Act2) [11 -- 1 --> 12]
JobA1(Act1) [10 -- 1 --> 11]
JobA1(Act0) [8 -- 1 --> 9]
JobA0(Act3) [3 -- 1 --> 4]
JobA0(Act2) [1 -- 1 --> 2]
JobA0(Act1) [2 -- 1 --> 3]
JobA0(Act0) [0 -- 1 --> 1]
*/
PREVIOUS
NEXT