Просмотр исходного текста страницы Hardprob/Minimum Preemptive Scheduling With Set-Up Times

<!-- start --><!-- {{svg-image-for-hard-problem|{{PAGENAME}}}} -->
* Набор компиляторов <em>C</em>, набор задач <em>T</em>, <em>m</em> процессоров, длительности задач <m>l(t)\in Z^+</m>, нужный для задачи компилятор <m>c(t)\in C</m>, время запуска-настройки для каждого компилятора <m>s(c)\in Z^+</m>.
* Найти <em>m</em>-процессорное [https://ru.wikipedia.org/wiki/%D0%92%D1%8B%D1%82%D0%B5%D1%81%D0%BD%D1%8F%D1%8E%D1%89%D0%B0%D1%8F_%D0%BC%D0%BD%D0%BE%D0%B3%D0%BE%D0%B7%D0%B0%D0%B4%D0%B0%D1%87%D0%BD%D0%BE%D1%81%D1%82%D1%8C вытесняющее расписание] <em>T</em>, т.е. для каждой для каждой задачи <em>t ∈ T</em>, разбиение <em>t</em> на какое-то количество подзадач <m>t_1, \ldots, t_k</m>, такое что 
** <m>\sum_{i=1}^k l(t_i) = l(t)</m>
** и есть некоторое назначение <m>\sigma = (\sigma_1, \sigma_2)</m>, которое назначает каждой подзадаче <m>t_i</m> пару неотрицательных целых <m>(\sigma_1(t_i), \sigma_2(t_i))</m>, таких, что 
*** <m>1 \le \sigma_1(t_i) \le m</m>
*** <m>\sigma_2(t_{i+1}) \ge \sigma_2(t_i) + l(t_i), \ \ 1 \le i < k</m>
** Это расписание должно удовлетворять дополнительному ограничению:
*** Если два подзадачи <m>t_i</m> от <em>t</em> и <m>t_j'</m> от <em>t'</em>, у которых <m>\sigma_2(t_i) < \sigma_2(t_j')</m> запланированы последовательно на одном процессоре (т.е. <m>\sigma_1(t_i) = \sigma_1(t_j')</m>, и нет другой подзадачи <m>t_k"</m>, у которой <m>\sigma_1(t_k") = \sigma_1(t_i)</m> и <m>\sigma_2(t_i) < \sigma_2(t_k") < \sigma_2(t_j')</m>, то 
**** <m>\sigma_2(t_j') \ge \sigma_2(t_i) + l(t_i) + s(c(t'))</m> — если у них один и тот же компилятор (<em>c(t) = c(t')</em>)
**** <m>\sigma_2(t_j') \ge \sigma_2(t_i) + l(t_i) + s(c(t'))</m> — если эти компиляторы разные.
* Минимизировать общее время выполнения, т.е. максимум по всем подзадачам <m>\sigma_2(t_i)+l(t_i)</m>

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

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

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