You can see the entire program resched2.cpp here or view it online in the standard distribution.
#include <ilsched/iloscheduler.h>
ILOSTLBEGIN
IloInt ResourceNumbers06 [] = {2, 0, 1, 3, 5, 4,
1, 2, 4, 5, 0, 3,
2, 3, 5, 0, 1, 4,
1, 0, 2, 3, 4, 5,
2, 1, 4, 5, 0, 3,
1, 3, 5, 0, 4, 2};
IloNum Durations06 [] = { 1, 3, 6, 7, 3, 6,
8, 5, 10, 10, 10, 4,
5, 4, 8, 9, 1, 7,
5, 5, 5, 3, 8, 9,
9, 3, 5, 4, 3, 1,
3, 3, 9, 10, 4, 1};
IloInt ResourceNumbers10 [] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9,
0, 2, 4, 9, 3, 1, 6, 5, 7, 8,
1, 0, 3, 2, 8, 5, 7, 6, 9, 4,
1, 2, 0, 4, 6, 8, 7, 3, 9, 5,
2, 0, 1, 5, 3, 4, 8, 7, 9, 6,
2, 1, 5, 3, 8, 9, 0, 6, 4, 7,
1, 0, 3, 2, 6, 5, 9, 8, 7, 4,
2, 0, 1, 5, 4, 6, 8, 9, 7, 3,
0, 1, 3, 5, 2, 9, 6, 7, 4, 8,
1, 0, 2, 6, 8, 9, 5, 3, 4, 7};
IloNum Durations10 [] = {29, 78, 9, 36, 49, 11, 62, 56, 44, 21,
43, 90, 75, 11, 69, 28, 46, 46, 72, 30,
91, 85, 39, 74, 90, 10, 12, 89, 45, 33,
81, 95, 71, 99, 9, 52, 85, 98, 22, 43,
14, 6, 22, 61, 26, 69, 21, 49, 72, 53,
84, 2, 52, 95, 48, 72, 47, 65, 6, 25,
46, 37, 61, 13, 32, 21, 32, 89, 30, 55,
31, 86, 46, 74, 32, 88, 19, 48, 36, 79,
76, 69, 76, 51, 85, 11, 40, 89, 26, 74,
85, 13, 61, 7, 64, 76, 47, 52, 90, 45};
IloInt ResourceNumbers20 [] = {0, 1, 2, 3, 4,
0, 1, 3, 2, 4,
1, 0, 2, 4, 3,
1, 0, 4, 2, 3,
2, 1, 0, 3, 4,
2, 1, 4, 0, 3,
1, 0, 2, 3, 4,
2, 1, 0, 3, 4,
0, 3, 2, 1, 4,
1, 2, 0, 3, 4,
1, 3, 0, 4, 2,
2, 0, 1, 3, 4,
0, 2, 1, 3, 4,
2, 0, 1, 3, 4,
0, 1, 4, 2, 3,
1, 0, 3, 4, 2,
0, 2, 1, 3, 4,
0, 1, 4, 2, 3,
1, 2, 0, 3, 4,
0, 1, 2, 3, 4};
IloNum Durations20 [] = {29, 9, 49, 62, 44,
43, 75, 69, 46, 72,
91, 39, 90, 12, 45,
81, 71, 9, 85, 22,
14, 22, 26, 21, 72,
84, 52, 48, 47, 6,
46, 61, 32, 32, 30,
31, 46, 32, 19, 36,
76, 76, 85, 40, 26,
85, 61, 64, 47, 90,
78, 36, 11, 56, 21,
90, 11, 28, 46, 30,
85, 74, 10, 89, 33,
95, 99, 52, 98, 43,
6, 61, 69, 49, 53,
2, 95, 72, 65, 25,
37, 13, 21, 89, 55,
86, 74, 88, 48, 79,
69, 51, 11, 89, 74,
13, 7, 76, 52, 45};
///////////////////////////////////////////////////////////////////////////////
//
// TEXTURE CHOICE POINT FOR SCHEDULING AND RESCHEDULING
//
///////////////////////////////////////////////////////////////////////////////
class TextureGoalI : public IlcGoalI {
private:
IlcSchedule _schedule;
IloRandom _randGen;
protected:
IlcResourceTexture chooseResource();
IlcBool choosePrecedence(IlcResourceTexture,
IlcResourceConstraint&, IlcResourceConstraint&);
public:
TextureGoalI(IlcSchedule s, IloRandom r)
: IlcGoalI(s.getSolver()), _schedule(s), _randGen(r) { }
~TextureGoalI() {}
virtual IlcGoal execute();
};
IlcGoal TextureGoalI::execute() {
IlcResourceTexture selectedTexture = chooseResource();
while(0 != selectedTexture.getImpl()) {
IlcResourceConstraint rctA, rctB;
if (!choosePrecedence(selectedTexture, rctA, rctB)) {
selectedTexture.setNoCommitmentsAtCriticalPoint();
selectedTexture = chooseResource();
}
else
return IlcAnd(IlcTrySetSuccessor(rctA, rctB), this);
}
return 0;
}
IlcResourceTexture TextureGoalI::chooseResource() {
IlcResourceTexture selectedTexture = 0;
IlcInt nbNonzero = 0;
// Randomly choose a texture from all of those with non-zero max
// criticality.
for(IlcResourceIterator iter(_schedule); iter.ok(); ++iter) {
if ((*iter).isDiscreteResource()) {
IlcDiscreteResource res = (IlcDiscreteResource) (*iter);
IlcResourceTexture texture = res.getTextureMeasurement();
if (texture.getMaxCriticality() > 0) {
nbNonzero++;
if ((0 == selectedTexture.getImpl()) ||
(_randGen.getFloat() < 1/(IlcFloat) nbNonzero)) {
selectedTexture = texture;
}
}
}
}
return selectedTexture;
}
IlcBool TextureGoalI::choosePrecedence(IlcResourceTexture texture,
IlcResourceConstraint& before,
IlcResourceConstraint& after) {
// Find a pair of unsequenced resource constraints which minimize a
// measure of temporal slack due to:
//
// Laborie, P. and Ghallab, M.
// Planning with Sharable Resource Constraints
// Proceedings of the 14th International Joint Conference on
// Artificial Intelligence, IJCAI-95, 1995
before = 0;
after = 0;
IlcRCTextureArray rcArray = texture.getCriticalityOrderedRCTextures();
IlcInt nbRCs = rcArray.getSize();
IlcFloat minCommitVal = IlcFloatMax;
for(IlcInt i = 0; (i < nbRCs - 1) &&
(rcArray[i].getCriticalContribution() > 0); ++i) {
IlcResourceConstraint ctI = (rcArray[i]).getResourceConstraint();
IlcInt startMinI = ctI.getActivity().getStartMin();
IlcInt startMaxI = ctI.getActivity().getStartMax();
IlcInt endMinI = ctI.getActivity().getEndMin();
IlcInt endMaxI = ctI.getActivity().getEndMax();
for(IlcInt j = i+1; (j < nbRCs) &&
(rcArray[j].getCriticalContribution() > 0); ++j) {
IlcResourceConstraint ctJ = (rcArray[j]).getResourceConstraint();
if (!ctI.isSucceededBy(ctJ) && !ctJ.isSucceededBy(ctI)) {
IlcInt startMinJ = ctJ.getActivity().getStartMin();
IlcInt startMaxJ = ctJ.getActivity().getStartMax();
IlcInt endMinJ = ctJ.getActivity().getEndMin();
IlcInt endMaxJ = ctJ.getActivity().getEndMax();
// calculate I before J
IlcInt denom = (endMaxI - endMinI) + (startMaxJ - startMinJ);
IlcInt numer;
IlcFloat commitVal = 1;
if ((endMinI <= startMaxJ) && (denom > 0)) {
numer = (IlcMin(endMaxI, startMaxJ) - endMinI) +
(startMaxJ - IlcMax(startMinJ, endMinI));
commitVal = 1 - IlcMax(((IlcFloat)numer/(IlcFloat)denom), 0);
if (commitVal < minCommitVal) {
minCommitVal = commitVal;
before = ctI;
after = ctJ;
}
}
// calculate J before I
denom = (endMaxJ - endMinJ) + (startMaxI - startMinI);
if ((endMinJ <= startMaxI) && (denom > 0)) {
numer = (IlcMin(endMaxJ, startMaxI) - endMinJ) +
(startMaxI - IlcMax(startMinI, endMinJ));
commitVal = 1 - IlcMax(((IlcFloat)numer/(IlcFloat)denom), 0);
if (commitVal < minCommitVal) {
minCommitVal = commitVal;
before = ctJ;
after = ctI;
}
}
}
}
}
return ((before.getImpl() != 0) && (after.getImpl() != 0));
}
ILCGOAL1(AssignESTArray,
IlcIntVarArray, stArray) {
IloSolver solver = getSolver();
IlcInt size = stArray.getSize();
for(IlcInt i = 0; i < size; ++i)
stArray[i].setValue(stArray[i].getMin());
return 0;
}
ILOCPGOALWRAPPER2(TextureGoal, solver, IloNumVar, cost, IloRandom, rand) {
IlcScheduler scheduler(solver);
IlcIntVarArray varArray(solver, scheduler.getNumberOfActivities()+1);
IlcInt index = 0;
for(IlcActivityIterator iter(scheduler); iter.ok(); ++iter)
varArray[index++] = (*iter).getStartVariable();
varArray[index] = solver.getIntVar(cost);
return IlcAnd(IlcGoal(new (solver.getHeap())
TextureGoalI(scheduler, rand)),
AssignESTArray(solver, varArray));
}
///////////////////////////////////////////////////////////////////////////////
//
// ORIGINAL MODEL DEFINITION
//
///////////////////////////////////////////////////////////////////////////////
void CreateOriginalModel(const IloEnv env,
IloNum resourceCapacity,
IloInt numberOfJobs,
IloInt numberOfResources,
IloInt* resourceNumbers,
IloNum* durations,
IloNumVar& makespan,
IloModel& model,
IloSchedulerSolution& solution)
{
IloRandom randGen(env, 8975324);
IloInt i, j, k;
IloInt numberOfActivities = numberOfJobs * numberOfResources;
char buffer[128];
model = IloModel(env);
solution = IloSchedulerSolution(env);
// CREATE THE MAKESPAN VARIABLE.
IloNum horizon = 0;
for (i = 0; i < numberOfActivities; i++)
horizon += durations[i];
makespan = IloNumVar(env, 0, horizon, ILOINT);
solution.getSolution().add(makespan);
// CREATE THE RESOURCES.
IloSchedulerEnv schedEnv(env);
schedEnv.getResourceParam().setCapacityEnforcement(IloHigh);
schedEnv.getResourceParam().setPrecedenceEnforcement(IloMediumHigh);
IloTextureParam textureParam = schedEnv.getTextureParam();
textureParam.setCriticalityCalculator(
IloProbabilisticCriticalityCalculator(env));
textureParam.setRCTextureFactory(IloRCTextureESTFactory(env));
textureParam.setRandomGenerator(randGen);
IloDiscreteResource *resources =
new (env) IloDiscreteResource[numberOfResources];
for (j = 0; j < numberOfResources; j++) {
sprintf(buffer, "R%ld", j);
resources[j] = IloDiscreteResource(env,resourceCapacity,buffer);
}
IloInt r;
for(r = 0; r < resourceCapacity; ++r) {
// CREATE THE ACTIVITIES.
k = 0;
for (i = 0; i < numberOfJobs; i++) {
IloActivity previousActivity;
for (j = 0; j < numberOfResources; j++) {
sprintf(buffer, "O%ldJ%ldS%ldR%ld", r, i, j, resourceNumbers[k]);
IloActivity activity(env, durations[k], buffer);
IloDiscreteResource resource = resources[resourceNumbers[k]];
model.add(activity.requires(resource, 1));
if (j != 0)
model.add(activity.startsAfterEnd(previousActivity));
solution.add(activity);
previousActivity = activity;
k++;
}
model.add( previousActivity.endsBefore(makespan) );
}
}
// SET THE OBJECTIVE
model.add(IloMinimize(env, makespan));
}
///////////////////////////////////////////////////////////////////////////////
//
// SOLVE THE MODEL (ORIGINAL OR SUBMODEL)
//
///////////////////////////////////////////////////////////////////////////////
IloBool SolveModel(const IloModel model, IloSchedulerSolution solution,
const IloNumVar optVar,
IloInt failLimit, IloNum& runningTime) {
IloEnv env = model.getEnv();
IloSolver solver(model);
IlcScheduler scheduler(solver);
IloBool solved = IloFalse;
// PROPAGATE TO FIND LOWER BOUND ON OPT-VAR
solver.solve(IloGoalTrue(env));
IlcInt minOpt = solver.getIntVar(optVar).getMin();
solver.out() << "Initial propagation lower-bound optimization value: "
<< minOpt << endl;
IloGoal goal = TextureGoal(env, optVar, IloRandom(env, 45874052));
IloInt nbOfFails = 0;
runningTime = 0;
IloBool foundOpt = IloFalse;
IloInt localFailLimit = 1;
IloNum bestOptVal = optVar.getUB();
IloNum lastBestOptVal = bestOptVal;
IloConstraint optVarConstraint;
while(!foundOpt && (localFailLimit > 0)) {
IloGoal limitedGoal = IloLimitSearch(env, goal,
IloFailLimit(env, localFailLimit));
solver.startNewSearch(limitedGoal);
while(!foundOpt && solver.next()) {
bestOptVal = solver.getIntVar(optVar).getValue();
solver.out() << "Solution with optimization value: "
<< bestOptVal << endl;
solution.store(scheduler);
if (bestOptVal == minOpt) {
solver.out() << "Locally optimal solution" << endl;
foundOpt = IloTrue;
}
solved = IloTrue;
}
runningTime += solver.getTime();
nbOfFails += solver.getNumberOfFails();
localFailLimit *= 2;
IloInt failsLeft = failLimit - nbOfFails;
if (localFailLimit > failsLeft)
localFailLimit = failsLeft;
solver.endSearch();
if (bestOptVal < lastBestOptVal) {
if (optVarConstraint.getImpl() != 0)
model.remove(optVarConstraint);
optVarConstraint = (optVar < bestOptVal);
model.add(optVarConstraint);
lastBestOptVal = bestOptVal;
}
}
solver.out() << "Number of fails : " << nbOfFails
<< "\nRunning time : " << runningTime
<< endl;
solver.end();
if (optVarConstraint.getImpl() != 0)
model.remove(optVarConstraint);
return solved;
}
///////////////////////////////////////////////////////////////////////////////
//
// RESCHEDULING EVENT (ADD A NEW JOB)
//
///////////////////////////////////////////////////////////////////////////////
void AddNewJob(IloModel model,
IloInt newJobNumber,
IloResourceConstraint *rcArray,
IloNumVar makespan,
IloInt numberOfJobs,
IloInt numberOfResources,
IloNum *existingDurations) {
IloEnv env = model.getEnv();
IloRandom randGen(env, 98303001);
// CREATE DURATIONS
IloNum minDur = IloInfinity;
IloNum maxDur = -IloInfinity;
IloInt i;
for(i = 0; i < numberOfJobs * numberOfResources; ++i) {
if (existingDurations[i] < minDur)
minDur = existingDurations[i];
if (existingDurations[i] > maxDur)
maxDur = existingDurations[i];
}
IloNum diff = maxDur - minDur + 1;
IloNumArray durations(env, numberOfResources);
for(i = 0; i < numberOfResources; ++i)
durations[i] = randGen.getInt(IloTrunc(diff)) + minDur;
// CREATE RESOURCE USAGE
IloArray<IloDiscreteResource> resources(env, numberOfResources);
i = 0;
for(IloIterator<IloDiscreteResource> iter(env); iter.ok(); ++iter) {
resources[i] = *iter;
++i;
}
// RANDOMLY PERMUTE RESOURCE REQUIREMENTS
for(i = 0; i < 1000; ++i) {
IloInt index1 = randGen.getInt(numberOfResources);
IloInt index2 = randGen.getInt(numberOfResources);
while (index1 == index2)
index2 = randGen.getInt(numberOfResources);
IloDiscreteResource tmp = resources[index1];
resources[index1] = resources[index2];
resources[index2] = tmp;
}
// CREATE THE ACTIVITIES
IloActivity previousActivity;
char buffer[128];
for(i = 0; i < numberOfResources; ++i) {
sprintf(buffer, "NJ%ldS%ld%s", newJobNumber, i, resources[i].getName());
IloActivity activity(env, durations[i], buffer);
rcArray[i] = activity.requires(resources[i], 1);
model.add(rcArray[i]);
if (i != 0)
model.add(activity.startsAfterEnd(previousActivity));
previousActivity = activity;
}
model.add(previousActivity.endsBefore(makespan));
randGen.end();
}
///////////////////////////////////////////////////////////////////////////////
//
// DEFINE AND SOLVE TEMPORAL MODEL
//
///////////////////////////////////////////////////////////////////////////////
void
CreateTemporalModel(IloSchedulerSolution originalSolution,
IloResourceConstraint *newJob,
IloInt numberOfResources,
IloNumVar makespan,
IloModel& temporalModel,
IloSchedulerSolution& temporalSolution) {
IloEnv env = originalSolution.getEnv();
temporalModel = IloModel(env);
temporalSolution = IloSchedulerSolution(env);
temporalSolution.add(makespan);
// CALCULATE MAXIMUM INCREASE IN MAKESPAN FROM THE NEW JOB
IloNum maxMakespanIncrease = 0;
IloInt i;
for(i = 0; i < numberOfResources; ++i)
maxMakespanIncrease +=
newJob[i].getActivity().getProcessingTimeVariable().getUB();
temporalModel.add(makespan <
originalSolution.getSolution().getValue(makespan) +
maxMakespanIncrease);
// Put all the precedence constraints from the original model into
// the temporal model but not the resource constraints.
for (IloIterator<IloPrecedenceConstraint> pcIter(env);
pcIter.ok();
++pcIter)
{
IloPrecedenceConstraint pc = (*pcIter);
IloActivity nextAct = pc.getFollowingActivity();
IloActivity prevAct = pc.getPrecedingActivity();
temporalModel.add(pc);
if (!temporalSolution.contains(nextAct))
temporalSolution.add(nextAct);
if (!temporalSolution.contains(prevAct))
temporalSolution.add(prevAct);
if (originalSolution.contains(prevAct))
temporalModel.add(prevAct.startsAfter(
originalSolution.getStartMin(prevAct)));
if (originalSolution.contains(nextAct))
temporalModel.add(nextAct.startsAfter(
originalSolution.getStartMin(nextAct)));
}
// search for the last activity, and add
// its time-bound constraint over the makespan.
for (IloIterator<IloTimeBoundConstraint> tbcIter(env);
tbcIter.ok();
++tbcIter) {
IloTimeBoundConstraint tbc = (*tbcIter);
if (tbc.getType() == IloEndsBefore)
temporalModel.add(tbc);
}
}
void CreateAndSolveTemporalModel(IloSchedulerSolution originalSolution,
IloResourceConstraint *newJob,
IloInt numberOfResources,
IloNumVar makespan,
IloSolver& temporalSolver,
IloModel& temporalModel,
IloSchedulerSolution& temporalSolution) {
CreateTemporalModel(originalSolution,
newJob,
numberOfResources,
makespan,
temporalModel,
temporalSolution);
IloEnv env = originalSolution.getEnv();
// SOLVE TEMPORAL MODEL (PROPAGATE)
temporalSolver = IloSolver(temporalModel);
if (!temporalSolver.solve(IloGoalTrue(env)))
throw IloSchedulerException( "No solution for temporal model." );
IlcScheduler temporalScheduler(temporalSolver);
temporalSolution.store(temporalScheduler);
IloInt i;
for(i = 0; i < numberOfResources; ++i) {
IloActivity act = newJob[i].getActivity();
env.out() << "\t" << act.getName() << "["
<< temporalSolution.getStartMin(act)
<< ".." << temporalSolution.getStartMax(act)
<< " -- " << act.getProcessingTimeVariable().getLB()
<< " --> " << temporalSolution.getEndMin(act)
<< ".." << temporalSolution.getEndMax(act)
<< "]" << endl;
}
env.out() << "Maximum new makespan: "
<< temporalSolution.getSolution().getMax(makespan) << endl;
}
///////////////////////////////////////////////////////////////////////////////
//
// UPDATE TEMPORAL MODEL
//
///////////////////////////////////////////////////////////////////////////////
void UpdateTemporalModel(IloModel tModel,
IloSolver tSolver,
IloSchedulerSolution tSolution,
IloSchedulerSolution subSolution) {
// ADD THE START TIMES IN tSolution TO THE TEMPORAL MODEL
for(IloSchedulerSolution::ActivityIterator iter(subSolution);
iter.ok(); ++iter) {
IloActivity act = *iter;
tModel.add(act.startsAt(subSolution.getStartMin(act)));
}
if (!tSolver.solve(IloGoalTrue(tSolver.getEnv())
, IloSynchronizeAndContinue
)
)
throw IloSchedulerException( "No solution for temporal model" );
IlcScheduler scheduler(tSolver);
tSolution.store(scheduler);
}
///////////////////////////////////////////////////////////////////////////////
//
// CREATE THE DEFAULT SOLUTION
//
///////////////////////////////////////////////////////////////////////////////
IloSchedulerSolution CreateDefaultSolution(
IloSchedulerSolution originalSolution,
IloResourceConstraint* newJob,
IloNumVar makespan,
IloInt numberOfResources) {
// The simplest way to add the new job is simply to place it at the
// end of the existing schedule.
IloEnv env = originalSolution.getEnv();
IloNum newActStartMin = 0;
IloSchedulerSolution defaultSolution = originalSolution.makeClone(env);
for(IloInt i = 0; i < numberOfResources; ++i) {
IloResource resource = newJob[i].getResource();
// FIND THE ACTIVITY ON THE RESOURCE WITH THE MAX endMin
for(IloIterator<IloResourceConstraint> iter(env);
iter.ok(); ++iter) {
IloResourceConstraint rct = *iter;
if ((rct.getImpl() != newJob[i].getImpl()) &&
(rct.getResource().getImpl() == resource.getImpl()) &&
(defaultSolution.getEndMin(rct.getActivity()) > newActStartMin))
newActStartMin = defaultSolution.getEndMin(rct.getActivity());
}
IloActivity newAct = newJob[i].getActivity();
defaultSolution.add(newAct);
defaultSolution.setStartMin(newAct, newActStartMin);
newActStartMin += newAct.getProcessingTimeVariable().getLB();
}
IloNum mkspValue = defaultSolution.getSolution().getMin(makespan);
if (mkspValue < newActStartMin) {
defaultSolution.getSolution().setMin(makespan, newActStartMin);
defaultSolution.getSolution().setMax(makespan, newActStartMin);
}
return defaultSolution;
}
///////////////////////////////////////////////////////////////////////////////
//
// SUB-MODEL DEFINITION
//
///////////////////////////////////////////////////////////////////////////////
void
CreateSubmodel(IloSchedulerSolution temporalSolution,
IloModel& subModel,
IloSchedulerSolution& subSolution,
IloNumVar& optCriteria,
IloSchedulerSolution originalSolution,
IloResourceConstraint newRC) {
IloEnv env = temporalSolution.getEnv();
subModel = IloModel(env);
subSolution = IloSchedulerSolution(env);
IloActivity newAct = newRC.getActivity();
IloDiscreteResource reschedRes = newRC.getResource();
// GET THE TIME BOUNDS OF THE TO-BE-ADDED ACTIVITY
IloNum minTime = temporalSolution.getStartMin(newAct);
IloNum maxTime = temporalSolution.getEndMax(newAct);
env.out() << "Resource " << reschedRes.getName()
<< " on interval: [" << minTime << ".." << maxTime << "]"
<< endl;
// ADD THE NEW TIME BOUNDS AND RESOURCE CONSTRAINT
subModel.add(newAct.startsAfter(minTime));
subModel.add(newAct.endsBefore(maxTime));
subModel.add(newRC);
subSolution.add(newAct);
env.out() << "Adding " << newAct.getName() << endl;
IloNumVar maxEnd(env, minTime, maxTime, ILOINT);
subSolution.add(maxEnd);
subModel.add(newAct.endsBefore(maxEnd));
IloSchedulerEnv schedEnv(env);
IloNumToNumStepFunction initialOcc = schedEnv.getInitialOccupationParam();
initialOcc.setValue(initialOcc.getDefinitionIntervalMin(),
initialOcc.getDefinitionIntervalMax(), 0);
IloInt nbActsInSubmodel = 0;
IloNumVarArray hasChanged(env);
// ITERATE OVER THE RESOURCE CONSTRAINTS
for(IloIterator<IloResourceConstraint> iter(env); iter.ok(); ++iter) {
IloDiscreteResource res = (*iter).getResource();
IloActivity act = (*iter).getActivity();
if ((res.getImpl() == reschedRes.getImpl()) &&
(act.getImpl() != newAct.getImpl())) {
IloNum actStart = temporalSolution.getStartMin(act);
IloNum actEnd = temporalSolution.getEndMin(act);
if ((actStart >= minTime) && (actEnd <= maxTime)) {
// ADD TO MODEL THOSE ACTIVITIES HAVE A [MIN-START MIN-END]
// INTERVAL WHOLLY WITHIN THE INTERVAL OF THE NEW ACTIVITY
subModel.add((*iter));
subModel.add(act.startsAfter(actStart));
subModel.add(act.endsBefore(temporalSolution.getEndMax(act)));
subModel.add(act.endsBefore(maxEnd));
subSolution.add(act);
++nbActsInSubmodel;
hasChanged.add(IloNumVar(act.startsAfter(originalSolution.getStartMin(act)+1)));
}
else if ((actEnd > minTime) && (actStart < maxTime)) {
// FOR THE ACTIVITIES PARTIALLY IN THE INTERVAL, ADD THEM AS
// INITIAL OCCUPATION ON THE RESOURCE
actStart = IloMax(actStart, minTime);
actEnd = IloMin(actEnd, maxTime);
initialOcc.addValue(actStart, actEnd, (*iter).getCapacity());
}
}
}
// SET OPTIMIZATION CRITERIA TO BE A COMBINATION OF THE (LOCAL)
// MAKESPAN AND THE CHANGES FROM THE ORIGINAL MODEL
optCriteria = IloNumVar(env, 0, IloIntMax, ILOINT);
subModel.add(optCriteria == 1000 * maxEnd + IloSum(hasChanged));
subModel.add(IloMinimize(env, optCriteria));
}
IloBool CreateAndSolveSubmodel(IloSchedulerSolution temporalSolution,
IloSchedulerSolution& subSolution,
IloSchedulerSolution originalSolution,
IloResourceConstraint newRC,
IloNum& runningTime)
{
IloNumVar optCriteria;
IloModel subModel;
CreateSubmodel(temporalSolution, subModel, subSolution,
optCriteria, originalSolution, newRC);
IloInt failLimit = 1000;
IloBool solved = SolveModel(subModel, subSolution, optCriteria,
failLimit, runningTime);
// UNSET THE INITIAL OCCUPATION (MAY HAVE BEEN MODIFIED IN SUBMODEL)
IloSchedulerEnv schedEnv(temporalSolution.getEnv());
IloNumToNumStepFunction initialOcc = schedEnv.getInitialOccupationParam();
initialOcc.setValue(initialOcc.getDefinitionIntervalMin(),
initialOcc.getDefinitionIntervalMax(), 0);
//subModel.end();
return solved;
}
///////////////////////////////////////////////////////////////////////////////
//
// COUNT CHANGES IN START TIME ASSIGNMENTS
//
///////////////////////////////////////////////////////////////////////////////
IloInt CountChanges(IloSchedulerSolution originalSolution,
IloSchedulerSolution currentSolution) {
IloInt nbChanges = 0;
for(IloSchedulerSolution::ActivityIterator iter(currentSolution);
iter.ok(); ++iter) {
IloActivity act = *iter;
if (originalSolution.contains(act) &&
(originalSolution.getStartMin(act) !=
currentSolution.getStartMin(act)))
++nbChanges;
}
return nbChanges;
}
///////////////////////////////////////////////////////////////////////////////
//
// PRINTING OF SOLUTIONS
//
///////////////////////////////////////////////////////////////////////////////
void PrintRange(IloEnv& env, IloNum min, IloNum max) {
if (min == max)
env.out() << (IlcInt)min;
else
env.out() << (IlcInt)min << ".." << (IlcInt)max;
}
void PrintSolution(const IloSchedulerSolution solution,
const IloNumVar makespan)
{
IloEnv env = solution.getEnv();
env.out() << "Solution with makespan ["
<< solution.getSolution().getMin(makespan) << ".."
<< solution.getSolution().getMax(makespan) << "]" << endl;
for (IloSchedulerSolution::ActivityIterator iter(solution);
iter.ok();
++iter)
{
IloActivity activity = *iter;
env.out() << activity.getName() << "[";
PrintRange(env,
solution.getStartMin(activity),
solution.getStartMax(activity));
env.out() << " -- ";
PrintRange(env,
solution.getDurationMin(activity),
solution.getDurationMax(activity));
env.out() << " --> ";
PrintRange(env,
solution.getEndMin(activity),
solution.getEndMax(activity));
env.out() << "]" << endl;
}
}
void PrintSolutionComparison(IloSchedulerSolution currentSolution,
IloSchedulerSolution previousSolution,
IloSchedulerSolution originalSolution,
IloNumVar makespan) {
IloInt incrementalChanges = CountChanges(previousSolution,
currentSolution);
IloInt totalChanges = CountChanges(originalSolution,
currentSolution);
IloNum incrementalPercentIncrease =
(IloNum(currentSolution.getSolution().getValue(makespan)) -
IloNum(previousSolution.getSolution().getValue(makespan))) /
IloNum(previousSolution.getSolution().getValue(makespan)) * 100;
IloNum totalPercentIncrease =
(IloNum(currentSolution.getSolution().getValue(makespan)) -
IloNum(originalSolution.getSolution().getValue(makespan))) /
IloNum(originalSolution.getSolution().getValue(makespan)) * 100;
IloEnv env = currentSolution.getEnv();
env.out() << "\n\nNew job successfully added.\n\tTotal makespan: "
<< currentSolution.getSolution().getValue(makespan)
<< "\n\t% makespan increase (incremental) : "
<< incrementalPercentIncrease << "%"
<< "\n\t% makespan increase (overall) : "
<< totalPercentIncrease << "%"
<< "\n\tNumber of changes (incremental) : "
<< incrementalChanges
<< "\n\tNumber of changes (overall) : "
<< totalChanges << "\n" << endl;
}
void PrintFinalSolutionComparison(IloSchedulerSolution fromScratchSolution,
IloNum fromScratchSolveTime,
IloSchedulerSolution incSolution,
IloNum incSolveTime,
IloSchedulerSolution origSolution,
IloNum origSolveTime,
IloNumVar makespan,
IloNum nbOrigActs) {
// PRINT COMPARISON OF THE SOLVE-FROM-SCRATCH VS INCREMENTAL SOLVES
IloInt incChanges = CountChanges(origSolution,
incSolution);
IloInt scratchChanges = CountChanges(origSolution,
fromScratchSolution);
IloNum incPercentIncrease =
(IloNum(incSolution.getSolution().getValue(makespan)) -
IloNum(origSolution.getSolution().getValue(makespan))) /
IloNum(origSolution.getSolution().getValue(makespan)) * 100;
IloNum scratchPercentIncrease =
(IloNum(fromScratchSolution.getSolution().getValue(makespan)) -
IloNum(origSolution.getSolution().getValue(makespan))) /
IloNum(origSolution.getSolution().getValue(makespan)) * 100;
IloEnv env = origSolution.getEnv();
env.out() << "\nOriginal solve:"
<< "\nMakespan : "
<< origSolution.getSolution().getValue(makespan)
<< "\nRunning time : " << origSolveTime
<< "\n\nIncremental solves:"
<< "\nMakespan : "
<< incSolution.getSolution().getValue(makespan)
<< "\n% Makespan increase : " << incPercentIncrease << "%"
<< "\n% Activities changed : "
<< IloNum(incChanges) / nbOrigActs * 100 << "% ("
<< incChanges << ")"
<< "\nRunning time : " << incSolveTime
<< "\n\nSolve from scratch:"
<< "\nMakespan : "
<< fromScratchSolution.getSolution().getValue(makespan)
<< "\n% Makespan increase : " << scratchPercentIncrease << "%"
<< "\n% Activities changed : "
<< IloNum(scratchChanges) / nbOrigActs * 100 << "% ("
<< scratchChanges << ")"
<< "\nRunning time : " << fromScratchSolveTime
<< "\n" << endl;
}
///////////////////////////////////////////////////////////////////////////////
//
// SOLVE MODEL AFTER ADDING NEW JOB
//
///////////////////////////////////////////////////////////////////////////////
void ScheduleJob(IloModel evolvingModel,
IloSchedulerSolution originalSolution,
IloSchedulerSolution& evolvingSolution,
IloResourceConstraint* newJob,
IloNumVar makespan,
IloInt numberOfResources,
IloNum& incRunningTime) {
IloEnv env = evolvingModel.getEnv();
// CREATE DEFAULT SOLUTION IN CASE WE FAIL TO INCORPORATE NEW JOB
IloSchedulerSolution defaultSolution =
CreateDefaultSolution(evolvingSolution, newJob,
makespan, numberOfResources);
// CREATE AND PROPAGATE TEMPORAL MODEL INCLUDING NEW JOB
IloModel temporalModel;
IloSchedulerSolution temporalSolution;
IloSolver temporalSolver;
CreateAndSolveTemporalModel(evolvingSolution, newJob,
numberOfResources, makespan,
temporalSolver, temporalModel,
temporalSolution);
// SCHEDULE EACH ACTIVITY IN THE NEW JOB
IloInt i;
IloBool solved = IloTrue;
for(i = 0; (i < numberOfResources) && solved; ++i) {
env.out() << "\n**** Submodel: " << i << " ****" << endl;
IloSchedulerSolution subSolution;
IloNum subRunningTime;
solved = CreateAndSolveSubmodel(temporalSolution,
subSolution, evolvingSolution,
newJob[i], subRunningTime);
incRunningTime += subRunningTime;
if (solved) {
// UPDATE TEMPORAL MODEL WITH SUBMODEL SOLUTION
UpdateTemporalModel(temporalModel, temporalSolver,
temporalSolution, subSolution);
IloInt nbChanges = CountChanges(evolvingSolution,
subSolution);
env.out() << "Subproblem solved.\n\tTotal makespan: "
<< temporalSolution.getMin(makespan)
<< "\n\tNumber of changes in sub-solution: "
<< nbChanges << endl;
}
else {
env.out() << "Failure to solve subproblem! "
<< "Reverting to default solution." << endl;
}
subSolution.end();
}
if (solved) {
// ASSIGN THE MAKESPAN TO MIN VALUE
temporalSolution.getSolution().setMax(makespan,
temporalSolution.getSolution().getMin(makespan));
PrintSolutionComparison(temporalSolution, evolvingSolution,
originalSolution, makespan);
evolvingSolution.end();
evolvingSolution = temporalSolution.makeClone(env);
}
else {
// ONE OF THE SUBMODELS COULD NOT BE SOLVED WITHIN THE FAILURE
// LIMITS. FALL BACK TO THE DEFAULT SOLUTION
PrintSolutionComparison(defaultSolution, evolvingSolution,
originalSolution, makespan);
evolvingSolution.end();
evolvingSolution = defaultSolution.makeClone(env);
}
temporalSolution.end();
temporalSolver.end();
defaultSolution.end();
}
///////////////////////////////////////////////////////////////////////////////
//
// PARAMETERS
//
///////////////////////////////////////////////////////////////////////////////
void InitParameters(int argc,
char** argv,
IloNum& resourceCap,
IloInt& numberOfJobs,
IloInt& numberOfResources,
IloInt*& resourceNumbers,
IloNum*& durations)
{
resourceCap = 3;
numberOfJobs = 6;
numberOfResources = 6;
resourceNumbers = ResourceNumbers06;
durations = Durations06;
if (argc > 1) {
IloInt number = atol(argv[1]);
if (number == 10) {
numberOfJobs = 10;
numberOfResources = 10;
resourceNumbers = ResourceNumbers10;
durations = Durations10;
}
else if (number == 20) {
numberOfJobs = 20;
numberOfResources = 5;
resourceNumbers = ResourceNumbers20;
durations = Durations20;
}
}
if (argc > 2)
resourceCap = atol(argv[2]);
}
///////////////////////////////////////////////////////////////////////////////
//
// MAIN FUNCTION
//
///////////////////////////////////////////////////////////////////////////////
int main(int argc, char** argv)
{
IloNum resourceCapacity;
IloInt numberOfJobs;
IloInt numberOfResources;
IloInt* resourceNumbers;
IloNum* durations;
InitParameters(argc,
argv,
resourceCapacity,
numberOfJobs,
numberOfResources,
resourceNumbers,
durations);
try {
IloEnv env;
IloNumVar makespan;
env.out() << "\n**** Original Model ****" << endl;
IloSchedulerSolution originalSolution;
IloModel originalModel;
// DEFINE ORIGINAL MODEL
CreateOriginalModel(env, resourceCapacity,
numberOfJobs, numberOfResources,
resourceNumbers, durations, makespan,
originalModel, originalSolution);
// SOLVE ORIGINAL MODEL
IloInt failLimit = 5000;
IloNum originalRunningTime;
IloBool solved = SolveModel(originalModel, originalSolution,
makespan,
failLimit, originalRunningTime);
if (!solved)
throw IloSchedulerException( "No solution found to original model." );
PrintSolution(originalSolution, makespan);
IloNum incRunningTime = 0;
IloSchedulerSolution evolvingSolution = originalSolution.makeClone(env);
// ADD NEW JOBS, EVERY TIME A JOB IS ADDED, INCREMENTALLY RE-SOLVE
IloInt nbNewJobs = numberOfJobs;
IloResourceConstraint *newJob =
new (env) IloResourceConstraint[numberOfResources];
for(IloInt j = 0; j < nbNewJobs; ++j) {
env.out() << "\nAdding new job: NJ" << j << endl;
// CREATE NEW JOB
AddNewJob(originalModel, j, newJob, makespan,
numberOfJobs, numberOfResources, durations);
// INCORPORATE NEW JOB INTO SCHEDULE
ScheduleJob(originalModel, originalSolution, evolvingSolution,
newJob, makespan, numberOfResources,
incRunningTime);
}
// SOLVE COMPLETE MODEL (ORIGINAL + NEW JOBS) FROM SCRATCH
env.out() << "\n **** Complete Model ***" << endl;
IloSchedulerSolution totalSolution = evolvingSolution.makeClone(env);
IloNum totalRunningTime;
solved = SolveModel(originalModel, totalSolution,
makespan,
failLimit, totalRunningTime);
if (!solved)
throw IloSchedulerException( "No solution found for overall model." );
// COMPARE ORIGINAL SOLUTION TO INCREMENTAL AND FROM SCRATCH SOLUTIONS
IloNum nbOrigActs = numberOfJobs * numberOfResources * resourceCapacity;
PrintFinalSolutionComparison(totalSolution, totalRunningTime,
evolvingSolution, incRunningTime,
originalSolution, originalRunningTime,
makespan, nbOrigActs);
PrintSolution(totalSolution, makespan);
totalSolution.end();
evolvingSolution.end();
originalSolution.end();
env.end();
} catch (IloSchedulerException& exc) {
cout << exc << endl;
} catch (IloException& exc) {
cout << exc << endl;
}
return 0;
}
PREVIOUS
NEXT