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