Hardprob/Minimum Weighted Completion Time Scheduling - История изменений

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

2023-04-17T23:35:34Z

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

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

2023-04-17T23:33:54Z

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

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

2023-04-17T21:26:20Z

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

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

2023-04-17T18:01:31Z

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

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

2023-04-17T11:34:13Z

Массовая правка: замена \rightarrow на →

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

2023-04-17T11:29:37Z

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

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

2023-04-17T06:17:52Z

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

StasFomin в 17:26, 12 апреля 2023

2023-04-12T17:26:15Z

StasFomin: Новая страница: « * Набор задач T, m идентичных процессоров, к…»

2023-04-12T17:14:51Z

Новая страница: « * Набор задач T, m идентичных процессоров, к…»

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

* Набор задач T, m идентичных процессоров, каждая задача <m>t\in T</m> имеет
** время выпуска <m>r(t)\in Z^+</m>
** длительность <m>l(t)\in Z^+</m>.
** вес <m>w(t) \in Z^+ </m>.
* Найти m-процессорное расписание для T, удовлетворяющее ограничениям времени выпуска, т.е. функция <m>f : T \rightarrow N </m>, такая что для всех <m>u \geq 0</m> и для любого процессора i, если S(u,i) это набор задач для которых <m>f(t)_{1} \leq u < f(t)_{1}+l(t)</m> и <m>f(t)_{2}=i</m>, то
<m>\vert S(u,i)\vert = 1</m> и для каждой задачи t, <m>f(t)_{1} \geq r(t)</m>.
* Минимизировать взешенную сумму времен выполнения, т.е.
<m>\sum_{t\in T} w(t)(f(t)_1+l(t)) → \min</m>

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




----


{{ViggoCode|node186}}
{{GDCode|SS13}}




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

@@ Строка 4: / Строка 4: @@
 ** длительность <m>l(t)∈  Z^+</m>.
 ** вес <m>w(t) ∈  Z^+ </m>.
-* Найти <em>m</em>-процессорное расписание для <em>T</em>, удовлетворяющее ограничениям времени выпуска, т.е. функция <em>f : T → N</em> , такая что для всех <m>u ≥  0</m> и для любого процессора <em>i</em>, если <em>S(u,i)</em> это набор задач для которых <m>f(t)_{1} ≤ u < f(t)_{1}+l(t)</m> и <m>f(t)_{2}=i</m>, то
+* Найти <em>m</em>-процессорное расписание для <em>T</em>, удовлетворяющее ограничениям времени выпуска, т.е. функция <em>f : T → N</em> , такая что для всех <em>u ≥ 0</em>  и для любого процессора <em>i</em>, если <em>S(u,i)</em> это набор задач для которых <m>f(t)_{1} ≤ u < f(t)_{1}+l(t)</m> и <m>f(t)_{2}=i</m>, то
 <m>\vert S(u,i)\vert = 1</m> и для каждой задачи <em>t</em>, <m>f(t)_{1} ≥  r(t)</m>.
 * Минимизировать взешенную сумму времен выполнения, т.е.

@@ Строка 4: / Строка 4: @@
 ** длительность <m>l(t)∈  Z^+</m>.
 ** вес <m>w(t) ∈  Z^+ </m>.
-* Найти <em>m</em>-процессорное расписание для <em>T</em>, удовлетворяющее ограничениям времени выпуска, т.е. функция <m>f : T →  N </m>, такая что для всех <m>u ≥  0</m> и для любого процессора <em>i</em>, если <em>S(u,i)</em> это набор задач для которых <m>f(t)_{1} ≤ u < f(t)_{1}+l(t)</m> и <m>f(t)_{2}=i</m>, то
+* Найти <em>m</em>-процессорное расписание для <em>T</em>, удовлетворяющее ограничениям времени выпуска, т.е. функция <em>f : T → N</em> , такая что для всех <m>u ≥  0</m> и для любого процессора <em>i</em>, если <em>S(u,i)</em> это набор задач для которых <m>f(t)_{1} ≤ u < f(t)_{1}+l(t)</m> и <m>f(t)_{2}=i</m>, то
 <m>\vert S(u,i)\vert = 1</m> и для каждой задачи <em>t</em>, <m>f(t)_{1} ≥  r(t)</m>.
 * Минимизировать взешенную сумму времен выполнения, т.е.

@@ Строка 4: / Строка 4: @@
 ** длительность <m>l(t)∈  Z^+</m>.
 ** вес <m>w(t) ∈  Z^+ </m>.
-* Найти <em>m</em>-процессорное расписание для <em>T</em>, удовлетворяющее ограничениям времени выпуска, т.е. функция <m>f : T →  N </m>, такая что для всех <m>u ≥  0</m> и для любого процессора <em>i</em>, если <em>S(u,i)</em> это набор задач для которых <m>f(t)_{1} \leq u < f(t)_{1}+l(t)</m> и <m>f(t)_{2}=i</m>, то
+* Найти <em>m</em>-процессорное расписание для <em>T</em>, удовлетворяющее ограничениям времени выпуска, т.е. функция <m>f : T →  N </m>, такая что для всех <m>u ≥  0</m> и для любого процессора <em>i</em>, если <em>S(u,i)</em> это набор задач для которых <m>f(t)_{1} ≤ u < f(t)_{1}+l(t)</m> и <m>f(t)_{2}=i</m>, то
 <m>\vert S(u,i)\vert = 1</m> и для каждой задачи <em>t</em>, <m>f(t)_{1} ≥  r(t)</m>.
 * Минимизировать взешенную сумму времен выполнения, т.е.

@@ Строка 1: / Строка 1: @@
 <!-- start --><!-- {{svg-image-for-hard-problem|{{PAGENAME}}}} -->
 * Набор задач <em>T</em>, <em>m</em> идентичных процессоров, каждая задача <em>t ∈ T</em> имеет
-** время выпуска <m>r(t)\in Z^+</m>
+** время выпуска <m>r(t)∈  Z^+</m>
-** длительность <m>l(t)\in Z^+</m>.
+** длительность <m>l(t)∈  Z^+</m>.
-** вес <m>w(t) \in Z^+ </m>.
+** вес <m>w(t) ∈  Z^+ </m>.
 * Найти <em>m</em>-процессорное расписание для <em>T</em>, удовлетворяющее ограничениям времени выпуска, т.е. функция <m>f : T →  N </m>, такая что для всех <m>u ≥  0</m> и для любого процессора <em>i</em>, если <em>S(u,i)</em> это набор задач для которых <m>f(t)_{1} \leq u < f(t)_{1}+l(t)</m> и <m>f(t)_{2}=i</m>, то
 <m>\vert S(u,i)\vert = 1</m> и для каждой задачи <em>t</em>, <m>f(t)_{1} ≥  r(t)</m>.
 * Минимизировать взешенную сумму времен выполнения, т.е.
-  <m>\sum_{t\in T} w(t)(f(t)_1+l(t)) → \min</m>
+  <m>\sum_{t∈  T} w(t)(f(t)_1+l(t)) → \min</m>
 ----

@@ Строка 4: / Строка 4: @@
 ** длительность <m>l(t)\in Z^+</m>.
 ** вес <m>w(t) \in Z^+ </m>.
-* Найти <em>m</em>-процессорное расписание для <em>T</em>, удовлетворяющее ограничениям времени выпуска, т.е. функция <m>f : T \rightarrow N </m>, такая что для всех <m>u ≥  0</m> и для любого процессора <em>i</em>, если <em>S(u,i)</em> это набор задач для которых <m>f(t)_{1} \leq u < f(t)_{1}+l(t)</m> и <m>f(t)_{2}=i</m>, то
+* Найти <em>m</em>-процессорное расписание для <em>T</em>, удовлетворяющее ограничениям времени выпуска, т.е. функция <m>f : T →  N </m>, такая что для всех <m>u ≥  0</m> и для любого процессора <em>i</em>, если <em>S(u,i)</em> это набор задач для которых <m>f(t)_{1} \leq u < f(t)_{1}+l(t)</m> и <m>f(t)_{2}=i</m>, то
 <m>\vert S(u,i)\vert = 1</m> и для каждой задачи <em>t</em>, <m>f(t)_{1} ≥  r(t)</m>.
 * Минимизировать взешенную сумму времен выполнения, т.е.

@@ Строка 18: / Строка 18: @@
 <small>
-{{ViggoCode|node186}}
+{{ViggoCode|node187}}
 {{GDCode|SS13}}
 <!-- * [ Задача в википедии]  -->