40
правок
Изменения
→Алгоритм построения расписания
==Алгоритм построения расписания==
Перед выполнением алгоритма, упорядочим все работы по убыванию их времени выполнеия:<tex> p_1 \ge p_2 \ge p_3... </tex>, а все машины в порядке убывания скоростей: <tex> s_1 \ge s_2 \ge s_3 ... </tex>. Введем следующие обозначения:
<tex> P_i = p_1 + ... + p_i</tex>
<tex> S_j = s_1 + ... + s_j</tex>
Необходимое условие для выполнения всех работ в интервале <tex>[0;..T]</tex>:
<tex> P_n = p_1 + ... + p_n \le s_1T + ... + s_mT = S_mT</tex> или <tex>P_n/S_m \le T</tex>
<tex>C_{max}</tex> = <tex>\max\{\max\limits_{j=1}^{m-1} {P_j \over S_j}, {P_n \over S_m}\}</tex>
Перейдем к описанию алгоритма. Будем назвать <tex>Level</tex>-ом работы <tex> p_i(t) </tex> - невыполненную часть работы <tex> p_i </tex> в момент времени <tex> t </tex>
Далее построим расписание, которое достигает нашей оценки <tex>C_{max}</tex>, с помощью <tex>Level</tex>-алгоритма.
'''WHILE''' существуют работы с положительным <tex>level</tex>
Assign(t)
<tex>t1 \leftarrow \min(s>t |</tex>находим следующую выполненную работу,где <tex> \mid s</tex> - время ее окончания какой-то работы <tex> ) </tex> <tex>t2 \leftarrow </tex> найти минимальное <tex>\min (s > t\mid </tex>. Для которого выполняется для некоторых работ <tex>i</tex> , <tex>j</tex>:<tex> level_ip_i(t)>level_jp_j(t)</tex> и <tex> level_ip_i(s) == level_jp_j(s))</tex> <tex> t \leftarrow \min(t1,t2) </tex> //поиск следующего момента времени ,в который нужно будет перераспределить машины/работы
Построение расписания
<tex>M = \{M_1,...,M_m\}</tex> - множество всех станков
'''WHILE''' множества <tex>J</tex> и <tex>M</tex> не пустые
Найти множество работ <tex>I</tex> подмножество <tex>\subset J</tex> ,<tex>level</tex> которых максимальныймаксимален.
<tex>r \leftarrow min</tex>(|<tex>M</tex>|,|<tex>I</tex>|)
Назначаем работы из множества <tex>I</tex> на <tex>r</tex> самых быстрых машин из множества <tex>M</tex>
<tex>J \leftarrow J</tex>\<tex>I</tex>
==Доказательство корректности алгоритма==
