Билет № 14 Модель dcpm и задача dtctp ( решение методом динамического программирования)

Дискретный случай DTCTP

• Работы имеют конечное число режимов выполнения (modes).

• Задачи DTCTP могут быть сформулированы как задачи целочисленного линейного программирования (ЦЛП), которые могут быть решены методом ветвей и границ.

• Точное решение проблемы занимает время, сравнимое с полным перебором всех возможных вариантов.

• Для нахождения приемлемых решений следует применять эвристические методы, например, модель DCPM.

Decision CPM

Это метод критического пути, при котором используется мультиработа или работа-решение.

Существует 2 варианта, первый, когда из кружочка выходит две работы и мы выполняем И ту И другую

И второй вариант, когда мы должны выбрать только одну работу ИЛИ ту ИЛИ другую

Модель разработана Crowston (MIT), Thompson (1967-1970).

Постановка задачи для DCPM

• 𝑚𝑖𝑘 - режимы выполнения работы i, j=1,…,𝑘𝑖

• Целевая функция – полные затраты проекта со штрафами/премиями

• В ограничениях:

• Альтернатива: для любой i верно: сумма 𝑚𝑖𝑘𝑘=1

• Импликация: 𝑚𝑖𝑘≤𝑚𝑗𝑙

• Эквивалентность: 𝑚𝑖𝑘=𝑚𝑗𝑙

• Предшествование _𝑖→𝑗:

• 𝑠𝑖+𝑑𝑖≤𝑠𝑗, если i – обычная работа

• −𝑀∙1−𝑚𝑖𝑘+𝑠𝑖𝑘+𝑑𝑖𝑘≤𝑠𝑗, если i-мультиработа

Сначала необходимо найти критический путь.

Динамическое программирование для поиска критического пути

Ищем самый длинный путь, который ведет к 5 вершине, это будет критический путь.

В данном случае это путь 0-2-3-5.

В процессе подсчетов берем макс. длину путей из двух возможных. Делаем слева направо.

Fi(k) – слой(вершина)

F(0)=0

-F(v)- max p:p=v{f(p)+dpv}

Решение методом динамического программирования ( Hindelang, Muth)

𝑌𝑖 - стоимость на i-м этапе (обратная прогонка) Начинаем с последней работы, так как есть мультиработы

𝑌𝑛= - 𝐶штраф/премия∙(𝛿𝑛 (навязанный финиш) −𝑠𝑛)

𝑌𝑖= сумма (𝐶𝑘+𝑌𝑘)∙𝑚𝑖𝑘 + сумма(C𝑗+𝑌𝑗) каждое предыдущее от большего номера к меньшему

A(i)– альтернативы мультиработы i

S(i)– прямые последователи работы I

𝐶𝑗 -оптимальные затраты работы j

ЦФ:𝑌1→ min в итоге дойдем до 1ого события и получим всю стоимость пути

Когда мы идем в обратную сторону на мультиработах выбираем минимум.

Алгоритм

• AND (обычная работа)

  • 𝐾𝐼(𝑡)= сумма (𝐾𝑋(𝑡+𝑡𝐼))+𝐶(𝐼) затраты

  • 𝐿𝐼(𝑡)=max𝑋𝜖𝑆(𝐼){𝐿𝑋(𝑡+𝑡𝐼)} продолжительность

• OR (мультиработа)

  • 𝐾𝐼(𝑡)=min𝑋∈𝐴(𝐼){𝐶𝑋+𝐾𝑋(𝑡+𝑡𝐼)}

  • 𝐿𝐼(𝑡)=𝑡𝐼+𝐿(𝑡+𝑡𝐼)

• K– затраты, L-продолжительность

Стандартная задача k,l, когда нам заданы штрафы за просрочку.

Недостатки

Было доказано, что этот метод не приводит к оптимальному решению.

Расширенные задачи DTCTP

DTCTP-tsc (time-switch constraints)

Календари 8 часов/сутки; 24; без выходных

• Yang & Chen (2000), Vanhoucke

DTCTP-wc (work continuity constraints)

Ограничение трудовых ресурсов на продолжительность работ

• El-Rayes, Moselhi (1998)

Задача максимизации NPV

• Herroelen, Demeulemeester, Van Dommelen (1997)

• Затраты насчитываются на конец

Это же метод критической цепи= все работы выполняются как можно позже (часть работ должна выполняться позже- количество звеньев в критической цепи увеличится).