Hardprob/Maximum Constrained Sequencing To Minimize Tardy Task Weight — различия между версиями
Материал из DISCOPAL
StasFomin (обсуждение | вклад) (Массовая правка: замена \in на ∈) |
StasFomin (обсуждение | вклад) (Массовая правка: замена \sigma на σ) |
||
| Строка 2: | Строка 2: | ||
* Набор <em>T</em> задач, для каждой задачи <em>t ∈ T</em> есть длина <m>l(t)∈ Z^+</m>, вес <m>w(t)∈ Z^+</m> и дедлайн <m>d(t)∈ Z^+</m>, подмножество <em>S ⊆ T</em> и положительное целое <em>K</em>. | * Набор <em>T</em> задач, для каждой задачи <em>t ∈ T</em> есть длина <m>l(t)∈ Z^+</m>, вес <m>w(t)∈ Z^+</m> и дедлайн <m>d(t)∈ Z^+</m>, подмножество <em>S ⊆ T</em> и положительное целое <em>K</em>. | ||
| − | * Найти однопроцессорное расписание <em>σ</em> для <em>T</em>, такая что сумма <em>w(t)</em> по всем <em>t ∈ T</em> для которых <m> | + | * Найти однопроцессорное расписание <em>σ</em> для <em>T</em>, такая что сумма <em>w(t)</em> по всем <em>t ∈ T</em> для которых <m>σ(t)+l(t)>d(t)</m> не превосходит <em>K</em>. |
* Максимизировать число работ в <em>S</em>, выполненных в срок. | * Максимизировать число работ в <em>S</em>, выполненных в срок. | ||
Текущая версия на 21:50, 17 апреля 2023
- Набор T задач, для каждой задачи t ∈ T есть длина , вес и дедлайн , подмножество S ⊆ T и положительное целое K.
- Найти однопроцессорное расписание σ для T, такая что сумма w(t) по всем t ∈ T для которых не превосходит K.
- Максимизировать число работ в S, выполненных в срок.
Задача в лаб17 (рид-онли просмотр)
- Задача в базе NP-полных задач Вигго Кана
- Код задачи в книге «ГД» → «SS3» (аналог)