Hardprob/Minimum Resource Constrained Scheduling — различия между версиями
Материал из DISCOPAL
StasFomin (обсуждение | вклад) (Новая страница: «<!-- start --><!-- {{svg-image-for-hard-problem|{{PAGENAME}}}} --> * Набор задач <em>T</em> с длинами <em>l(t)</em>, <em>m</em> процессо…») |
StasFomin (обсуждение | вклад) |
||
| Строка 8: | Строка 8: | ||
</m> | </m> | ||
* Минимизировать общую длительность расписания, т.е. | * Минимизировать общую длительность расписания, т.е. | ||
| − | <m>\max_{t \in T}(f(t)+l(t))</m> | + | <m>\max_{t \in T}(f(t)+l(t)) → \min</m> |
---- | ---- | ||
Версия 07:47, 12 апреля 2023
- Набор задач T с длинами l(t), m процессоров, число ресурсов , ресурсные потребности задач и ресурсные ограничения .
- Найти m-процессорное расписание для T, соблюдающую отношения предшествования, т.е. функцию , такую что
- , если S(u) будет набор задач t для которых , то и
- Минимизировать общую длительность расписания, т.е.
Задача в лаб17 (рид-онли просмотр)
- Задача в базе NP-полных задач Вигго Кана
- Код задачи в книге «ГД» → «SS10»