Hardprob/Minimum Time-Cost Tradeoff — различия между версиями

Материал из DISCOPAL
Перейти к: навигация, поиск
(Новая страница: «<!-- start --><!-- {{svg-image-for-hard-problem|{{PAGENAME}}}} --> * Набор активностей <em>J</em>, направленный ациклическ…»)
 
(Массовая правка: замена 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, ∀ j\in J </m>, положительный бюджет <em>B</em>, и для каждой активности <em>j ∈ J</em> задана монотонно невозрастающая ступенчатая функция с <m>l_j</m> ступенями:
+
* Набор активностей <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}
\infty&\mbox{if $0\le t< a_{j,1}$},\\
+
∈ fty&\mbox{if $0≤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}≤t<a_{j,i+1}, 1≤i<l_j$},\\
0&\mbox{if $a_{j,l_j}\le t$},
+
0&\mbox{if $a_{j,l_j}≤t$},
 
\end{array}\right.
 
\end{array}\right.
</m>, где <m>\infty>c_j(a_{j,1})>\cdots>c_j(a_{j,l_j})</m>.
+
</m>, где <m>∈ fty>c_j(a_{j,1})>\cdots>c_j(a_{j,l_j})</m>.
  
* Найти однопроцессорное расписание для <em>J</em> которое соблюдает отношения предшествования, длительности задач и укладывается в бюджет <m>\sum_{j\in J} c_j(t_j)\le B</m>.
+
* Найти однопроцессорное расписание для <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_{j\in J} t_j</m>
+
* Минимизировать общее время всех активностей <m>\sum_{j∈  J} t_j</m>
  
 
----
 
----

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


  • Набор активностей J, направленный ациклический граф определяющий отношения предшествования для активностей, , длительности , положительный бюджет B, и для каждой активности j ∈ J задана монотонно невозрастающая ступенчатая функция с lj ступенями:

, где .

  • Найти однопроцессорное расписание для J которое соблюдает отношения предшествования, длительности задач и укладывается в бюджет .

StasFomin 07:13, 12 апреля 2023 (UTC): Что-то на первый взгляд очень странное, штраф за первую задачу всегда будет бесконечным, непонятно.

  • Минимизировать общее время всех активностей

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