Hardprob/Minimum Time-Cost Tradeoff — различия между версиями
Материал из DISCOPAL
StasFomin (обсуждение | вклад) (Новая страница: «<!-- start --><!-- {{svg-image-for-hard-problem|{{PAGENAME}}}} --> * Набор активностей <em>J</em>, направленный ациклическ…») |
StasFomin (обсуждение | вклад) (Массовая правка: замена \in на ∈) |
||
| Строка 1: | Строка 1: | ||
<!-- start --><!-- {{svg-image-for-hard-problem|{{PAGENAME}}}} --> | <!-- start --><!-- {{svg-image-for-hard-problem|{{PAGENAME}}}} --> | ||
| − | * Набор активностей <em>J</em>, направленный ациклический граф определяющий отношения предшествования для активностей, , длительности <m>t_j > 0, ∀ | + | * Набор активностей <em>J</em>, направленный ациклический граф определяющий отношения предшествования для активностей, , длительности <m>t_j > 0, ∀ j∈ J </m>, положительный бюджет <em>B</em>, и для каждой активности <em>j ∈ J</em> задана монотонно невозрастающая ступенчатая функция с <m>l_j</m> ступенями: |
<m> | <m> | ||
\begin{displaymath} | \begin{displaymath} | ||
c_j(t)=\left\{\begin{array}{ll} | c_j(t)=\left\{\begin{array}{ll} | ||
| − | + | ∈ fty&\mbox{if $0\le t< a_{j,1}$},\\ | |
c_j(a_{j,i})&\mbox{if $a_{j,i}\le t<a_{j,i+1}, 1\le i<l_j$},\\ | c_j(a_{j,i})&\mbox{if $a_{j,i}\le t<a_{j,i+1}, 1\le i<l_j$},\\ | ||
0&\mbox{if $a_{j,l_j}\le t$}, | 0&\mbox{if $a_{j,l_j}\le t$}, | ||
\end{array}\right. | \end{array}\right. | ||
| − | </m>, где <m> | + | </m>, где <m>∈ fty>c_j(a_{j,1})>\cdots>c_j(a_{j,l_j})</m>. |
| − | * Найти однопроцессорное расписание для <em>J</em> которое соблюдает отношения предшествования, длительности задач и укладывается в бюджет <m>\sum_{ | + | * Найти однопроцессорное расписание для <em>J</em> которое соблюдает отношения предшествования, длительности задач и укладывается в бюджет <m>\sum_{j∈ J} c_j(t_j)\le B</m>. |
[[Участник:StasFomin|StasFomin]] 07:13, 12 апреля 2023 (UTC): Что-то на первый взгляд очень странное, штраф за первую задачу всегда будет бесконечным, непонятно. | [[Участник:StasFomin|StasFomin]] 07:13, 12 апреля 2023 (UTC): Что-то на первый взгляд очень странное, штраф за первую задачу всегда будет бесконечным, непонятно. | ||
| − | * Минимизировать общее время всех активностей <m>\sum_{ | + | * Минимизировать общее время всех активностей <m>\sum_{j∈ J} t_j</m> |
---- | ---- | ||
Версия 18:01, 17 апреля 2023
- Набор активностей J, направленный ациклический граф определяющий отношения предшествования для активностей, , длительности , положительный бюджет B, и для каждой активности j ∈ J задана монотонно невозрастающая ступенчатая функция с ступенями:
, где .
- Найти однопроцессорное расписание для J которое соблюдает отношения предшествования, длительности задач и укладывается в бюджет .
StasFomin 07:13, 12 апреля 2023 (UTC): Что-то на первый взгляд очень странное, штраф за первую задачу всегда будет бесконечным, непонятно.
- Минимизировать общее время всех активностей
Задача в лаб22 (рид-онли просмотр)