Hi,
we are trying to implement edge-finder propagator. The algorithm is
implemented according to the book Baptiste,Le Pape, Nuijten (2001)
Constraint-Based Scheduling.
We also took some Gecode coding inspiration from the cumulatives
propagator.
The problem we have, is that for FT6 job-shop benchmark (we did not try
more benchmarks yet), the edge-finder combined with BAB branching founds
a solution that has Cmax>OptimalCmax, but is marked as an optimum, since
BAB founds no better solution.
However, when a constraint Cmax < 57 is added (optimum for FT6 is 55),
see line 96 of jobshop.cpp, then a solution with correct Cmax is found.
We do not know if the bug is in the edge-finder algoritm (not much
likely), in the Gecode stuff of the propagator code, or in the Gecode
itself.
Maybe someone who already implemented some edge-finder variation could
help us.
The code of the whole program is attached (about 300 lines of code). The
problem object Jobshop is inherited from the object Example, ie. it is
necessary to include "examples/support.hh" and to link it with
"example.o" and "options.o" from examples/support directory of the
Gecode distribution.
We use Gecode 2.1.1 binary distribution, Visual C++ 2008 and Windows XP.
There are some TODOs we know about, but we think that are not the source
of the problem:
* some methods of the propagator should be inlined
* vector used for sorting tasks should not be created each time
propagate() method is called - instead it should be created in
propagator constructor
* improve input function to be able to compute jobshops with different
number of jobs and tasks (n != m)
I also obtained the same memory allocation problem, that was already
reported by Nick Hindle on July 21st
http://www.gecode.org/gecode-users/2008-July/002344.html
The problematic code is in file jobshop.cpp line 115:
os << S[i] << ", "; //raises memory allocation exception
os << S[i].val() << ", "; //this works
Thanks, Jan
#include "edgeFinder.h"
#include "examples/support.hh"
#include "gecode/minimodel.hh"
#include <cstdio>
// random jobshop 4x4
const int processingTime04[] = {
2, 3, 5, 1,
7, 2, 3, 4,
3, 8, 2, 6,
1, 2, 8, 5
};
int resource04[] = {
1, 3, 2, 4,
2, 4, 3, 1,
4, 2, 1, 3,
1, 2, 4, 3
};
// jobshop FT6
const int processingTime06[] = {
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
};
int resource06[] = {
3, 1, 2, 4, 6, 5,
2, 3, 5, 6, 1, 4,
3, 4, 6, 1, 2, 5,
2, 1, 3, 4, 5, 6,
3, 2, 5, 6, 1, 4,
2, 4, 6, 1, 5, 3
};
class Jobshop : public Example
{
protected:
IntVarArray S; // starting time variables
const int n; // size (jobshop n x n)
public:
// The actual problem
Jobshop(const SizeOptions& opt)
: n(opt.size()), S(this,opt.size()*opt.size()+1,0,100)
{
const int* processingTime = processingTime04;
int* resource = resource04;
switch(opt.size())
{
case 4:
resource = resource04;
processingTime = processingTime04;
break;
case 6:
resource = resource06;
processingTime = processingTime06;
break;
}
// count resources from 0
for (int i = 0; i < n*n; ++i)
resource[i]--;
// precedence constraints
for (int i = 0; i<n; ++i){
for (int j = 0; j < n-1; ++j){
post(this,S[i*n+j] + processingTime[i*n+j] <= S[i*n+j+1]);
}
}
// every job ends before makespan
for (int i = 0; i<n; ++i){
post(this,S[i*n+n-1] + processingTime[i*n+n-1] <= S[n*n]);
}
// disjunctive resource constraints
for (int k = 0; k < n*n; ++k) {
for (int l = k+1; l <n*n; ++l){
if(resource[k] == resource[l]) {
post(this,tt(~(S[k] + processingTime[k] <= S[l])||~(S[l] +
processingTime[l] <= S[k])));
}
}
}
EdgeFinder::post(this,S,resource,processingTime,n);
// ATTENTION: when uncommented, a solution with correct optimal Cmax=55 for
FT06 is found
//post(this,S[n*n] < 57);
branch(this, S, INT_VAR_SIZE_MIN, INT_VAL_MIN);
};
// Constructor for cloning \a s
Jobshop(bool share, Jobshop& s) : Example(share,s), n(s.n) {
S.update(this, share, s.S);
}
// Perform copying during cloning
virtual Space*
copy(bool share) {
return new Jobshop(share,*this);
}
// Print solution
virtual void print(std::ostream& os) {
for (int i = 0; i < S.size(); i++) {
//os << S[i] << ", "; //raises memory allocation exception
os << S[i].val() << ", "; //this works
if ((i+1) % n == 0){
os << std::endl;
}
}
os << std::endl;
}
// add requirement for better next result - for BAB
void constrain(Space * s){
rel(this, S[n*n], IRT_LE, static_cast<Jobshop*>(s)->S[n*n].min());
}
};
int main(int argc, char* argv[])
{
SizeOptions opt("Jobshop");
opt.solutions(0);
opt.size(6);
opt.parse(argc,argv);
opt.icl(ICL_BND);
Example::run<Jobshop,BAB,SizeOptions>(opt);
return 0;
};
#include "edgeFinder.h"
EdgeFinder::EdgeFinder(Space* home, ViewArray<Gecode::Int::IntView>& _start,
const IntArgs& _processing_time)
: processingTime(_processing_time.size()), NaryPropagator
<Gecode::Int::IntView, Gecode::Int::PC_INT_BND> (home,_start)
{
n = x.size();
for(int i = _processing_time.size(); i--; )
processingTime[i] = _processing_time[i];
};
EdgeFinder::EdgeFinder(Space* home, bool share, EdgeFinder& p)
: processingTime(p.processingTime.size()), n(p.n), NaryPropagator
<Gecode::Int::IntView, Gecode::Int::PC_INT_BND> (home, share, p)
{
processingTime.update(home, share, p.processingTime);
};
size_t EdgeFinder::dispose(Space* home)
{
processingTime.~SharedArray();
return NaryPropagator::dispose(home);
};
PropCost EdgeFinder::cost() { return Gecode::PC_QUADRATIC_LO ; };
ExecStatus EdgeFinder::propagate(Space * home, ModEventDelta med)
{
bool subsumed = true;
for (int i = n; i--; ) {
if (!x[i].assigned()) {
subsumed = false;
break;
}
};
// subsume propagator if all tasks have assigned starting time (x)
if (subsumed) return ES_SUBSUMED(this,home);
// Algorithm 1: Edge-Finding according the book [Baptiste,P., Le Pape, C. and
Nuijten, W. : Constraint-Based Scheduling. Applying..., 2001]
bool modified = false;
std::vector<TaskInfo> tasks;
for(int i=0; i < n; i++){
tasks.push_back(TaskInfo(x[i], processingTime[i]));
}
std::sort(tasks.begin(), tasks.end(),nondecreasingEstSort);
for (int k=0; k < n ; k++){
int P = 0;
int C = std::numeric_limits<int>::min();
int H = C;
for (int i = n; i--; ){
if((tasks[i].start.max()+tasks[i].processingTime) <=
(tasks[k].start.max()+tasks[k].processingTime) ){ //line 7
P += tasks[i].processingTime;
C = std::max(C, tasks[i].start.min() + P);
if (C > (tasks[k].start.max()+tasks[k].processingTime)) //line 10
return ES_FAILED;
}
tasks[i].Ci=C; //line 14
}
for (int i=0; i < n; i++){
if ((tasks[i].start.max()+tasks[i].processingTime) <=
(tasks[k].start.max()+tasks[k].processingTime)){ //line 17
H = std::max(H, tasks[i].start.min()+P);
P -= tasks[i].processingTime;
}
else{
if((( tasks[i].start.min() + P + tasks[i].processingTime )) >
tasks[k].start.max() ){ //line 21
tasks[i].releaseTime = std::max( tasks[i].releaseTime, tasks[i].Ci);
modified = true;
}
if ((H + tasks[i].processingTime) > (tasks[k].start.max() +
tasks[k].processingTime)){ //line 24
tasks[i].releaseTime = std::max(tasks[i].releaseTime,C);
modified = true;
}
}
}
}
if (!modified)
return ES_FIX;
for (int i=0; i < n; i++){
if (me_failed(tasks[i].start.gq(home, tasks[i].releaseTime))) //line 31
return ES_FAILED;
}
return ES_NOFIX;
};
Actor* EdgeFinder::copy(Space * home, bool share)
{
return new (home) EdgeFinder(home, share, *this);
}
ExecStatus EdgeFinder::post(Space* home, const IntVarArgs& _starts, const int*
_machine, const int* _processing_time, int size)
{
ViewArray<Int::IntView> starts(home,_starts);
for (int i=0; i < size ; i++){ // for each machine
ViewArray<Int::IntView> start(home, size);
IntArgs processingTime(size);
int j = 0;
int count =0;
while (count < size){
if(_machine[j]==i){ // task j is processed by machine i
processingTime[count] = _processing_time[j];
start[count]=starts[j];//copy view
count++;
}
j++;
}
new (home) EdgeFinder(home,start,processingTime);
}
return ES_OK;
};
#ifndef __EDGEFINDER_H__
#define __EDGEFINDER_H__
#include "gecode/int.hh"
#include <vector>
#include <limits>
#include <algorithm>
using namespace Gecode;
class TaskInfo
{
public:
Int::IntView start;
int processingTime;
int releaseTime;
int Ci;
TaskInfo(Int::IntView _start, int _proctime) : start(_start),
processingTime(_proctime), releaseTime(_start.min()), Ci(0) {};
};
inline bool nondecreasingEstSort(const TaskInfo& t1, const TaskInfo& t2)
{
return ( t1.start.min() < t2.start.min() );
};
class EdgeFinder: NaryPropagator<Gecode::Int::IntView, Gecode::Int::PC_INT_BND>
//Gecode::PC_GEN_ASSIGNED Gecode::Int::PC_INT_BND
{
protected:
// Number of tasks
int n;
// List of processingTimes
SharedArray<int> processingTime;
// Constructor for propagator creation
EdgeFinder(Space * home, ViewArray<Gecode::Int::IntView> &_start, const
IntArgs& _processing_time);
// Constructor for cloning \a p
EdgeFinder(Space * home, bool share, EdgeFinder& p);
public:
virtual PropCost cost();
virtual size_t dispose(Space* home);
virtual ExecStatus propagate(Space * home, ModEventDelta med);
virtual Actor* copy(Space * home, bool share);
static ExecStatus post(Space* home, const IntVarArgs& _starts, const int*
_machine, const int* _processing_time, int size);
};
#endif // __EDGEFINDER_H_________________________________________________
Gecode users mailing list
[EMAIL PROTECTED]
https://www.gecode.org/mailman/listinfo/gecode-users
