Hardprob/Minimum Storage Time Sequencing — различия между версиями

Материал из DISCOPAL
Перейти к: навигация, поиск
(Новая страница: «<!-- start --><!-- {{svg-image-for-hard-problem|{{PAGENAME}}}} --> * Набор задач <em>T</em>, для каждой задачи есть длина <m>l(…»)
 
(Массовая правка: замена \in на ∈)
 
(не показаны 2 промежуточные версии этого же участника)
Строка 1: Строка 1:
 
<!-- start --><!-- {{svg-image-for-hard-problem|{{PAGENAME}}}} -->
 
<!-- 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>, измеряющий некий объем хранения, нужный для передачи промежуточных результатов между этими задачами.
 
** направленный ациклический граф <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>∈  E</m> выполняется <m>\pi^{-1}(i)<\pi^{-1}(j)</m>.
  
 
* Минимизировать произведение затрат на хранение и времени, т.е.
 
* Минимизировать произведение затрат на хранение и времени, т.е.
 +
<blockquote>
 
<m>
 
<m>
 
  \begin{displaymath}
 
  \begin{displaymath}
 
\displaystyle\sum\limits_{
 
\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)}).
 
\displaystyle\sum\limits_{k=\min(i,j)}^{\max(i,j)} l(t_{\pi(k)}).
 
\end{displaymath}
 
\end{displaymath}
 
</m>
 
</m>
 
+
</blockquote>
 
----
 
----
 
{{hard-problem-on-lab17|{{PAGENAME}}}}
 
{{hard-problem-on-lab17|{{PAGENAME}}}}

Текущая версия на 18:01, 17 апреля 2023


  • Набор задач T, для каждой задачи есть длина ,
    • направленный ациклический граф , определяющий отношения предшествования для этих задач, для каждого ребра этого графа есть вес , измеряющий некий объем хранения, нужный для передачи промежуточных результатов между этими задачами.
  • Найти одно-процессорное расписание для T, соблюдающее отношения предшествования, т.е. перестановка , такая что для каждого ребра выполняется .
  • Минимизировать произведение затрат на хранение и времени, т.е.


Задача в лаб22 (рид-онли просмотр)