Suppose there are two types of products: A and B. The type "A" must be scheduled, but type "B" can be optionally scheduled. The goal is to schedule as much as jobs with minimum completion time. Now, the type "A" jobs cannot be overlapped, but type "B" jobs can be overlapped among the same type "B".
In the following illustration, job 9 was not scheduled, but the job could be scheduled by overlapping with job 10 (note both jobs 9 and 10 are type "B").
Assume there is no way to pre-batch jobs during a pre-processing. I have tried "SPAN" method to contain multiple overlapping jobs and assigned those representing jobs to machine while still utilizing NoOverlap. This approach worked well, but when a size of problem gets bigger, the approach got slower. Is there better way to capture two different types of jobs (one allowing overlap and the other not allowing overlap) in a same sequence?
using CP;
tuple t_job {
key int id;
string ptype;
int sz; //size
int est; //early start time
int let; //latest end time
};
{t_job} Jobs = {
<1, "A", 20, 0, 200>,
<2, "A", 10, 0, 200>,
<3, "A", 30, 30, 200>,
<4, "A", 20, 40, 100>,
<5, "A", 10, 0, 50>,
<6, "B", 20, 10, 100>,
<7, "B", 20, 0, 100>,
<8, "B", 10, 10, 100>,
<9, "B", 20, 50, 100>,
<10, "B", 20, 50, 100>
};
dvar interval itv[j in Jobs] optional (j.ptype=="B") in j.est..j.let size j.sz;
dvar sequence seqMch in all(j in Jobs) itv[j];
dexpr int cmax =max(j in Jobs) endOf(itv[j]);
dexpr int cntJob=sum(j in Jobs) presenceOf(itv[j]);
maximize staticLex(cntJob,-cmax);
subject to {
noOverlap(seqMch);
}
I made it work with the following codes by utilizing duplicated sequence. However, this method is still not fast for a large-scale problem. Is there better way?
range copies = 0..1;
dvar interval itv[j in Jobs][copies] optional in j.est..j.let size j.sz;
dvar sequence seqMch[c in copies] in all(j in Jobs) itv[j][c];
dexpr int cmax =max(j in Jobs,c in copies) endOf(itv[j][c]);
dexpr int cntJob=sum(j in Jobs,c in copies) presenceOf(itv[j][c]);
maximize staticLex(cntJob,-cmax);
subject to {
forall(c in copies)
noOverlap(seqMch[c]);
forall (j in Jobs:j.ptype=="B")
sum(c in copies) presenceOf(itv[j][c]) <= 1;
}
#DecisionOptimization