Просмотр исходного текста страницы Hardprob/Minimum Precedence Constrained Sequencing With Delays

<!-- start --><!-- {{svg-image-for-hard-problem|{{PAGENAME}}}} -->

* Набор задач <em>T</em>, положительное целое <em>D</em>, для каждой задачи есть целочисленная задержка <m>$0≤d(t)≤D$</m>, 
** направленный ациклический граф <m>G=\left(T,E\right)</m>, определяющий отношения предшествования для этих задач.
* Найти одно-процессорное расписание для <em>T</em>, соблюдающее отношения предшествования и задержки, т.е. инъективная функция <m>S: T→  Z^+</m>, такая, что для каждого ребра <m>\left<t_i,t_j\right>∈  E</m>, выполняется <m>S(t_j)-S(t_i)>d(t_i)</m>
* Минимизировать время выполнение всего расписания.

 <m>\max\limits_{t∈  T} S(t) → \min</m>

----
{{hard-problem-on-lab17|{{PAGENAME}}}}
<!-- * {{has-testdata-and-visualization}} -->
<!-- * {{has-pyomo-model}}   -->
<!-- * {{has-npc-reduction}} -->
<!-- * {{add-random-fuzzing-tests}} -->
----
<small>

{{ViggoCode|node177}}
<!-- {{GDCode|}} -->
<!-- * [ Задача в википедии]  -->
</small>
<!-- end -->

[[Категория:ClassicHardProblems]]