Как сформулировать планирование ресурсов с дискретным временем в проблему?

Question

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

Моя проблема аналогична проблеме планирования ресурсов машины. У меня есть набор двоичных переменных для представления парных комбинаций машин с сеткой дискретного времени. Задание A занимает 1 час, задание B - 1 час и 15 минут, поэтому временная сетка должна составлять 15 минут. Поэтому задание A будет использовать 4 единицы времени, а задание B будет использовать 5 единиц времени.

Мне трудно понять, как express ограничить такое, чтобы при назначении задания машине Единицы, которые он занимает, являются последовательными во временной переменной. Есть ли пример того, как смоделировать это ограничение? Я использую PuLP, если это поможет.

Спасибо!

Answer 1

Вы хотите реализовать ограничение:

x(t-1) = 0 and x(t) = 1 ==> x(t)+...+x(t+n-1) = n

Один из способов:

x(t)+...+x(t+n-1) >= n*(x(t)-x(t-1))

Примечания:

1. необходимо повторить это ограничение для каждого t.

2. Несколько лучшая версия:

   x(t+1)+...+x(t+n-1) >= (n-1)*(x(t)-x(t-1))
   

3. Существует также дезагрегированная версия этого ограничения это может повысить производительность (в зависимости от решателя: некоторые решатели могут выполнить это разделение автоматически).

4. В начале и в конце периода планирования все может стать интересным. Например, машина запущена в t=-1.

Обновление:

Другой подход - просто ограничить «начало» задания до 1. Т.е. разрешить только комбинацию

 x(j,t-1) = 0 and x(j,t) = 1

для данной работы j. Это можно сделать аналогичным образом:

 start(j,t) >= x(j,t)-x(j,t-1)
 sum(t, start(j,t)) <= 1
 0 <= start(j,t) <= 1