You can see the entire program jobshopshuff.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};
IloInt 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};
IloInt 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};
IloInt 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};
///////////////////////////////////////////////////////////////////////////////
//
// PROBLEM DEFINITION
//
///////////////////////////////////////////////////////////////////////////////
IloModel
DefineModel(IloEnv& env,
IloInt numberOfJobs,
IloInt numberOfResources,
IloInt* resourceNumbers,
IloInt* durations,
IloNumVar& makespan,
IloSchedulerSolution& solution)
{
IloModel model(env);
/* CREATE THE MAKESPAN VARIABLE. */
IloInt numberOfActivities = numberOfJobs * numberOfResources;
IloInt horizon = 0;
IloInt k;
for (k = 0; k < numberOfActivities; k++)
horizon += durations[k];
makespan = IloNumVar(env, 0, horizon, ILOINT);
solution = IloSchedulerSolution(env);
/* CREATE THE RESOURCES. */
IloSchedulerEnv schedEnv(env);
schedEnv.getResourceParam().setCapacityEnforcement(IloMediumHigh);
schedEnv.getResourceParam().setPrecedenceEnforcement(IloMediumHigh);
IloTextureParam tParam = schedEnv.getTextureParam();
IloRCTextureFactory rcFactory = IloRCTextureProbabilisticFactory(env);
tParam.setRCTextureFactory(rcFactory);
IloTextureCriticalityCalculator critCalc =
IloProbabilisticCriticalityCalculator(env);
tParam.setCriticalityCalculator(critCalc);
IloRandom randGen(env, 98020981);
tParam.setRandomGenerator(randGen);
tParam.setHeuristicBeta(0.75);
IloInt j;
IloUnaryResource *resources =
new (env) IloUnaryResource[numberOfResources];
for (j = 0; j < numberOfResources; j++)
resources[j] = IloUnaryResource(env);
/* CREATE THE ACTIVITIES. */
char buffer[128];
k = 0;
IloInt i;
for (i = 0; i < numberOfJobs; i++) {
IloActivity previousActivity;
for (j = 0; j < numberOfResources; j++) {
IloActivity activity(env, durations[k]);
sprintf(buffer, "J%ldS%ldR%ld", i, j, resourceNumbers[k]);
activity.setName(buffer);
model.add(activity.requires(resources[resourceNumbers[k]]));
if (j != 0)
model.add(activity.startsAfterEnd(previousActivity));
solution.add(activity, IloRestoreNothing);
previousActivity = activity;
k++;
}
model.add(previousActivity.endsBefore(makespan));
}
/* RETURN THE MODEL. */
return model;
}
///////////////////////////////////////////////////////////////////////////////
//
// PRINT SOLUTION
//
///////////////////////////////////////////////////////////////////////////////
void PrintSolution(IloSchedulerSolution sol){
IloEnv env = sol.getEnv();
for(IloSchedulerSolution::ActivityIterator ite(sol); ite.ok(); ++ite){
IloActivity act = *ite;
env.out() << act.getName() << "[";
IloNum startMin = sol.getStartMin(act);
IloNum startMax = sol.getStartMax(act);
env.out() << startMin;
if (startMin != startMax)
env.out() << ".." << startMax;
env.out() << " -- ";
IloNum pMin = sol.getProcessingTimeMin(act);
IloNum pMax = sol.getProcessingTimeMax(act);
env.out() << pMin;
if (pMin != pMax)
env.out() << ".." << pMax;
env.out() << " --> ";
IloNum endMin = sol.getEndMin(act);
IloNum endMax = sol.getEndMax(act);
env.out() << endMin;
if (endMin != endMax)
env.out() << ".." << endMax;
env.out() << "]" << endl;
}
}
///////////////////////////////////////////////////////////////////////////////
//
// 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;
IloNum _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; }
IloNum getStartValue() { return _startValue; }
IloInt getTieBreaker() { return _tieBreaker; }
void setRC(IloResourceConstraint rc) { _rc = rc; }
void setStartValue(IloNum 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:
IloInt _cpSize;
IloArray<IloResourceConstraint> _cpArray;
IloRandom _randGen;
RCSortElement *getCriticalRCs(IloSchedulerSolution, IloInt&);
void pickRandomCP(RCSortElement *, IloSchedulerSolution,IloInt);
void addCPElement(IloResourceConstraint);
public:
CriticalPath(IloEnv env) :
_cpSize(0), _cpArray(env), _randGen(env, 98998) {}
~CriticalPath() {}
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(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;
IloNum 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 = solution.getEndMin(next.getActivity());
}
else
i = nbCriticalRCs;
}
}
IloArray<IloResourceConstraint>& CriticalPath::computeCP(
IloSchedulerSolution solution,
IloInt& cpSize) {
IloInt nbCriticalRCs = 0;
RCSortElement *sortArray = getCriticalRCs(solution, nbCriticalRCs);
// Pick the RCs in one (randomly selected) critical path
pickRandomCP(sortArray, solution, nbCriticalRCs);
delete [] sortArray;
cpSize = _cpSize;
return _cpArray;
}
///////////////////////////////////////////////////////////////////////////////
//
// SHUFFLE NEIGHBORHOOD
//
///////////////////////////////////////////////////////////////////////////////
class ShuffleNHoodI : public IloNHoodI {
private:
IloNumVar _costVar;
IloNum _prob;
CriticalPath _cp;
IloSchedulerSolution _delta;
IloRandom _randGen;
public:
ShuffleNHoodI(IloEnv env, IloNumVar cost,
IloNum probability, const char *name = 0)
: IloNHoodI (env, name),
_costVar(cost), _prob(probability),
_cp(env), _delta(0), _randGen(env, 98998) {}
~ShuffleNHoodI() {}
void start (IloSolver solver, IloSolution soln);
IloSolution define (IloSolver solver, IloInt) {
assert(_delta.getImpl() != 0);
assert(_delta.getSolution().getImpl() != 0);
return _delta.getSolution().makeClone(solver.getEnv());
}
IloInt getSize (IloSolver) const { return 1; }
};
void ShuffleNHoodI::start(IloSolver solver, IloSolution soln) {
IloSchedulerSolution solution(soln);
IloEnv env = solver.getEnv();
IloInt cpSize = 0;
IloArray<IloResourceConstraint> cpArray = _cp.computeCP(solution, cpSize);
// Create the move
if (_delta.getImpl() != 0)
_delta.end();
_delta = solution.makeClone(env);
// For each edge in the critical path (between resource constraints
// on the same resource) keep it in the solution with probability
// (1 - _prob)
for(IloInt i = 0; i < cpSize - 1; ++i) {
IloResourceConstraint before = cpArray[i];
IloResourceConstraint after = cpArray[i + 1];
if (solution.hasNextRC(before) &&
(after.getImpl() == solution.getNextRC(before).getImpl()) &&
(_randGen.getFloat() > _prob)) {
// Remove resource constraint from delta. This has the effect of
// ensuring that this edge will be in the next solution
_delta.remove(before);
}
}
// For everything remaining in the solution, get rid of the nexts.
// This has the effect of leaving the next of each rc undefined and
// so this defines the search space for the rescheduling goal.
for(IloSchedulerSolution::ResourceConstraintIterator iter3(_delta);
iter3.ok(); ++iter3) {
IloResourceConstraint rc = *iter3;
if (_delta.hasNextRC(rc))
_delta.unsetNext(rc, _delta.getNextRC(rc));
}
// Reset the lower bound of the costVar
_delta.setMin(_costVar, 0);
}
IloNHood ShuffleNHood(IloEnv env, IloNumVar cost,
IloNum prob, const char *name = 0) {
return new (env) ShuffleNHoodI(env, cost, prob, name);
}
///////////////////////////////////////////////////////////////////////////////
//
// PROBLEM SOLVING
//
///////////////////////////////////////////////////////////////////////////////
void FindInitialSolution(IloModel model,
IloSchedulerSolution globalSolution,
IloSchedulerSolution lsSolution,
IloNumVar costVar) {
IloEnv env = model.getEnv();
IloSolver solver(model);
IlcScheduler scheduler(solver);
IloGoal g = IloRankForward(env) && IloInstantiate(env, costVar);
solver.startNewSearch(g);
if(solver.next()) {
IlcInt best = (IlcInt)solver.getValue(costVar);
solver.out() << "Solution for Cost " << best << endl;
solver.printInformation();
globalSolution.store(scheduler);
lsSolution.store(scheduler);
}
solver.endSearch();
solver.end();
}
void
SolveModel(IloModel model,
IloNumVar makespan,
IloSchedulerSolution& globalSolution)
{
IloEnv env = model.getEnv();
IloObjective obj = IloMinimize(env, makespan);
globalSolution.getSolution().add(makespan);
/* CREATE LOCAL SEARCH SOLUTION */
IloSchedulerSolution lsSolution = globalSolution.makeClone(env);
for (IloIterator <IloResourceConstraint> iter(env); iter.ok(); ++iter)
lsSolution.add(*iter, IloRestoreRCNext);
lsSolution.getSolution().add(obj);
/* GENERATE AN INITIAL SOLUTION. */
FindInitialSolution(model, globalSolution, lsSolution, makespan);
IloNum best = globalSolution.getMax(makespan);
env.out() << "Initial solution:" << endl;
PrintSolution(globalSolution);
/* LOCAL SEARCH */
IloSolver lsSolver(model);
IlcScheduler lsScheduler(lsSolver);
IloNHood nhood = ShuffleNHood(env, makespan, 0.2);
IloGoal reschedGoal = IloLimitSearch(env,
IloTextureSuccessorGoal(env) &&
IloInstantiate(env, makespan),
IloFailLimit(env, 100));
IloGoal move = IloSingleMove(env,
lsSolution,
nhood,
reschedGoal);
IloInt maxIter = 100;
for(IloInt i = 0; i < maxIter; ++i) {
lsSolver.out() << "Move: " << i << ":\t";
if (!lsSolver.solve(move))
lsSolver.out() << "no solution" << endl;
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(globalSolution);
lsSolver.end();
}
///////////////////////////////////////////////////////////////////////////////
//
// MAIN FUNCTION
//
///////////////////////////////////////////////////////////////////////////////
void
InitParameters(int argc,
char** argv,
IloInt& numberOfJobs,
IloInt& numberOfResources,
IloInt*& resourceNumbers,
IloInt*& durations)
{
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;
}
}
}
int main(int argc, char** argv)
{
try {
IloEnv env;
IloInt numberOfJobs = 6;
IloInt numberOfResources = 6;
IloInt* resourceNumbers = ResourceNumbers06;
IloInt* durations = Durations06;
InitParameters(argc,
argv,
numberOfJobs,
numberOfResources,
resourceNumbers,
durations);
IloNumVar makespan;
IloSchedulerSolution solution;
IloModel model = DefineModel(env,
numberOfJobs,
numberOfResources,
resourceNumbers,
durations,
makespan,
solution);
SolveModel(model,
makespan,
solution);
env.end();
}
catch (IloException& exc) {
cout << exc << endl;
}
return 0;
}
PREVIOUS
NEXT