Классификация задач

Эта статья находится в разработке!

Классификация задач нотация Грэхема a|b|c a - тип обработки b - характерстика работ с - критерий оптимизации

Диаграммы Гантта

Пусть работы [math] J_i (i = 1,..,n) [/math] должны быть выполнены на машинах [math] M_i (i = 1,..,n) [/math].

Определение:

Расписанием называется соответствие между каждой работой и одним или более интервалов времени на одной или более машине, на которой эта работа выполняется.

Диаграмма Гантта [math]{-}[/math] способ представления расписания.

Пример

вставь картинку

Нотация Грэхема

Чтобы описать задачу на теорию расписаний требуется указать три поля.

[math] \alpha | \beta | \gamma [/math]. При этом

Характеристика работ

[math] \beta_1 {-}[/math] pmtn(premtion) - возможность остановить работу и продолжить ее позже. Работа может быть прервана несколько раз.

[math] \beta_2 {-}[/math] precedence - работа может начаться только после завершения каких-то других работ. b2 удобно задавать графом. prec - ациклический направленный граф, соответственно ребро (i, j), будет если j может начаться только после окончания i. write about intree outtree

[math] \beta_3 {-}[/math] означает, что работы появляются в определенное время (release time), задается множеством [math] r_i [/math].

[math] \beta_4 {-}[/math] время, которое нужно затратить станку на выполнение работы, задается множеством [math] p_i [/math].

[math] \beta_5 {-}[/math] дедлайны на работы, время к которому работы должны быть закончены, задается множеством [math] d_i [/math].

[math] \beta_6 {-}[/math] условие на пакеты. Означает, что некоторые работ объединены в группу, которая должна быть выполнена на одной машине.

Критерии оптимизации

[math] C_i [/math] время окончания работы

[math] L_i = C_i - d_i [/math]

[math] T_i = max0, C_i - d_i[/math] Найти аккуратные максимум

[math] U_i = [/math] [math] \Bigg\{ \begin{matrix} 1,c_i \gt d_i \\ 0, c_i \lt p_i\\ \end{matrix} [/math]

f_i(C_i) монотонно неубывающая функция f_max = max f_i

Тип обработки

[math] P_m {-}[/math] несколько одинаковых станков

[math] Q_m {-}[/math] разные, но однородные станки(отличаются скорость).

[math] R_m {-}[/math] разные произвольные станки.