Hardprob/Minimum Precedence Constrained Sequencing With Delays - История изменений

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

2023-04-17T21:28:15Z

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

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

2023-04-17T18:01:11Z

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

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

2023-04-17T11:34:08Z

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

StasFomin в 22:19, 11 апреля 2023

2023-04-11T22:19:02Z

StasFomin: Новая страница: « * Набор задач T, положительное целое D, для…»

2023-04-11T22:18:45Z

Новая страница: « * Набор задач T, положительное целое D, для…»

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

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

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




----


{{ViggoCode|node177}}





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

@@ Строка 1: / Строка 1: @@
 <!-- start --><!-- {{svg-image-for-hard-problem|{{PAGENAME}}}} -->
-* Набор задач <em>T</em>, положительное целое <em>D</em>, для каждой задачи есть целочисленная задержка <m>$0\le d(t)\le D$</m>,
+* Набор задач <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>

@@ Строка 3: / Строка 3: @@
 * Набор задач <em>T</em>, положительное целое <em>D</em>, для каждой задачи есть целочисленная задержка <m>$0\le d(t)\le D$</m>,
 ** направленный ациклический граф <m>G=\left(T,E\right)</m>, определяющий отношения предшествования для этих задач.
-* Найти одно-процессорное расписание для <em>T</em>, соблюдающее отношения предшествования и задержки, т.е. инъективная функция <m>S: T→  Z^+</m>, такая, что для каждого ребра <m>\left<t_i,t_j\right>\in E</m>, выполняется <m>S(t_j)-S(t_i)>d(t_i)</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\in T} S(t) → \min</m>
+  <m>\max\limits_{t∈  T} S(t) → \min</m>
 ----

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

@@ Строка 5: / Строка 5: @@
 * Найти одно-процессорное расписание для <em>T</em>, соблюдающее отношения предшествования и задержки, т.е. инъективная функция <m>S: T\rightarrow Z^+</m>, такая, что для каждого ребра <m>\left<t_i,t_j\right>\in E</m>, выполняется <m>S(t_j)-S(t_i)>d(t_i)</m>
 * Минимизировать время выполнение всего расписания.
 <m>
-\max\limits_{t\in T} S(t) → \min
+ <m>\max\limits_{t\in T} S(t) → \min</m>
 </m>
 ----