Hardprob/Minimum Storage Time Sequencing - История изменений

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

2023-04-17T18:01:17Z

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

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

2023-04-17T11:34:10Z

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

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

2023-04-11T22:08:26Z

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

2023-04-11T22:06:45Z

Новая страница: « * Набор задач T, для каждой задачи есть длина <m>l(…»

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

* Набор задач T, для каждой задачи есть длина <m>l(t)\in Z^+</m>,
** направленный ациклический граф <m>G=\left(T,E\right)</m>, определяющий отношения предшествования для этих задач, для каждого ребра этого графа есть вес <m>w(t_1,t_2)</m>, измеряющий некий объем хранения, нужный для передачи промежуточных результатов между этими задачами.
* Найти одно-процессорное расписание для T, соблюдающее отношения предшествования, т.е. перестановка <m>\pi: [1..\vert T\vert ]\rightarrow[1..\vert T\vert ]</m>, такая что для каждого ребра <m>\left<t_i,t_j\right>\in E</m> выполняется <m>\pi^{-1}(i)<\pi^{-1}(j)</m>.

* Минимизировать произведение затрат на хранение и времени, т.е.
<m>
\begin{displaymath}
\displaystyle\sum\limits_{
\left<t_{\pi(i)},t_{\pi(j)}\right>\in E} w(t_{\pi(i)},t_{\pi(j)})
\displaystyle\sum\limits_{k=\min(i,j)}^{\max(i,j)} l(t_{\pi(k)}).
\end{displaymath}
</m>

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




----


{{ViggoCode|node176}}





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

@@ Строка 3: / Строка 3: @@
 * Набор задач <em>T</em>, для каждой задачи есть длина <m>l(t)\in Z^+</m>,
 ** направленный ациклический граф <m>G=\left(T,E\right)</m>, определяющий отношения предшествования для этих задач, для каждого ребра этого графа есть вес <m>w(t_1,t_2)</m>, измеряющий некий объем хранения, нужный для передачи промежуточных результатов между этими задачами.
-* Найти одно-процессорное расписание для <em>T</em>, соблюдающее отношения предшествования, т.е. перестановка <m>\pi: [1..\vert T\vert ]\rightarrow[1..\vert T\vert ]</m>, такая что для каждого ребра <m>\left<t_i,t_j\right>\in E</m> выполняется <m>\pi^{-1}(i)<\pi^{-1}(j)</m>.
+* Найти одно-процессорное расписание для <em>T</em>, соблюдающее отношения предшествования, т.е. перестановка <m>\pi: [1..\vert T\vert ]→ [1..\vert T\vert ]</m>, такая что для каждого ребра <m>\left<t_i,t_j\right>\in E</m> выполняется <m>\pi^{-1}(i)<\pi^{-1}(j)</m>.
 * Минимизировать произведение затрат на хранение и времени, т.е.

@@ Строка 1: / Строка 1: @@
 <!-- start --><!-- {{svg-image-for-hard-problem|{{PAGENAME}}}} -->
-* Набор задач <em>T</em>, для каждой задачи есть длина <m>l(t)\in Z^+</m>,
+* Набор задач <em>T</em>, для каждой задачи есть длина <m>l(t)∈  Z^+</m>,
 ** направленный ациклический граф <m>G=\left(T,E\right)</m>, определяющий отношения предшествования для этих задач, для каждого ребра этого графа есть вес <m>w(t_1,t_2)</m>, измеряющий некий объем хранения, нужный для передачи промежуточных результатов между этими задачами.
-* Найти одно-процессорное расписание для <em>T</em>, соблюдающее отношения предшествования, т.е. перестановка <m>\pi: [1..\vert T\vert ]→ [1..\vert T\vert ]</m>, такая что для каждого ребра <m>\left<t_i,t_j\right>\in E</m> выполняется <m>\pi^{-1}(i)<\pi^{-1}(j)</m>.
+* Найти одно-процессорное расписание для <em>T</em>, соблюдающее отношения предшествования, т.е. перестановка <m>\pi: [1..\vert T\vert ]→ [1..\vert T\vert ]</m>, такая что для каждого ребра <m>\left<t_i,t_j\right>∈  E</m> выполняется <m>\pi^{-1}(i)<\pi^{-1}(j)</m>.
 * Минимизировать произведение затрат на хранение и времени, т.е.
@@ Строка 10: / Строка 10: @@
   \begin{displaymath}
 \displaystyle\sum\limits_{
-\left<t_{\pi(i)},t_{\pi(j)}\right>\in E} w(t_{\pi(i)},t_{\pi(j)})
+\left<t_{\pi(i)},t_{\pi(j)}\right>∈  E} w(t_{\pi(i)},t_{\pi(j)})
 \displaystyle\sum\limits_{k=\min(i,j)}^{\max(i,j)} l(t_{\pi(k)}).
 \end{displaymath}

@@ Строка 6: / Строка 6: @@
 * Минимизировать произведение затрат на хранение и времени, т.е.
 <m>
   \begin{displaymath}
@@ Строка 13: / Строка 14: @@
 \end{displaymath}
 </m>
+</blockquote>
 ----
 {{hard-problem-on-lab17|{{PAGENAME}}}}