Hardprob/Maximum Constrained Sequencing To Minimize Tardy Task Weight — различия между версиями

Материал из DISCOPAL
Перейти к: навигация, поиск
(Новая страница: «<!-- start --><!-- {{svg-image-for-hard-problem|{{PAGENAME}}}} --> * Набор <em>T</em> задач, для каждой задачи <m>t\in T</m> есть д…»)
 
(Массовая правка: замена \sigma на σ)
 
(не показаны 4 промежуточные версии этого же участника)
Строка 1: Строка 1:
 
<!-- start --><!-- {{svg-image-for-hard-problem|{{PAGENAME}}}} -->
 
<!-- start --><!-- {{svg-image-for-hard-problem|{{PAGENAME}}}} -->
  
* Набор <em>T</em> задач, для каждой задачи <m>t\in T</m> есть длина <m>l(t)\in Z^+</m>, вес <m>w(t)\in Z^+</m> и дедлайн <m>d(t)\in Z^+</m>, подмножество <m>S\subseteq T</m> и положительное целое <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> по всем <m>t\in T</m> для которых <m>\sigma(t)+l(t)>d(t)</m> не превосходит <em>K</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|аналог SS3}}
+
{{GDCode|SS3}} (аналог)
 
<!-- * [ Задача в википедии]  -->
 
<!-- * [ Задача в википедии]  -->
 
</small>
 
</small>
 
<!-- end -->
 
<!-- end -->
  
[[Категория:ClassicHardProblems]]
+
[[Category:ClassicHardProblems]]

Текущая версия на 21:50, 17 апреля 2023


  • Набор T задач, для каждой задачи t ∈ T есть длина , вес и дедлайн , подмножество S ⊆ T и положительное целое K.
  • Найти однопроцессорное расписание σ для T, такая что сумма w(t) по всем t ∈ T для которых не превосходит K.
  • Максимизировать число работ в S, выполненных в срок.

Задача в лаб22 (рид-онли просмотр)