I'm playing around with choco solver to solve some task scheduling problems.
I have several jobs and possible slots (where a job can be executed). There are some constraints like:
t
and slot has an available duration d
.
The job must fit into the that available duration: t<=d
(C.2)So, basically expressed with some basic/pseudo classes:
class Job {
int id;
int time;
}
class Slot {
int id;
int duration;
}
Currently, I'm able to allocate a slot for each job, assuming that id of a job and a slot are consecutively numbered
int jobCount = 5; // 5 jobs with ids from 0 to 4
int slotCount= 20; // 20 jobs with ids from 0 to 19
Model model = new Model("Example");
IntVar[] jobs = model.intVarArray("Job", jobCount, 0, slotCount, false);
// all jobs must have different slots (C.1)
model.allDifferent(jobs).post();
// solving - details omitted, because I think it is not relevant...
Solution solution = model.getSolver().findSolution();
// assign the jobs to the slots like (pseudo-code):
// foreach i in jobs.length do
// job = getJobForId(i);
// getSlotForId(jobs[i]).setJob(job);
This is working as expected. But now I want to model the other constraints as well. But I'm stucking on how to combine the job/slot with the times/durations, because the time and duration is a dependent variable.
At a first step, I modeled two additional variables for times and durations:
int[] slotDurations = {10, 20, 10, 40, ..., 20} // 20 durations (d)
IntVar[] durations = model.intVarArray("Time", slotCount, slotDurations);
int[] jobTimes = {5, 16, 30, 2, 17} // 5 times (t)
IntVar[] times = model.intVarArray("Time", jobCount , jobTimes);
Now, I need to express the constraint that the time should fit into the duration (C.2).
Is it possible to define a constraint like this (not working/valid pseudo-code):
for(int i=0;i<jobCount;i++){
times[i].le(durations[jobs[i]]).post();
}
or is the model totally wrong?!
Maybe someone has a solution or an idea?!
If you say that there can be only one job per slot, then it is natural to select slot
as your IntVarArray
, as so:
IntVar[] slots = model.intVarArray("Slot", slotCount, 0, jobCount, false);
int[] jobTimes = {0, 5, 16, 30, 2, 17}; //6(!) items; see explanation below.
int[] slotDurations = {10, 20, 10, 40, ..., 20}; //20 items
Here, slots
points to the items in jobTime
. If you have more slots than jobs, then take care with the allDifferent
constraint: You will end up having no solutions. In that case, use a modified constraint, such as allDifferentExcept0
so that the solver can select a valid item. Then, jobTimes[0]
must be an entry satisfying all slots (say, 0).
Then you are very close. All you need to do is to introduce an intermediate IntVar
variable, say shadowTime
, which represents the times in the order given by slots
, like so:
IntVar[] shadowTime = model.intVarArray("shadowTime", slotDurations.length, 0, jobTimes.length, false); //has the jobTimes in the order indicated by slots.
for(int i=0;i<slotCount;i++){
model.element(shadowTime[i], jobTimes, slots[i]).post();
//this is similar to what you wanted to achieve with 'durations[jobs[i]]' in your code
}
Then you can add the constraint C.2 in the same loop:
//within in the above loop:
{
...
model.arithm(shadowTime[i], "<", slotDurations[i]).post();
}
You can then enumerate all solutions as described in the manual (while (solver.solver(){...}
).