Hardprob/Minimum Time-Cost Tradeoff — различия между версиями
Материал из DISCOPAL
StasFomin (обсуждение | вклад) (Новая страница: «<!-- start --><!-- {{svg-image-for-hard-problem|{{PAGENAME}}}} --> * Набор активностей <em>J</em>, направленный ациклическ…») |
StasFomin (обсуждение | вклад) (Массовая правка: замена PCRE <m>(\w)_(\w)</m> на <em>\1<sub>\2</sub></em>) |
||
| (не показаны 2 промежуточные версии этого же участника) | |||
| Строка 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> задана монотонно невозрастающая ступенчатая функция с <em>l<sub>j</sub></em> ступенями: |
<m> | <m> | ||
\begin{displaymath} | \begin{displaymath} | ||
c_j(t)=\left\{\begin{array}{ll} | c_j(t)=\left\{\begin{array}{ll} | ||
| − | + | ∈ fty&\mbox{if $0≤t< a_{j,1}$},\\ | |
| − | c_j(a_{j,i})&\mbox{if $a_{j,i} | + | c_j(a_{j,i})&\mbox{if $a_{j,i}≤t<a_{j,i+1}, 1≤i<l_j$},\\ |
| − | 0&\mbox{if $a_{j,l_j} | + | 0&\mbox{if $a_{j,l_j}≤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)≤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> |
---- | ---- | ||
Текущая версия на 22:33, 17 апреля 2023
- Набор активностей J, направленный ациклический граф определяющий отношения предшествования для активностей, , длительности , положительный бюджет B, и для каждой активности j ∈ J задана монотонно невозрастающая ступенчатая функция с lj ступенями:
, где .
- Найти однопроцессорное расписание для J которое соблюдает отношения предшествования, длительности задач и укладывается в бюджет .
StasFomin 07:13, 12 апреля 2023 (UTC): Что-то на первый взгляд очень странное, штраф за первую задачу всегда будет бесконечным, непонятно.
- Минимизировать общее время всех активностей
Задача в лаб22 (рид-онли просмотр)