Hardprob/Minimum Storage Time Sequencing — различия между версиями
Материал из DISCOPAL
StasFomin (обсуждение | вклад) (Массовая правка: замена \rightarrow на →) |
StasFomin (обсуждение | вклад) (Массовая правка: замена \in на ∈) |
||
| Строка 1: | Строка 1: | ||
<!-- start --><!-- {{svg-image-for-hard-problem|{{PAGENAME}}}} --> | <!-- start --><!-- {{svg-image-for-hard-problem|{{PAGENAME}}}} --> | ||
| − | * Набор задач <em>T</em>, для каждой задачи есть длина <m>l(t) | + | * Набор задач <em>T</em>, для каждой задачи есть длина <m>l(t)∈ Z^+</m>, |
** направленный ациклический граф <m>G=\left(T,E\right)</m>, определяющий отношения предшествования для этих задач, для каждого ребра этого графа есть вес <m>w(t_1,t_2)</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> | + | * Найти одно-процессорное расписание для <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} | \begin{displaymath} | ||
\displaystyle\sum\limits_{ | \displaystyle\sum\limits_{ | ||
| − | \left<t_{\pi(i)},t_{\pi(j)}\right> | + | \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)}). | \displaystyle\sum\limits_{k=\min(i,j)}^{\max(i,j)} l(t_{\pi(k)}). | ||
\end{displaymath} | \end{displaymath} | ||
Текущая версия на 18:01, 17 апреля 2023
- Набор задач T, для каждой задачи есть длина ,
- направленный ациклический граф , определяющий отношения предшествования для этих задач, для каждого ребра этого графа есть вес , измеряющий некий объем хранения, нужный для передачи промежуточных результатов между этими задачами.
- Найти одно-процессорное расписание для T, соблюдающее отношения предшествования, т.е. перестановка , такая что для каждого ребра выполняется .
- Минимизировать произведение затрат на хранение и времени, т.е.
Задача в лаб22 (рид-онли просмотр)