You can see the entire program altlns.cpp here or view it online in the standard distribution.
#include <ilsched/ilolnsgoals.h>
#include <ilsolver/iimls.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};
///////////////////////////////////////////////////////////////////
//
// 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(IloEnv& env,
const IloSchedulerSolution solution,
const IloNumVar makespan)
{
if (solution.contains(makespan)) {
env.out() << "Solution with makespan ["
<< solution.getMin(makespan) << ".."
<< solution.getMax(makespan) << "]" << endl;
}
for (IloSchedulerSolution::ResourceConstraintIterator
iter(solution);
iter.ok();
++iter)
{
IloResourceConstraint rc = *iter;
if (!solution.isResourceSelected(rc))
IloSchedulerException("No resource assigned!");
IloActivity activity = rc.getActivity();
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() << "]: " << solution.getSelected(rc).getName()
<< endl;
}
}
////////////////////////////////////////////////////////////////////
//
// FIND A FIRST SOLUTION
//
////////////////////////////////////////////////////////////////////
void FindInitialSolution(IloModel model,
IloSchedulerSolution globalSolution,
IloSchedulerSolution lsSolution,
IloNumVar costVar) {
IloEnv env = model.getEnv();
IloSolver solver(model);
IlcScheduler scheduler(solver);
IloGoal g = IloAssignAlternative(env) &&
IloRankForward(env) &&
IloInstantiate(env, costVar);
solver.startNewSearch(g);
if(solver.next()) {
IloNum best = solver.getValue(costVar);
solver.out() << "Solution for Cost " << best << endl;
solver.printInformation();
globalSolution.store(scheduler);
lsSolution.store(scheduler);
}
solver.endSearch();
solver.end();
}
////////////////////////////////////////////////////////////////////
//
// DEFINE A NEW NEIGHBORHOOD : RELOCATE JOB
//
////////////////////////////////////////////////////////////////////
class RelocateJobNHoodI : public IloSchedulerLargeNHoodI {
protected:
IloArray<IloActivityArray> _jobs;
public:
RelocateJobNHoodI(IloEnv env,
IloArray<IloActivityArray> jobs,
const char* name);
~RelocateJobNHoodI();
// virtuals
virtual IloInt getSize(IloSolver solver) const;
virtual IloSolution defineSelected(IloSolver solver, IloInt index);
virtual void start(IloSolver solver, IloSolution solution);
};
ILOPREDICATE0(IloRCFalsePredicate,
IloResourceConstraint, rc) {
return IloFalse;
}
ILOCTXPREDICATE0(IloRCTrueIfNotSelectedPredicate,
IloResourceConstraint, rc,
IloSchedulerLargeNHood, nhood) {
if (nhood.isSelected(rc))
return IloFalse;
else
return IloTrue;
}
ILOPREDICATE0(IloActivityFalsePredicate,
IloActivity, activity) {
return IloFalse;
}
RelocateJobNHoodI::RelocateJobNHoodI(IloEnv env,
IloArray<IloActivityArray> jobs,
const char* name)
: IloSchedulerLargeNHoodI(env, name),
_jobs(env)
{
// set default restore policy
IloPredicate<IloResourceConstraint> rcFalsePredicate =
IloRCFalsePredicate(env);
setRestoreRCNextPredicate(rcFalsePredicate);
setRestoreRCPrevPredicate(rcFalsePredicate);
setRestoreRCSetupPredicate(rcFalsePredicate);
setRestoreRCTeardownPredicate(rcFalsePredicate);
IloPredicate<IloResourceConstraint> rcTrueIfNotSelectedPredicate =
IloRCTrueIfNotSelectedPredicate(env);
setRestoreRCDirectSuccessorPredicate(rcTrueIfNotSelectedPredicate);
setRestoreRCDirectPredecessorPredicate(rcTrueIfNotSelectedPredicate);
setRestoreRCCapacityPredicate(rcTrueIfNotSelectedPredicate);
setRestoreRCSelectedPredicate(rcTrueIfNotSelectedPredicate);
IloPredicate<IloActivity> activityFalsePredicate =
IloActivityFalsePredicate(env);
setRestoreActivityStartPredicate(activityFalsePredicate);
setRestoreActivityEndPredicate(activityFalsePredicate);
setRestoreActivityDurationPredicate(activityFalsePredicate);
setRestoreActivityProcessingTimePredicate(activityFalsePredicate);
setRestoreActivityExternalPredicate(activityFalsePredicate);
for (IloInt j=0; j<jobs.getSize(); ++j) {
IloInt nbActivities = jobs[j].getSize();
IloActivityArray job(env);
for (IloInt a=0; a<nbActivities; ++a) {
IloActivity activity = jobs[j][a];
job.add(activity);
}
_jobs.add(job);
}
}
RelocateJobNHoodI::~RelocateJobNHoodI()
{
_jobs.end();
}
void
RelocateJobNHoodI::start(IloSolver solver, IloSolution solution)
{
IloSchedulerLargeNHoodI::start(solver, solution);
}
IloInt
RelocateJobNHoodI::getSize(IloSolver solver) const
{
IloInt size = _jobs.getSize();
return size;
}
IloSolution
RelocateJobNHoodI::defineSelected(IloSolver solver, IloInt index)
{
IloEnv env = solver.getEnv();
IloActivityArray job;
job = _jobs[index];
IloSchedulerSolution selected(env);
IloSchedulerSolution currentSolution = getCurrentSolution();
// add in selected all activities of selected job and their
// resource constraints
IloInt nbActivities = job.getSize();
for (IloInt a=0; a<nbActivities; a++) {
IloActivity activity = job[a];
selected.add(activity);
IloSchedulerSolution::ResourceConstraintIterator
rcIter(currentSolution, activity);
for (; rcIter.ok(); ++rcIter) {
IloResourceConstraint rc = *rcIter;
selected.add(rc);
}
}
return selected;
}
IloSchedulerLargeNHood
RelocateJobNHood(IloEnv env,
IloArray<IloActivityArray> jobs,
const char* name = 0)
{
return new (env) RelocateJobNHoodI(env,
jobs,
name);
}
IloSchedulerSolution CreateLSSolution(IloEnv env,
IloSchedulerSolution globalSolution) {
/* CREATE LOCAL SEARCH SOLUTION */
IloSchedulerSolution lsSolution = globalSolution.makeClone(env);
for (IloIterator <IloResourceConstraint> iter(env); iter.ok(); ++iter)
lsSolution.setRestorable(*iter,
IloRestoreRCNext | IloRestoreRCSelected);
for (IloIterator <IloResource> resIter(env); resIter.ok(); ++resIter)
lsSolution.add(*resIter);
return lsSolution;
}
////////////////////////////////////////////////////////////////////
//
// SOLVE THE MODEL USING A GREEDY DESCENT SEARCH
//
////////////////////////////////////////////////////////////////////
void SolveModel(IloModel model,
IloNumVar makespan,
IloArray<IloActivityArray> jobs,
IloSchedulerSolution& globalSolution) {
IloEnv env = model.getEnv();
/* CREATE LOCAL SEARCH SOLUTION */
IloSchedulerSolution lsSolution = CreateLSSolution(env, globalSolution);
IloObjective obj = IloMinimize(env, makespan);
lsSolution.getSolution().add(obj);
globalSolution.getSolution().add(makespan);
/* GENERATE AN INITIAL SOLUTION. */
FindInitialSolution(model, globalSolution, lsSolution, makespan);
IloNum best = globalSolution.getMax(makespan);
env.out() << "Initial solution:" << endl;
PrintSolution(env, globalSolution, makespan);
/* SET PARAMETERS FOR LOCAL SEARCH */
IloSolver lsSolver(model);
IlcScheduler lsScheduler(lsSolver);
/* GLIDING TIME WINDOW SEARCH */
IloGoal subGoal =
IloAssignAlternative(env) &&
IloRankForward(env) &&
IloInstantiate(env, makespan);
IloInt failLimit = 2000;
if (failLimit < IloIntMax) {
subGoal = IloLimitSearch(env, subGoal, IloFailLimit(env, failLimit));
}
subGoal = IloSelectSearch(env, subGoal, IloMinimizeVar(env, makespan, 1.0));
IloSchedulerLargeNHood relocateActivities = IloRelocateActivityNHood(env);
IloSchedulerLargeNHood timeWindowNHood =
IloTimeWindowNHood(env, 20, 10);
IloSchedulerLargeNHood relocateJobNHood = RelocateJobNHood(env, jobs);
IloNHood nhood =
IloContinue(env, relocateActivities)
+
IloContinue(env, relocateJobNHood)
+
IloContinue(env, timeWindowNHood)
;
IloGoal greedyMove = IloSingleMove(env,
lsSolution,
nhood,
IloImprove(env),
IloFirstSolution(env),
subGoal);
IloInt movesDone = 0;
while(lsSolver.solve(greedyMove)) {
IloNum cost = lsSolution.getSolution().getObjectiveValue();
lsSolver.out() << "Move: " << movesDone << ":\t";
++movesDone;
lsSolver.out() << "solution at cost: " << cost << " ** HC" << endl;
best = cost;
globalSolution.store(lsScheduler);
}
env.out() << "Final solution Cost: " << best << endl;
PrintSolution(env, globalSolution, makespan);
lsSolver.end();
}
////////////////////////////////////////////////////////////////////
//
// DEFINE THE MODEL WITH ALTERNATIVE RESOURCES
//
////////////////////////////////////////////////////////////////////
IloModel
DefineModel(IloEnv& env,
IloInt numberOfJobs,
IloInt numberOfResources,
IloInt* resourceNumbers,
IloNum* durations,
IloRandom randomGenerator,
IloSchedulerSolution solution,
IloArray<IloActivityArray>& jobs,
IloNumVar& makespan)
{
IloModel model(env);
/* CREATE THE MAKESPAN VARIABLE. */
IloInt numberOfActivities = numberOfJobs * numberOfResources;
IloNum horizon = 0;
IloInt k;
for (k = 0; k < numberOfActivities; k++)
horizon += durations[k];
makespan = IloNumVar(env, 0, IloIntMax/2, ILOINT);
/* CREATE THE RESOURCES. */
IloSchedulerEnv schedEnv(env);
IloResourceParam resParam = schedEnv.getResourceParam();
resParam.setCapacityEnforcement(IloMediumLow);
char buffer[128];
IloInt j;
IloUnaryResource *resources =
new (env) IloUnaryResource[numberOfResources];
for (j = 0; j < numberOfResources; j++) {
sprintf(buffer, "R%ld", j);
resources[j] = IloUnaryResource(env, buffer);
}
/* CREATE THE ALTERNATIVE RESOURCE SETS */
env.out() << "Creating resource sets" << endl;
IloInt *altResourceNumbers = new (env) IloInt[numberOfResources];
IloAltResSet *altResSets =
new (env) IloAltResSet[numberOfResources];
for (j = 0; j < numberOfResources; j++) {
altResSets[j] = IloAltResSet(env);
altResSets[j].add(resources[j]);
// RANDOMLY PICK ANOTHER RESOURCE TO BE IN THE SET
assert(numberOfResources > 1);
IloInt index = randomGenerator.getInt(numberOfResources);
while(index == j)
index = randomGenerator.getInt(numberOfResources);
altResSets[j].add(resources[index]);
altResourceNumbers[j] = index;
env.out() << "Set #" << j << ":\t" << resources[j].getName()
<< " " << resources[index].getName() << endl;
}
/* CREATE THE ALTERNATIVE DURATIONS */
IloNum *altDurations = new (env) IloNum[numberOfActivities];
for(k = 0; k < numberOfActivities; k++) {
IloNum multiplier = 1.0 + (randomGenerator.getFloat() / 2.0);
altDurations[k] = IloCeil(multiplier * durations[k]);
}
/* CREATE THE ACTIVITIES. */
env.out() << "Setting alternative processing times" << endl;
k = 0;
IloInt i;
jobs = IloArray<IloActivityArray>(env);
for (i = 0; i < numberOfJobs; i++) {
IloActivityArray job(env);
jobs.add(job);
IloActivity previousActivity;
for (j = 0; j < numberOfResources; j++) {
IloNum ptMin = IloMin(durations[k], altDurations[k]);
IloNum ptMax = IloMax(durations[k], altDurations[k]);
IloNumVar ptVar(env, ptMin, ptMax, ILOINT);
IloActivity activity(env, ptVar);
job.add(activity);
sprintf(buffer, "J%ldS%ldR%ld", i, j, resourceNumbers[k]);
activity.setName(buffer);
solution.add(activity, IloRestoreNothing);
IloResourceConstraint rc =
activity.requires(altResSets[resourceNumbers[k]]);
// SET THE DIFFERENT DURATIONS DEPENDING ON
// RESOURCE SELECTION
rc.setProcessingTimeMax(resources[resourceNumbers[k]],
durations[k]);
rc.setProcessingTimeMin(resources[resourceNumbers[k]],
durations[k]);
rc.setProcessingTimeMax(
resources[altResourceNumbers[resourceNumbers[k]]],
altDurations[k]);
rc.setProcessingTimeMin(
resources[altResourceNumbers[resourceNumbers[k]]],
altDurations[k]);
model.add(rc);
solution.add(rc, IloRestoreNothing);
env.out() << activity.getName()
<< ":\tProcessing Time("
<< resources[resourceNumbers[k]].getName()
<< "): " << durations[k]
<< "\n\tProcessing Time("
<< resources[altResourceNumbers[
resourceNumbers[k]]].getName()
<< "): " << altDurations[k]
<< endl;
if (j != 0)
model.add(activity.startsAfterEnd(previousActivity));
previousActivity = activity;
k++;
}
model.add(previousActivity.endsBefore(makespan));
}
/* RETURN THE MODEL. */
return model;
}
/////////////////////////////////////////////////////////////////
//
// INITIALIZE THE PROGRAM ARGUMENTS
//
/////////////////////////////////////////////////////////////////
void
InitParameters(int argc,
char** argv,
IloInt& numberOfJobs,
IloInt& numberOfResources,
IloInt*& resourceNumbers,
IloNum*& durations)
{
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;
}
}
}
/////////////////////////////////////////////////////////////////
//
// MAIN FUNCTION
//
/////////////////////////////////////////////////////////////////
int main(int argc, char** argv)
{
IloInt numberOfJobs;
IloInt numberOfResources;
IloInt* resourceNumbers;
IloNum* durations;
InitParameters(argc,
argv,
numberOfJobs,
numberOfResources,
resourceNumbers,
durations);
try {
IloEnv env;
IloNumVar makespan;
IloArray<IloActivityArray> jobs;
IloRandom randGen(env, 8975324);
IloSchedulerSolution solution(env);
IloModel model = DefineModel(env,
numberOfJobs,
numberOfResources,
resourceNumbers,
durations,
randGen,
solution,
jobs,
makespan);
SolveModel(model, makespan, jobs, solution);
env.end();
}
catch (IloSchedulerException& exc) {
cout << exc << endl;
}
catch (IloException& exc) {
cout << exc << endl;
}
return 0;
}
PREVIOUS
NEXT