Hardprob/Maximum Constrained Sequencing To Minimize Tardy Task Weight — различия между версиями
Материал из DISCOPAL
StasFomin (обсуждение | вклад) (Новая страница: «<!-- start --><!-- {{svg-image-for-hard-problem|{{PAGENAME}}}} --> * Набор <em>T</em> задач, для каждой задачи <m>t\in T</m> есть д…») |
StasFomin (обсуждение | вклад) (Массовая правка: замена \sigma на σ) |
||
| (не показаны 4 промежуточные версии этого же участника) | |||
| Строка 1: | Строка 1: | ||
<!-- start --><!-- {{svg-image-for-hard-problem|{{PAGENAME}}}} --> | <!-- start --><!-- {{svg-image-for-hard-problem|{{PAGENAME}}}} --> | ||
| − | * Набор <em>T</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>σ</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>, выполненных в срок. | ||
| Строка 15: | Строка 15: | ||
{{ViggoCode|node175}} | {{ViggoCode|node175}} | ||
| − | {{GDCode| | + | {{GDCode|SS3}} (аналог) |
<!-- * [ Задача в википедии] --> | <!-- * [ Задача в википедии] --> | ||
</small> | </small> | ||
<!-- end --> | <!-- end --> | ||
| − | [[ | + | [[Category:ClassicHardProblems]] |
Текущая версия на 21:50, 17 апреля 2023
- Набор T задач, для каждой задачи t ∈ T есть длина , вес и дедлайн , подмножество S ⊆ T и положительное целое K.
- Найти однопроцессорное расписание σ для T, такая что сумма w(t) по всем t ∈ T для которых не превосходит K.
- Максимизировать число работ в S, выполненных в срок.
Задача в лаб22 (рид-онли просмотр)
- Задача в базе NP-полных задач Вигго Кана
- Код задачи в книге «ГД» → «SS3» (аналог)