You can see the entire program altls.cpp here or view it online in the standard distribution.
#include <ilsched/iloscheduler.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)
{
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;
}
}
///////////////////////////////////////////////////////////////////////////////
//
// MOVES
//
// These are classes that will be associated with a specific
// neighborhood and represent a particular type of local search move
//
///////////////////////////////////////////////////////////////////////////////
// Abstract move object
class LSMove {
public:
LSMove() {}
virtual ~LSMove() {}
virtual IloBool isReverseMove(IloSolution delta) const = 0;
virtual IloSolution createDelta(IloEnv, IloSchedulerSolution) = 0;
};
class SwapRC : public LSMove {
// This class represents the data to perform a swap of _rc and
// _after in the sequence
private:
IloResourceConstraint _rc;
IloResourceConstraint _after;
public:
SwapRC() : _rc(0), _after(0) {}
SwapRC(IloResourceConstraint rc, IloResourceConstraint after)
: _rc(rc), _after(after) {}
virtual ~SwapRC() {}
IloResourceConstraint getRC() const { return _rc; }
IloResourceConstraint getAfter() const { return _after; }
void setRC(IloResourceConstraint rc) { _rc = rc; }
void setAfter(IloResourceConstraint after) { _after = after; }
virtual IloBool isReverseMove(IloSolution delta) const {
IloSchedulerSolution schedDelta(delta);
return (schedDelta.contains(_rc) &&
schedDelta.getNextRC(_rc).getImpl() == _after.getImpl());
}
virtual IloSolution createDelta(IloEnv, IloSchedulerSolution);
static SwapRC* findSwapFromDelta(IloSolver, IloSolution,
IloSchedulerSolution);
};
SwapRC* SwapRC::findSwapFromDelta(IloSolver solver,
IloSolution delta,
IloSchedulerSolution current) {
// Try to generate a SwapRC move from the information in delta. This may
// fail as delta does not necessarily represent a SwapRC move
IloSchedulerSolution solution(delta);
for(IloSchedulerSolution::ResourceConstraintIterator preiter(solution);
preiter.ok(); ++preiter) {
IloResourceConstraint rc = *preiter;
if (solution.getSelected(rc).getImpl() !=
current.getSelected(rc).getImpl())
return 0;
}
// find the element that is not next of any element in the delta
IloResourceConstraint first;
for(IloSchedulerSolution::ResourceConstraintIterator iter(solution);
iter.ok() && (0 == first.getImpl()); ++iter) {
first = *iter;
for(IloSchedulerSolution::ResourceConstraintIterator iter2(solution);
iter2.ok() && (0 != first.getImpl()); ++iter2) {
IloResourceConstraint rc = *iter2;
if (rc.getImpl() != first.getImpl()) {
if (solution.hasNextRC(rc) &&
(solution.getNextRC(rc).getImpl() == first.getImpl()))
first = 0;
}
}
}
assert(0 != first.getImpl());
IloResourceConstraint second = solution.getNextRC(first);
IloResourceConstraint third = solution.getNextRC(second);
if (0 == third.getImpl())
return new (solver.getEnv()) SwapRC(second, first);
else
return new (solver.getEnv()) SwapRC(third, second);
}
IloSolution SwapRC::createDelta(IloEnv env, IloSchedulerSolution current) {
IloSchedulerSolution swapDelta(env);
// old order: before -> _rc -> _after -> afterAfter
// new order: before -> _after -> _rc -> afterAfter
swapDelta.add(_rc, current.getRestorable(_rc));
swapDelta.getSolution().copy(_rc, current);
swapDelta.unsetNext(_rc, current.getNextRC(_rc));
swapDelta.add(_after, current.getRestorable(_after));
swapDelta.getSolution().copy(_after, current);
if (current.hasNextRC(_after))
swapDelta.unsetNext(_after, current.getNextRC(_after));
// change beforeBefore --> _rc to beforeBefore --> _after
// IloResourceConstraint before = getBefore();
IloResourceConstraint before = current.getPrevRC(_rc);
if (before.getImpl() != 0) {
swapDelta.add(before, current.getRestorable(before));
swapDelta.getSolution().copy(before, current);
swapDelta.unsetNext(before, current.getNextRC(before));
swapDelta.setNext(before, _after);
}
// change _after --> afterAfter to _after --> _rc
swapDelta.setNext(_after, _rc);
// change _rc --> _after to _rc --> afterAfter
if (current.hasNextRC(_after))
swapDelta.setNext(_rc, current.getNextRC(_after));
return swapDelta;
}
class RelocateRC : public LSMove {
// This class represents the data to perform a relocate of _and
// _after in the sequence
private:
IloResourceConstraint _relocated;
IloResource _to;
IloResourceConstraint _beforeInsertion;
public:
RelocateRC() : _relocated(0),_to(0),_beforeInsertion(0) {}
RelocateRC(IloResourceConstraint rc,
IloResource to,
IloResourceConstraint before)
: _relocated(rc), _to(to), _beforeInsertion(before) {}
virtual ~RelocateRC() {}
IloResourceConstraint getRC() const { return _relocated; }
IloResource getTo() const { return _to; }
void setRC(IloResourceConstraint rc) { _relocated = rc; }
void setTo(IloResource res) { _to = res; }
void setBeforeInsertion(IloResourceConstraint before) {
_beforeInsertion = before;
}
virtual IloBool isReverseMove(IloSolution delta) const {
IloSchedulerSolution schedDelta(delta);
return (schedDelta.contains(_relocated) &&
(schedDelta.getSelected(_relocated).getImpl() != _to.getImpl()));
}
virtual IloSolution createDelta(IloEnv, IloSchedulerSolution);
static RelocateRC* findRelocateFromDelta(IloSolver,
IloSolution, IloSchedulerSolution);
};
IloSolution RelocateRC::createDelta(IloEnv env, IloSchedulerSolution current) {
IloSchedulerSolution relocateDelta(env);
// old state: _relocated is not on resource _to
// new state: _relocated is on resource _to after _beforeInsertion
// set the selected resource of _relocated
relocateDelta.add(_relocated, current.getRestorable(_relocated));
relocateDelta.setSelected(_relocated, _to);
if (current.hasNextRC(_relocated))
relocateDelta.unsetNext(_relocated, current.getNextRC(_relocated));
// set the next of _relocated
IloResourceConstraint afterInsertion;
if (_beforeInsertion.getImpl() == 0)
// insert _relocated as the first rc on _to
afterInsertion = current.getSetupRC(_to);
else
afterInsertion = current.getNextRC(_beforeInsertion);
if (afterInsertion.getImpl() != 0)
relocateDelta.setNext(_relocated, afterInsertion);
// set the next of _beforeInsertion
if (_beforeInsertion.getImpl() != 0) {
relocateDelta.add(_beforeInsertion,
current.getRestorable(_beforeInsertion));
relocateDelta.getSolution().copy(_beforeInsertion, current);
if (relocateDelta.hasNextRC(_beforeInsertion))
relocateDelta.unsetNext(_beforeInsertion,
current.getNextRC(_beforeInsertion));
relocateDelta.setNext(_beforeInsertion, _relocated);
}
// change the rc that was before _relocated in the previous solution
IloResourceConstraint oldBefore =
current.getPrevRC(_relocated);
if (oldBefore.getImpl() != 0) {
relocateDelta.add(oldBefore,
current.getRestorable(oldBefore));
relocateDelta.getSolution().copy(oldBefore, current);
relocateDelta.unsetNext(oldBefore, _relocated);
if (current.hasNextRC(_relocated))
relocateDelta.setNext(oldBefore, current.getNextRC(_relocated));
}
return relocateDelta;
}
RelocateRC* RelocateRC::findRelocateFromDelta(IloSolver solver,
IloSolution delta,
IloSchedulerSolution current) {
// Try to generate a RelocateRC move from the information in delta.
// This may fail as delta does not necessarily represent a SwapRC
// move
IloSchedulerSolution solution(delta);
IloResourceConstraint resChange;
for(IloSchedulerSolution::ResourceConstraintIterator iter2(solution);
iter2.ok() && (resChange.getImpl() == 0); ++iter2) {
resChange = *iter2;
if (solution.getSelected(resChange).getImpl() ==
current.getSelected(resChange).getImpl())
resChange = 0;
}
if (0 == resChange.getImpl())
return 0;
// find the element that is not next of any element in the delta
IloResourceConstraint first;
for(IloSchedulerSolution::ResourceConstraintIterator iter(solution);
iter.ok() && (0 == first.getImpl()); ++iter) {
first = *iter;
for(IloSchedulerSolution::ResourceConstraintIterator iter3(solution);
iter3.ok() && (0 != first.getImpl()); ++iter3) {
IloResourceConstraint rc = *iter3;
if (rc.getImpl() != first.getImpl()) {
if (solution.hasNextRC(rc) &&
(solution.getNextRC(rc).getImpl() == first.getImpl()))
first = 0;
}
}
}
assert(0 != first.getImpl());
if (first.getImpl() == resChange.getImpl())
return new (solver.getEnv()) RelocateRC(first,
solution.getSelected(first),
0);
else
return new (solver.getEnv()) RelocateRC(resChange,
solution.getSelected(resChange),
first);
}
///////////////////////////////////////////////////////////////////////////////
//
// UTILITIES
//
// We use some utilities classes to help carry out the features common
// to the neighborhoods we use
//
///////////////////////////////////////////////////////////////////////////////
///////////////////////////////////////////////////////////////////////////////
//
// Critical Path Object: This object computes and returns a set of
// resource constraints that constitute a randomly selected critical
// path in the current solution
//
///////////////////////////////////////////////////////////////////////////////
class RCSortElement {
private:
IloResourceConstraint _rc;
IloInt _startValue;
IloInt _tieBreaker;
public:
RCSortElement() : _rc(0), _startValue(0), _tieBreaker(0) {}
RCSortElement(IloResourceConstraint rc, IloInt startValue, IloInt tieBreaker)
: _rc(rc), _startValue(startValue), _tieBreaker(tieBreaker) {}
IloResourceConstraint getRC() { return _rc; }
IloInt getStartValue() { return _startValue; }
IloInt getTieBreaker() { return _tieBreaker; }
void setRC(IloResourceConstraint rc) { _rc = rc; }
void setStartValue(IloInt st) { _startValue = st; }
void setTieBreaker(IloInt tie) { _tieBreaker = tie; }
};
static
int RCSortElementAscendingSTCompare(const void* first,
const void* second)
{
RCSortElement *a = (RCSortElement *) first;
RCSortElement *b = (RCSortElement *) second;
if (a->getStartValue() > b->getStartValue())
return 1;
else if (a->getStartValue() < b->getStartValue())
return -1;
else if (a->getTieBreaker() > b->getTieBreaker())
return 1;
else if (a->getTieBreaker() < b->getTieBreaker())
return -1;
return 0;
}
class CriticalPath {
private:
IloBool _needsRecomputing;
IloInt _cpSize;
IloArray<IloResourceConstraint> _cpArray;
IloRandom _randGen;
RCSortElement *getCriticalRCs(IloSchedulerSolution, IloInt&);
void pickRandomCP(RCSortElement *, IloSchedulerSolution,IloInt);
void addCPElement(IloResourceConstraint);
public:
CriticalPath(IloEnv env) :
_needsRecomputing(IloTrue), _cpSize(0),
_cpArray(env), _randGen(env, 98998) {}
~CriticalPath() {}
void needsRecomputing() { _needsRecomputing = IloTrue; }
IloArray<IloResourceConstraint>& computeCP(IloSchedulerSolution, IloInt&);
};
RCSortElement *CriticalPath::getCriticalRCs(IloSchedulerSolution solution,
IloInt& nbCriticalRCs) {
// count the number of RCs with assigned start times
for(IloSchedulerSolution::ResourceConstraintIterator iter(solution);
iter.ok(); ++iter) {
IloResourceConstraint rc = *iter;
IloActivity act = rc.getActivity();
if (solution.getStartMin(act) == solution.getStartMax(act))
++nbCriticalRCs;
}
// populate array
RCSortElement *sortArray = new RCSortElement[nbCriticalRCs];
IloInt index = 0;
for(IloSchedulerSolution::ResourceConstraintIterator iter2(solution);
iter2.ok(); ++iter2) {
IloResourceConstraint rc = *iter2;
IloActivity act = rc.getActivity();
if (solution.getStartMin(act) == solution.getStartMax(act)) {
sortArray[index].setRC(rc);
sortArray[index].setStartValue( (IloInt)solution.getStartMin(act) );
sortArray[index].setTieBreaker(index);
++index;
}
}
// order in ascending start time
qsort(sortArray, nbCriticalRCs,
sizeof(RCSortElement), RCSortElementAscendingSTCompare);
return sortArray;
}
void CriticalPath::addCPElement(IloResourceConstraint rc) {
if (_cpSize < _cpArray.getSize())
// reuse
_cpArray[_cpSize] = rc;
else
// add
_cpArray.add(rc);
_cpSize++;
}
void CriticalPath::pickRandomCP(RCSortElement *sortArray,
IloSchedulerSolution solution,
IloInt nbCriticalRCs) {
_cpSize = 0;
IloInt endRC = 0;
IloInt i = -1;
while(i < nbCriticalRCs - 1) {
// skip elements not on the same critical path as rc
IloInt nextIndexStart = i + 1;
while((nextIndexStart < nbCriticalRCs) &&
(sortArray[nextIndexStart].getStartValue() < endRC))
nextIndexStart++;
// gather elements that are successors of rc on the critical
// path. There may be more than one
IloInt nextIndexEnd = nextIndexStart + 1;
while((nextIndexEnd < nbCriticalRCs) &&
(sortArray[nextIndexEnd].getStartValue() == endRC))
nextIndexEnd++;
if (nextIndexStart < nbCriticalRCs) {
// At this point the elements between sortArray[nextIndexStart]
// and sortArray[nextIndexEnd-1] inclusive are all successors to
// rc on some critical path.
// We randomly pick one of them.
IloInt randIndex = nextIndexStart;
IloInt indexDiff = nextIndexEnd - nextIndexStart;
if (indexDiff > 1)
randIndex += _randGen.getInt(indexDiff);
IloResourceConstraint next = sortArray[randIndex].getRC();
addCPElement(next);
i = randIndex;
endRC = (IloInt)solution.getEndMin(next.getActivity());
}
else
i = nbCriticalRCs;
}
}
IloArray<IloResourceConstraint>& CriticalPath::computeCP(
IloSchedulerSolution solution,
IloInt& cpSize) {
if (_needsRecomputing) {
IloInt nbCriticalRCs = 0;
RCSortElement *sortArray = getCriticalRCs(solution, nbCriticalRCs);
// pick one (randomly selected) critical path
pickRandomCP(sortArray, solution, nbCriticalRCs);
delete [] sortArray;
_needsRecomputing = IloFalse;
}
cpSize = _cpSize;
return _cpArray;
}
///////////////////////////////////////////////////////////////////////////////
//
// NEIGHBORHOODS
//
///////////////////////////////////////////////////////////////////////////////
// Abstract Neighborhood
class MyNHoodI : public IloNHoodI {
private:
void resetCache() { _cp->needsRecomputing(); }
protected:
IloSchedulerSolution _solution;
CriticalPath *_cp;
IloArray<LSMove*> _moves;
IloInt _nbMoves;
void realAddMove(LSMove *m) {
if (_nbMoves < _moves.getSize()) _moves[_nbMoves] = m;
else _moves.add(m);
_nbMoves++;
}
public:
MyNHoodI(IloEnv env, CriticalPath *cp,
const char *name = 0 )
: IloNHoodI(env, name),
_solution(0), _cp(cp),
_moves(env), _nbMoves(0) {}
~MyNHoodI() {}
void start(IloSolver, IloSolution soln) {
_solution = IloSchedulerSolution(soln);
_nbMoves = 0;
}
IloSolution define(IloSolver solver, IloInt i) {
return (_moves[i])->createDelta(solver.getEnv(), _solution);
}
IloInt getSize(IloSolver) const { return _nbMoves; }
void notify(IloSolver, IloInt) { resetCache(); }
void notifyOther (IloSolver, IloSolution) { resetCache(); }
void reset() { _solution = 0; _nbMoves = 0; resetCache(); }
};
///////////////////////////////////////////////////////////////////////////////
//
// NEIGHBORHOOD #1: The N1 neighborhood found by swapping activities
// on the critical path
//
///////////////////////////////////////////////////////////////////////////////
class N1NHoodI : public MyNHoodI {
private:
void addMove(IloSolver solver,
IloResourceConstraint rc, IloResourceConstraint after) {
SwapRC *move = new (solver.getEnv()) SwapRC(rc, after);
MyNHoodI::realAddMove(move);
}
public:
N1NHoodI(IloEnv env, CriticalPath *cp,
const char *name = 0 ) :
MyNHoodI (env, cp, name) {}
~N1NHoodI() {}
void start(IloSolver solver, IloSolution soln);
};
void N1NHoodI::start(IloSolver solver, IloSolution soln) {
MyNHoodI::start(solver, soln);
IloInt cpSize = 0;
IloArray<IloResourceConstraint> cpArray = _cp->computeCP(_solution, cpSize);
// create the moves
for(IloInt i = 0; i < cpSize - 1; ++i) {
IloResourceConstraint rc = cpArray[i];
IloResourceConstraint after = cpArray[i + 1];
if ((_solution.getNextRC(rc).getImpl() != 0) &&
(after.getImpl() == _solution.getNextRC(rc).getImpl())) {
addMove(solver, rc, after);
}
}
}
IloNHood N1NHood(IloEnv env, CriticalPath *cp,
const char *name = 0) {
return new (env) N1NHoodI(env, cp, name);
}
///////////////////////////////////////////////////////////////////////////////
//
// NEIGHBORHOOD #2: The neighborhood found by relocating activities
// on the critical path to another possible resource
// alternative
//
///////////////////////////////////////////////////////////////////////////////
class RelocateNHoodI : public MyNHoodI {
private:
void addMove(IloSolver solver,
IloResourceConstraint relocate, IloResource to,
IloResourceConstraint beforeInsertion) {
RelocateRC *move = new (solver.getEnv())
RelocateRC(relocate, to, beforeInsertion);
MyNHoodI::realAddMove(move);
}
public:
RelocateNHoodI(IloEnv env, CriticalPath *cp,
const char *name = 0 ) :
MyNHoodI(env, cp, name) {}
~RelocateNHoodI() {}
void start(IloSolver solver, IloSolution soln);
};
void RelocateNHoodI::start(IloSolver solver, IloSolution soln) {
MyNHoodI::start(solver, soln);
IloInt cpSize = 0;
IloArray<IloResourceConstraint> cpArray = _cp->computeCP(_solution, cpSize);
// create the moves
for(IloInt i = 0; i < cpSize; ++i) {
IloResourceConstraint rc = cpArray[i];
IloResource selected = _solution.getSelected(rc);
if (rc.hasAltResSet()) {
for(IloAltResSet::Iterator iter(rc.getAltResSet());
iter.ok(); ++iter) {
IloResource res = *iter;
if (selected.getImpl() != res.getImpl()) {
// add move to insert rc first on res
addMove(solver, rc, res, 0);
IloResourceConstraint prev = _solution.getSetupRC(res);
while(prev.getImpl() != 0) {
addMove(solver, rc, res, prev);
prev = _solution.getNextRC(prev);
}
}
}
}
}
}
IloNHood RelocateNHood(IloEnv env, CriticalPath *cp,
const char *name = 0) {
return new (env) RelocateNHoodI(env, cp, name);
}
///////////////////////////////////////////////////////////////////////////////
//
// TABU LIST
//
///////////////////////////////////////////////////////////////////////////////
class MyTabuI : public IloMetaHeuristicI {
private:
IloSchedulerSolution _currentSolution;
IloInt _maxTabuSize;
IloArray<LSMove*> _tabuList;
IloInt _nbTabuEles;
IloInt _nextTabuEle;
IloNumVar _costVar;
IloNum _bestCost;
public:
MyTabuI(IloEnv env, IloNumVar costVar, const char *name = 0)
: IloMetaHeuristicI(env, name)
, _currentSolution(0)
, _maxTabuSize(10)
, _tabuList(env, _maxTabuSize)
, _nbTabuEles(0)
, _nextTabuEle(0)
, _costVar(costVar)
, _bestCost(IloInfinity)
{ }
virtual IloBool start(IloSolver, IloSolution);
virtual IloBool test(IloSolver, IloSolution);
virtual void notify(IloSolver, IloSolution);
virtual IloBool complete();
virtual void reset() {
_bestCost = IloInfinity; _nbTabuEles = 0; _nextTabuEle = 0;
}
};
IloBool MyTabuI::start(IloSolver, IloSolution solution) {
_currentSolution = IloSchedulerSolution(solution);
if (solution.isObjectiveSet()) {
IloNumVar obj = solution.getObjectiveVar();
if (obj.getImpl() && obj.getImpl() == _costVar.getImpl()) {
if (solution.getObjectiveValue() < _bestCost)
_bestCost = solution.getObjectiveValue();
}
else
throw "MyTabuI::start - Solution objective must be a simple variable.";
}
else
throw "MyTabuI::start - Solution has no objective.";
return IloTrue;
}
IloBool MyTabuI::test(IloSolver solver, IloSolution delta) {
if (solver.getMin(_costVar) < _bestCost)
return IloTrue;
for(IloInt i = 0; i < _nbTabuEles; ++i) {
if ((_tabuList[i] != 0) && _tabuList[i]->isReverseMove(delta))
return IloFalse;
}
return IloTrue;
}
void MyTabuI::notify(IloSolver solver, IloSolution delta) {
LSMove *move = 0;
RelocateRC *relocateMove =
RelocateRC::findRelocateFromDelta(solver, delta, _currentSolution);
if (0 != relocateMove)
move = relocateMove;
else {
SwapRC *swapMove = SwapRC::findSwapFromDelta(solver,
delta, _currentSolution);
if (0 != swapMove)
move = swapMove;
}
assert(move != 0);
_tabuList[_nextTabuEle] = move;
_nextTabuEle++;
_nextTabuEle %= _maxTabuSize;
if (_nbTabuEles < _maxTabuSize)
_nbTabuEles++;
}
IloBool MyTabuI::complete() {
// iterate through the tabu list (from oldest to youngest) removing
// elements up to and including the oldest element that is part of
// the neighborbood. Insert the youngest element in place of all
// elements that are removed.
IloInt youngest = _nextTabuEle - 1;
if (youngest < 0)
youngest = _nbTabuEles - 1;
if ((youngest < 0) ||
(_tabuList[youngest] == _tabuList[_nextTabuEle]))
return IloTrue;
_tabuList[_nextTabuEle] = _tabuList[youngest];
_nextTabuEle++;
_nextTabuEle %= _maxTabuSize;
return IloFalse;
}
IloMetaHeuristic MyTabu(IloEnv env, IloNumVar costVar,
const char *name = 0)
{
return (IloMetaHeuristicI *) new (env) MyTabuI(env, costVar, name);
}
////////////////////////////////////////////////////////////////////
//
// 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();
}
////////////////////////////////////////////////////////////////////
//
// SOLVE THE MODEL USING LOCAL SEARCH
//
////////////////////////////////////////////////////////////////////
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;
}
void SolveModel(IloModel model,
IloNumVar makespan,
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 */
IloSchedulerEnv schedEnv(env);
schedEnv.setPrecedenceEnforcement(IloHigh);
schedEnv.getResourceParam().ignoreCapacityConstraints();
IloSolver lsSolver(model);
IlcScheduler lsScheduler(lsSolver);
/* HILL CLIMB */
CriticalPath cp(env);
IloNHood nhood = N1NHood(env, &cp) + RelocateNHood(env, &cp);
IloGoal greedyMove = IloSingleMove(env,
lsSolution,
nhood,
IloImprove(env),
IloFirstSolution(env),
IloInstantiate(env, makespan));
IloInt maxIter = 100;
IloInt movesDone = 0;
while((movesDone < maxIter) && 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);
}
/* TABU */
IloMetaHeuristic mh = MyTabu(env, makespan);
IloGoal move = IloSingleMove(env,
lsSolution,
nhood,
mh,
IloMinimizeVar(env, makespan),
IloInstantiate(env, makespan));
for(IloInt i = movesDone; i < maxIter; ++i) {
lsSolver.out() << "Move: " << i << ":\t";
if (!lsSolver.solve(move)) {
lsSolver.out() << "no solution" << endl;
if ((nhood.getSize(lsSolver) == 0) || mh.complete())
break;
}
else {
IloNum cost = lsSolution.getSolution().getObjectiveValue();
lsSolver.out() << "solution at cost: " << cost;
if (cost < best) {
globalSolution.store(lsScheduler);
best = cost;
lsSolver.out() << " **";
}
lsSolver.out() << endl;
}
}
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,
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.setPrecedenceEnforcement(IloMediumHigh);
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;
for (i = 0; i < numberOfJobs; i++) {
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);
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;
IloRandom randGen(env, 8975324);
IloSchedulerSolution solution(env);
IloModel model = DefineModel(env,
numberOfJobs,
numberOfResources,
resourceNumbers,
durations,
randGen,
solution,
makespan);
SolveModel(model, makespan, solution);
env.end();
}
catch (IloSchedulerException& exc) {
cout << exc << endl;
}
catch (IloException& exc) {
cout << exc << endl;
}
return 0;
}
PREVIOUS
NEXT