228
правок
Изменения
Новая страница: «<div style="background-color: #ABCDEF; font-size: 16px; font-weight: bold; color: #000000; text-align: center; padding: 4px; border-style: solid; border-width: 1p...»
<div style="background-color: #ABCDEF; font-size: 16px; font-weight: bold; color: #000000; text-align: center; padding: 4px; border-style: solid; border-width: 1px;">Эта статья находится в разработке!</div>
<includeonly>[[Категория: В разработке]]</includeonly>
Классификация задач
нотация Грэхема
a|b|c
a - тип обработки
b - характерстика работ
с - критерий оптимизации
==Диаграммы Гантта==
Пусть работы <tex> J_i (i = 1,..,n) </tex> должны быть выполнены на машинах <tex> M_i (i = 1,..,n) </tex>.
{{Определение
|definition =
'''Расписанием''' называется соответствие между каждой работой и одним или более интервалов времени на одной или более машине, на которой эта работа выполняется.
}}
'''Диаграмма Гантта''' <tex>{-}</tex> способ представления расписания.
===Пример===
'''вставь картинку'''
==Нотация Грэхема==
Чтобы описать задачу на теорию расписаний требуется указать три поля.
<tex> \alpha | \beta | \gamma </tex>. При этом
==Характеристика работ==
<tex> \beta_1 {-}</tex> pmtn(premtion) - возможность остановить работу и продолжить ее позже. Работа может быть прервана несколько раз.
<tex> \beta_2 {-}</tex> precedence - работа может начаться только после завершения каких-то других работ. b2 удобно задавать графом.
prec - ациклический направленный граф, соответственно ребро (i, j), будет если j может начаться только после окончания i.
'''write about intree outtree '''
<tex> \beta_3 {-}</tex> означает, что работы появляются в определенное время (release time), задается множеством <tex> r_i </tex>.
<tex> \beta_4 {-}</tex> время, которое нужно затратить станку на выполнение работы, задается множеством <tex> p_i </tex>.
<tex> \beta_5 {-}</tex> дедлайны на работы, время к которому работы должны быть закончены, задается множеством <tex> d_i </tex>.
<tex> \beta_6 {-}</tex> условие на пакеты. Означает, что некоторые работ объединены в группу, которая должна быть выполнена на одной машине.
==Критерии оптимизации==
<tex> C_i </tex> время окончания работы
<tex> L_i = C_i - d_i </tex>
<tex> T_i = max0, C_i - d_i</tex> '''Найти аккуратные максимум'''
<tex> U_i = </tex>
<tex> \Bigg\{
\begin{matrix}
1,c_i > d_i \\
0, c_i < p_i\\
\end{matrix}
</tex>
f_i(C_i) монотонно неубывающая функция f_max = max f_i
==Тип обработки==
<tex> P_m {-}</tex> несколько одинаковых станков
<tex> Q_m {-}</tex> разные, но однородные станки(отличаются скорость).
<tex> R_m {-}</tex> разные произвольные станки.
<includeonly>[[Категория: В разработке]]</includeonly>
Классификация задач
нотация Грэхема
a|b|c
a - тип обработки
b - характерстика работ
с - критерий оптимизации
==Диаграммы Гантта==
Пусть работы <tex> J_i (i = 1,..,n) </tex> должны быть выполнены на машинах <tex> M_i (i = 1,..,n) </tex>.
{{Определение
|definition =
'''Расписанием''' называется соответствие между каждой работой и одним или более интервалов времени на одной или более машине, на которой эта работа выполняется.
}}
'''Диаграмма Гантта''' <tex>{-}</tex> способ представления расписания.
===Пример===
'''вставь картинку'''
==Нотация Грэхема==
Чтобы описать задачу на теорию расписаний требуется указать три поля.
<tex> \alpha | \beta | \gamma </tex>. При этом
==Характеристика работ==
<tex> \beta_1 {-}</tex> pmtn(premtion) - возможность остановить работу и продолжить ее позже. Работа может быть прервана несколько раз.
<tex> \beta_2 {-}</tex> precedence - работа может начаться только после завершения каких-то других работ. b2 удобно задавать графом.
prec - ациклический направленный граф, соответственно ребро (i, j), будет если j может начаться только после окончания i.
'''write about intree outtree '''
<tex> \beta_3 {-}</tex> означает, что работы появляются в определенное время (release time), задается множеством <tex> r_i </tex>.
<tex> \beta_4 {-}</tex> время, которое нужно затратить станку на выполнение работы, задается множеством <tex> p_i </tex>.
<tex> \beta_5 {-}</tex> дедлайны на работы, время к которому работы должны быть закончены, задается множеством <tex> d_i </tex>.
<tex> \beta_6 {-}</tex> условие на пакеты. Означает, что некоторые работ объединены в группу, которая должна быть выполнена на одной машине.
==Критерии оптимизации==
<tex> C_i </tex> время окончания работы
<tex> L_i = C_i - d_i </tex>
<tex> T_i = max0, C_i - d_i</tex> '''Найти аккуратные максимум'''
<tex> U_i = </tex>
<tex> \Bigg\{
\begin{matrix}
1,c_i > d_i \\
0, c_i < p_i\\
\end{matrix}
</tex>
f_i(C_i) монотонно неубывающая функция f_max = max f_i
==Тип обработки==
<tex> P_m {-}</tex> несколько одинаковых станков
<tex> Q_m {-}</tex> разные, но однородные станки(отличаются скорость).
<tex> R_m {-}</tex> разные произвольные станки.
