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

Материал из DISCOPAL
Перейти к: навигация, поиск
(Массовая правка: замена <m>t\in T</m> на <em>t ∈ T</em>)
(Массовая правка: замена \sigma на σ)
 
(не показаны 2 промежуточные версии этого же участника)
Строка 1: Строка 1:
 
<!-- start --><!-- {{svg-image-for-hard-problem|{{PAGENAME}}}} -->
 
<!-- 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)∈  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>\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>, выполненных в срок.
  

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


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

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