Изменения

Допустим, у нас <tex>n</tex> работ и <tex>m</tex> машин. В начальный момент времени мы можем начать обрабатывать любую работу на первой машине. В следующий момент на первом первой машине можно обрабатывать следующую работу, а на второй перейдёт предыдущая работа с первой машины, и так далее. Таким образом, на выполнение всех работ у нас уйдёт <tex>n + m - 1</tex> единиц времени. Проиллюстрируем это диаграммой Гантта Ганта для случая <tex>n = 6, m = 5</tex>: (по горизонтали время, по вертикали машины, в ячейке — номер выполняемой работы)

Алгоритм такой: возьмём два пустых списка. Будем рассматривать работы в порядке возрастания <tex>min(p_1, p_2)</tex>, то есть , минимума из времён выполнения данной работы на первой и второй машине. Если у работы <tex>p_1 <= p_2</tex>, то добавим её в конец первого списка. В противном случае , добавим её в начало второго списка. Итоговое расписание — это конкатенация первого и второго списков.