Hardprob/Minimum Resource Constrained Scheduling - История изменений

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

2023-04-17T22:33:38Z

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

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

2023-04-17T22:16:38Z

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

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

2023-04-17T21:26:18Z

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

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

2023-04-17T18:01:15Z

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

StasFomin в 07:49, 12 апреля 2023

2023-04-12T07:49:25Z

StasFomin в 07:47, 12 апреля 2023

2023-04-12T07:47:54Z

StasFomin: Новая страница: « * Набор задач T с длинами l(t), m процессо…»

2023-04-12T07:47:33Z

Новая страница: « * Набор задач T с длинами l(t), m процессо…»

Новая страница

* Набор задач T с длинами l(t), m процессоров, число ресурсов <m>r</m>, ресурсные потребности задач <m>r_i(t), \ 1 \leq i \leq r \ ∀t ∈ T</m> и ресурсные ограничения <m>b_i</m>.
* Найти m-процессорное расписание для T, соблюдающую отношения предшествования, т.е. функцию <m>f: T→ Z</m>, такую что
** <m>∀ u \leq 0</m>, если S(u) будет набор задач t для которых <m>f(t) \leq u < f(t)+l(t)</m>, то <m>\vert S(u)\vert \leq m</m> и <m>
\begin{displaymath}
∀ i \ \sum_{t \in S(u)}r_i(t) \leq b_i.
\end{displaymath}
</m>
* Минимизировать общую длительность расписания, т.е.
<m>\max_{t \in T}(f(t)+l(t))</m>

----
{{hard-problem-on-lab17|{{PAGENAME}}}}




----


{{ViggoCode|node183}}
{{GDCode|SS10}}




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

@@ Строка 1: / Строка 1: @@
 <!-- start --><!-- {{svg-image-for-hard-problem|{{PAGENAME}}}} -->
-* Набор задач <em>T</em> с длинами <em>l(t)</em>, <em>m</em> процессоров, число ресурсов <m>r</m>, ресурсные потребности задач <m>r_i(t), \ 1 ≤ i ≤ r \ ∀t ∈ T</m> и ресурсные ограничения <m>b_i</m>.
+* Набор задач <em>T</em> с длинами <em>l(t)</em>, <em>m</em> процессоров, число ресурсов <m>r</m>, ресурсные потребности задач <m>r_i(t), \ 1 ≤ i ≤ r \ ∀t ∈ T</m> и ресурсные ограничения <em>b<sub>i</sub></em>.
 * Найти <em>m</em>-процессорное расписание для <em>T</em>, соблюдающую ресурсные ограничения, т.е. функцию <em>f: T → Z</em>, такую что
 ** <m>∀ u ≤ 0</m>, если <em>S(u)</em> будет набор задач <em>t</em> для которых <m>f(t) ≤ u < f(t)+l(t)</m>, то <m>\vert S(u)\vert ≤ m</m> и <m>

@@ Строка 1: / Строка 1: @@
 <!-- start --><!-- {{svg-image-for-hard-problem|{{PAGENAME}}}} -->
 * Набор задач <em>T</em> с длинами <em>l(t)</em>, <em>m</em> процессоров, число ресурсов <m>r</m>, ресурсные потребности задач <m>r_i(t), \ 1 ≤ i ≤ r \ ∀t ∈ T</m> и ресурсные ограничения <m>b_i</m>.
-* Найти <em>m</em>-процессорное расписание для <em>T</em>, соблюдающую ресурсные ограничения, т.е. функцию <m>f: T→ Z</m>, такую что
+* Найти <em>m</em>-процессорное расписание для <em>T</em>, соблюдающую ресурсные ограничения, т.е. функцию <em>f: T → Z</em>, такую что
 ** <m>∀ u ≤ 0</m>, если <em>S(u)</em> будет набор задач <em>t</em> для которых <m>f(t) ≤ u < f(t)+l(t)</m>, то <m>\vert S(u)\vert ≤ m</m> и <m>
 \begin{displaymath}

@@ Строка 1: / Строка 1: @@
 <!-- start --><!-- {{svg-image-for-hard-problem|{{PAGENAME}}}} -->
-* Набор задач <em>T</em> с длинами <em>l(t)</em>, <em>m</em> процессоров, число ресурсов <m>r</m>, ресурсные потребности задач <m>r_i(t), \ 1 \leq i \leq r \ ∀t ∈ T</m> и ресурсные ограничения <m>b_i</m>.
+* Набор задач <em>T</em> с длинами <em>l(t)</em>, <em>m</em> процессоров, число ресурсов <m>r</m>, ресурсные потребности задач <m>r_i(t), \ 1 ≤ i ≤ r \ ∀t ∈ T</m> и ресурсные ограничения <m>b_i</m>.
 * Найти <em>m</em>-процессорное расписание для <em>T</em>, соблюдающую ресурсные ограничения, т.е. функцию <m>f: T→ Z</m>, такую что
-** <m>∀ u \leq 0</m>, если <em>S(u)</em> будет набор задач <em>t</em> для которых <m>f(t) \leq u < f(t)+l(t)</m>, то <m>\vert S(u)\vert \leq m</m> и <m>
+** <m>∀ u ≤ 0</m>, если <em>S(u)</em> будет набор задач <em>t</em> для которых <m>f(t) ≤ u < f(t)+l(t)</m>, то <m>\vert S(u)\vert ≤ m</m> и <m>
 \begin{displaymath}
-∀ i \ \sum_{t ∈  S(u)}r_i(t) \leq b_i.
+∀ i \ \sum_{t ∈  S(u)}r_i(t) ≤ b_i.
 \end{displaymath}
 </m>

@@ Строка 4: / Строка 4: @@
 ** <m>∀ u \leq 0</m>, если <em>S(u)</em> будет набор задач <em>t</em> для которых <m>f(t) \leq u < f(t)+l(t)</m>, то <m>\vert S(u)\vert \leq m</m> и <m>
 \begin{displaymath}
-∀ i \ \sum_{t \in S(u)}r_i(t) \leq b_i.
+∀ i \ \sum_{t ∈  S(u)}r_i(t) \leq b_i.
 \end{displaymath}
 </m>
 * Минимизировать общую длительность расписания, т.е.
-  <m>\max_{t \in T}(f(t)+l(t)) → \min</m>
+  <m>\max_{t ∈  T}(f(t)+l(t)) → \min</m>
 ----

@@ Строка 1: / Строка 1: @@
 <!-- start --><!-- {{svg-image-for-hard-problem|{{PAGENAME}}}} -->
 * Набор задач <em>T</em> с длинами <em>l(t)</em>, <em>m</em> процессоров, число ресурсов <m>r</m>, ресурсные потребности задач <m>r_i(t), \ 1 \leq i \leq r \ ∀t ∈ T</m> и ресурсные ограничения <m>b_i</m>.
-* Найти <em>m</em>-процессорное расписание для <em>T</em>, соблюдающую отношения предшествования, т.е. функцию <m>f: T→ Z</m>, такую что
+* Найти <em>m</em>-процессорное расписание для <em>T</em>, соблюдающую ресурсные ограничения, т.е. функцию <m>f: T→ Z</m>, такую что
 ** <m>∀ u \leq 0</m>, если <em>S(u)</em> будет набор задач <em>t</em> для которых <m>f(t) \leq u < f(t)+l(t)</m>, то <m>\vert S(u)\vert \leq m</m> и <m>
 \begin{displaymath}