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

Версия 06:19, 17 апреля 2023

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

@@ Строка 1: / Строка 1: @@
 <!-- start --><!-- {{svg-image-for-hard-problem|{{PAGENAME}}}} -->
-* Набор <em>T</em> задач, для каждой задачи <em>t ∈ T</em> есть длина <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)\in Z^+</m>, вес <m>w(t)\in Z^+</m> и дедлайн <m>d(t)\in Z^+</m>, подмножество <em>S ⊆ T</em> и положительное целое <em>K</em>.
 * Найти однопроцессорное расписание <em>σ</em> для <em>T</em>, такая что сумма <em>w(t)</em> по всем <em>t ∈ T</em> для которых <m>\sigma(t)+l(t)>d(t)</m> не превосходит <em>K</em>.
 * Максимизировать число работ в <em>S</em>, выполненных в срок.