Ограничения моделирования в решателе Choco

Я играю с chocosolver, чтобы решить некоторые проблемы планирования задач.

У меня есть несколько заданий и возможных слотов (где задание может быть выполнено). Есть некоторые ограничения, такие как:

  • В каждом слоте может быть только одно задание (C.1)
  • Для задания требуется определенное время t, а слот имеет доступную продолжительность d. Работа должна соответствовать доступной продолжительности: t<=d (C.2)

Итак, в основном выражено некоторыми базовыми/псевдоклассами:

class Job {
    int id;
    int time;
}

class Slot {
    int id;
    int duration;
}

В настоящее время я могу выделить слот для каждого задания, предполагая, что идентификатор задания и слот последовательно пронумерованы

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);

Это работает, как и ожидалось. Но теперь я хочу смоделировать и другие ограничения. Но я зацикливаюсь на том, как совместить задание/слот со временем/длительностью, потому что время и продолжительность являются зависимой переменной.

На первом этапе я смоделировал две дополнительные переменные для времени и длительности:

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);

Теперь мне нужно выразить ограничение, согласно которому время должно соответствовать длительности (C.2).

Можно ли определить подобное ограничение (не работающий/действительный псевдокод):

for(int i=0;i<jobCount;i++){
    times[i].le(durations[jobs[i]]).post();
}

или модель совсем не та?!

Может у кого есть решение или идея?!


java constraint-programming choco
person Indivon    schedule 22.08.2018    source источник

Ответы (1)


arrow_upward
1
arrow_downward

Если вы говорите, что в каждом слоте может быть только одно задание, то естественно выбрать slot в качестве IntVarArray, а именно:

 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

Здесь slots указывает на элементы в jobTime. Если у вас больше слотов, чем рабочих мест, позаботьтесь об ограничении allDifferent: у вас не будет решений. В этом случае используйте модифицированное ограничение, такое как allDifferentExcept0, чтобы решатель мог выбрать допустимый элемент. Тогда jobTimes[0] должна быть записью, удовлетворяющей всем слотам (скажем, 0).

Тогда вы очень близки. Все, что вам нужно сделать, это ввести промежуточную IntVarпеременную, скажем, shadowTime, которая представляет время в порядке, заданном slots, например так:

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
}

Затем вы можете добавить ограничение C.2 в тот же цикл:

//within in the above loop:
{    
    ...
    model.arithm(shadowTime[i], "<", slotDurations[i]).post();
}

Затем вы можете перечислить все решения, как описано в руководстве (while (solver.solver(){...}).

person Philip Harding    schedule 23.08.2018
comment
model.element помог мне! Там могут быть сотни слотов, но только несколько заданий, поэтому я более или менее просто добавил это shadow и ограничение, подобное вашей второй части. Спасибо! - person Indivon; 23.08.2018