Планирование проекта с ограниченными ресурсами, так что задачи планируются на основе наивысшего приоритета

Question

Это связано с проблемой планирования проекта с ограниченными ресурсами (RCPSP). Это включает планирование определенных задач во временных окнах на машинах в зависимости от наличия рабочей силы. Это настроено в форме Целочисленной Программы. Я использую единое дискретное представление времени.

Переменными решения являются x_it: x_it = 1, если запланировано начать действие i в отдельный момент времени t.

Каждое задание имеет приоритет, связанный с ним по внешним причинам. Чтобы проиллюстрировать цель, рассмотрим 3 задачи - p1,p2,p3 с приоритетами 3,3,4. (два уровня приоритета - 3,4) Требование следующее: если достаточно рабочей силы для планирования только p1 и p2 или p3, следует выбрать p3, даже если p1+p2 > p3. Я ищу способ реализовать эту логику, используя переменные решения x_it.

Я попытался реализовать свое требование следующим образом: назначить новый приоритет (P) для каждой задачи: P1 = 3, P2 = 3, P3 = 7; По сути, это включает в себя масштабирование каждого уровня приоритета так, чтобы ни одна комбинация задач с более низким приоритетом не могла быть выше этого уровня приоритета, и установка целевой функции на "максимизировать P_i*x_it"

Проблема этого подхода заключается в том, что при масштабировании большого набора задач (~300 задач) и нескольких уровней приоритета (20 уровней) новые значения приоритетов быстро становятся огромными числами (~10^17).

Есть ли более надежный способ реализовать это требование в рамках парадигмы целочисленного программирования?

Answer 1

Одним из способов будет:

1. Решите для работы с наивысшим приоритетом (скажем, приоритет 1). Пусть количество рабочих мест будет равно n1.
2. Добавить ограничение: scheduled number of jobs with priority 1 = n1
3. Решите для заданий с приоритетами 1 и 2. Пусть количество запланированных заданий с приоритетом 2 будет n2.
4. Добавить ограничение: scheduled number of jobs with priority 2 = n2так далее