Hardprob/Minimum Preemptive Scheduling With Set-Up Times - История изменений

StasFomin в 16:58, 20 апреля 2023

2023-04-20T16:58:45Z

StasFomin: Массовая правка: замена PCRE (\w)_(\w)(') на \1_\2\3*

2023-04-17T23:13:56Z

Массовая правка: замена PCRE <m>(\w)_(\w)('*)</m> на \1\2\3

StasFomin: Массовая правка: замена PCRE (\w)_(\w),\s…\s,\s(\w)_(\w)<\/m> на \1_\2, …, \3_\4*

2023-04-17T22:54:02Z

Массовая правка: замена PCRE <m>(\w)_(\w),\s*…\s*,\s*(\w)_(\w)<\/m> на \1\2, …, \3\4

StasFomin: Массовая правка: замена \ldots на …

2023-04-17T22:45:09Z

Массовая правка: замена \ldots на …

StasFomin: Массовая правка: замена PCRE (\w)_(\w) на \1_\2

2023-04-17T22:33:38Z

Массовая правка: замена PCRE <m>(\w)_(\w)</m> на \1\2

StasFomin: Массовая правка: замена \sigma на σ

2023-04-17T21:50:44Z

Массовая правка: замена \sigma на σ

StasFomin: Массовая правка: замена PCRE \\le\s на ≤

2023-04-17T21:28:16Z

Массовая правка: замена PCRE \\le\s на ≤

StasFomin: Массовая правка: замена \in на ∈

2023-04-17T18:01:12Z

Массовая правка: замена \in на ∈

StasFomin: Массовая правка: замена \ge на ≥

2023-04-17T11:30:22Z

Массовая правка: замена \ge на ≥

StasFomin: Массовая правка: замена t\in T на t ∈ T

2023-04-17T06:17:52Z

Массовая правка: замена <m>t\in T</m> на t ∈ T

@@ Строка 22: / Строка 22: @@
 {{ViggoCode|node184}}
-{{GDCode|SS6, SS12}}
+{{GDCode|SS6}}
 <!-- * [ Задача в википедии]  -->
 </small>

@@ Строка 7: / Строка 7: @@
 *** <m>σ_2(t_{i+1}) ≥  σ_2(t_i) + l(t_i), \ \ 1 ≤i < k</m>
 ** Это расписание должно удовлетворять дополнительному ограничению:
-*** Если два подзадачи <em>t<sub>i</sub></em> от <em>t</em> и <m>t_j'</m> от <em>t'</em>, у которых <m>σ_2(t_i) < σ_2(t_j')</m> запланированы последовательно на одном процессоре (т.е. <m>σ_1(t_i) = σ_1(t_j')</m>, и нет другой подзадачи <m>t_k"</m>, у которой <m>σ_1(t_k") = σ_1(t_i)</m> и <m>σ_2(t_i) < σ_2(t_k") < σ_2(t_j')</m>, то
+*** Если два подзадачи <em>t<sub>i</sub></em> от <em>t</em> и <em>t<sub>j</sub>'</em> от <em>t'</em>, у которых <m>σ_2(t_i) < σ_2(t_j')</m> запланированы последовательно на одном процессоре (т.е. <m>σ_1(t_i) = σ_1(t_j')</m>, и нет другой подзадачи <m>t_k"</m>, у которой <m>σ_1(t_k") = σ_1(t_i)</m> и <m>σ_2(t_i) < σ_2(t_k") < σ_2(t_j')</m>, то
 **** <m>σ_2(t_j') ≥  σ_2(t_i) + l(t_i) + s(c(t'))</m> — если у них один и тот же компилятор (<em>c(t) = c(t')</em>)
 **** <m>σ_2(t_j') ≥  σ_2(t_i) + l(t_i) + s(c(t'))</m> — если эти компиляторы разные.

@@ Строка 1: / Строка 1: @@
 <!-- start --><!-- {{svg-image-for-hard-problem|{{PAGENAME}}}} -->
 * Набор компиляторов <em>C</em>, набор задач <em>T</em>, <em>m</em> процессоров, длительности задач <m>l(t)∈  Z^+</m>, нужный для задачи компилятор <m>c(t)∈  C</m>, время запуска-настройки для каждого компилятора <m>s(c)∈  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, …, t_k</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> на какое-то количество подзадач <em>t<sub>1</sub>, …, t<sub>k</sub></em>, такое что
 ** <m>\sum_{i=1}^k l(t_i) = l(t)</m>
 ** и есть некоторое назначение <m>σ = (σ_1, σ_2)</m>, которое назначает каждой подзадаче <em>t<sub>i</sub></em> пару неотрицательных целых <m>(σ_1(t_i), σ_2(t_i))</m>, таких, что

@@ Строка 1: / Строка 1: @@
 <!-- start --><!-- {{svg-image-for-hard-problem|{{PAGENAME}}}} -->
 * Набор компиляторов <em>C</em>, набор задач <em>T</em>, <em>m</em> процессоров, длительности задач <m>l(t)∈  Z^+</m>, нужный для задачи компилятор <m>c(t)∈  C</m>, время запуска-настройки для каждого компилятора <m>s(c)∈  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>, такое что
+* Найти <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, …, t_k</m>, такое что
 ** <m>\sum_{i=1}^k l(t_i) = l(t)</m>
 ** и есть некоторое назначение <m>σ = (σ_1, σ_2)</m>, которое назначает каждой подзадаче <em>t<sub>i</sub></em> пару неотрицательных целых <m>(σ_1(t_i), σ_2(t_i))</m>, таких, что

@@ Строка 3: / Строка 3: @@
 * Найти <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>σ = (σ_1, σ_2)</m>, которое назначает каждой подзадаче <m>t_i</m> пару неотрицательных целых <m>(σ_1(t_i), σ_2(t_i))</m>, таких, что
+** и есть некоторое назначение <m>σ = (σ_1, σ_2)</m>, которое назначает каждой подзадаче <em>t<sub>i</sub></em> пару неотрицательных целых <m>(σ_1(t_i), σ_2(t_i))</m>, таких, что
 *** <m>1 ≤σ_1(t_i) ≤m</m>
 *** <m>σ_2(t_{i+1}) ≥  σ_2(t_i) + l(t_i), \ \ 1 ≤i < k</m>
 ** Это расписание должно удовлетворять дополнительному ограничению:
-*** Если два подзадачи <m>t_i</m> от <em>t</em> и <m>t_j'</m> от <em>t'</em>, у которых <m>σ_2(t_i) < σ_2(t_j')</m> запланированы последовательно на одном процессоре (т.е. <m>σ_1(t_i) = σ_1(t_j')</m>, и нет другой подзадачи <m>t_k"</m>, у которой <m>σ_1(t_k") = σ_1(t_i)</m> и <m>σ_2(t_i) < σ_2(t_k") < σ_2(t_j')</m>, то
+*** Если два подзадачи <em>t<sub>i</sub></em> от <em>t</em> и <m>t_j'</m> от <em>t'</em>, у которых <m>σ_2(t_i) < σ_2(t_j')</m> запланированы последовательно на одном процессоре (т.е. <m>σ_1(t_i) = σ_1(t_j')</m>, и нет другой подзадачи <m>t_k"</m>, у которой <m>σ_1(t_k") = σ_1(t_i)</m> и <m>σ_2(t_i) < σ_2(t_k") < σ_2(t_j')</m>, то
 **** <m>σ_2(t_j') ≥  σ_2(t_i) + l(t_i) + s(c(t'))</m> — если у них один и тот же компилятор (<em>c(t) = c(t')</em>)
 **** <m>σ_2(t_j') ≥  σ_2(t_i) + l(t_i) + s(c(t'))</m> — если эти компиляторы разные.

@@ Строка 4: / Строка 4: @@
 ** <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>1 ≤\sigma_1(t_i) ≤m</m>
-*** <m>\sigma_2(t_{i+1}) ≥  \sigma_2(t_i) + l(t_i), \ \ 1 \le i < k</m>
+*** <m>\sigma_2(t_{i+1}) ≥  \sigma_2(t_i) + l(t_i), \ \ 1 ≤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>, то

@@ Строка 5: / Строка 5: @@
 ** и есть некоторое назначение <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>\sigma_2(t_{i+1}) ≥  \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') ≥  \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_j') ≥  \sigma_2(t_i) + l(t_i) + s(c(t'))</m> — если эти компиляторы разные.
 * Минимизировать общее время выполнения, т.е. максимум по всем подзадачам <m>\sigma_2(t_i)+l(t_i)</m>