48
правок
Изменения
Нет описания правки
=== Псевдокод ===
Алгоритм принимает на вход два массива {{---}} массив с количеством обработки нужным для каждой работы объемами работ и массив скоростей обработки станков, и возвращает массив длинной <tex>m</tex>, в котором на <tex>i</tex>-ой позиции содержится расписание для <tex>i</tex>-ого станка, представляющей собой вектор троекчетвёрок, где первый элемент является номером станка, второй {{---}} номером работы, а два оставшихся время начала и окончания обработки этой работы на этом станке. '''function''' scheduling(p: '''Arrayint'''[intn], v: '''Arrayint'''[intn]) -> '''Array[Vector[(vector<int, int, int, int)]]>'''
'''int''' time = 0 <font color=green>// текущее время на всех станках</font>
'''Array[Vector[(int, vector<int, int)]]''' ans = new '''Array[Vector[(int, int, int)]]>'''(m) ans <font color=green> // массив длинной mвектор, куда будет записан ответ</font>
sort(p) <font color=green>// сортируем времена обработки работ в невозрастающем порядке</font>
sort(v) <font color=green>// сортируем скорости обработки станков в невозрастающем порядке</font>
'''int''' dt = p[i] / v[1] <font color=green>// время обработки самой короткой доступной задачи на самом быстром станке</font>
'''for''' j = i '''downto''' k = max(1, i - m + 1)
ans[.push(1 + i - j].push(, j, time, time + dt) <font color=green>// Назначаем работу j на станок <tex>M_{1+i-j}</tex> работу j на время от time до time + dt</font>
p[j] = p[j] - dt * v[1 + i - j] <font color=green>// уменьшаем количество обработки, оставшейся для j-ой работы</font>
time = time + dt <font color=green>// обновляем текущее время</font>
