Hardprob/Minimum Storage Time Sequencing — различия между версиями
Материал из DISCOPAL
StasFomin (обсуждение | вклад) |
StasFomin (обсуждение | вклад) (Массовая правка: замена \rightarrow на →) |
||
| Строка 3: | Строка 3: | ||
* Набор задач <em>T</em>, для каждой задачи есть длина <m>l(t)\in Z^+</m>, | * Набор задач <em>T</em>, для каждой задачи есть длина <m>l(t)\in 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 ] | + | * Найти одно-процессорное расписание для <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>. |
* Минимизировать произведение затрат на хранение и времени, т.е. | * Минимизировать произведение затрат на хранение и времени, т.е. | ||
Версия 11:34, 17 апреля 2023
- Набор задач T, для каждой задачи есть длина ,
- направленный ациклический граф , определяющий отношения предшествования для этих задач, для каждого ребра этого графа есть вес , измеряющий некий объем хранения, нужный для передачи промежуточных результатов между этими задачами.
- Найти одно-процессорное расписание для T, соблюдающее отношения предшествования, т.е. перестановка , такая что для каждого ребра выполняется .
- Минимизировать произведение затрат на хранение и времени, т.е.
Задача в лаб22 (рид-онли просмотр)