QpmtnSumCi

[math] Q \mid pmtn \mid \sum C_i [/math]

Задача:

Дано [math]m[/math] станков с разной скоростью выполнения работ [math]v_j[/math] и [math]n[/math] работ с заданным временем выполнения [math]p_i[/math]. Работы можно прерывать и продолжать их выполнение на другом станке. Необходимо построить такое расписание, чтобы суммарное время окончания всех работ было минимальным.

Описание алгоритма

Пример работы алгоритма

Идея

Для решения применим правило SRPT-FM (Shortest Remaining Processing Time on Fastest Machine), которое предлагает класть работу с наименьшим оставшемся временем обработки на самый быстрый доступный станок. Отсортируем работы по времени обработки в невозрастающем порядке так, что [math]p_1 \ge p_2 \ge ... \ge p_n[/math]. Отсортируем станки по скорости обработки в невозрастающем порядке, так чтобы [math]v_1 \ge v_2 \ge ... \ge v_m[/math]. Далее назначаем [math]n[/math]-ю работу на станок [math]M_1[/math] (1-й по скорости станок) на время [math]t_1 = \cfrac{p_n}{v_1}[/math], то есть пока она полностью не выполнится. Теперь назначим [math]n-1[/math] работу сначала станок [math]M_2[/math] на время [math]t_1[/math], а затем на время от [math]t_1[/math] до [math]t_2 \ge t_1[/math] на станок [math]M_1[/math], пока она не завершится. С [math]n-2[/math] работой поступаем аналогично, сначала она [math]t_1[/math] времени выполняется на станке [math]M_3[/math], затем [math]t_2 - t_1[/math] времени на станке [math]M_2[/math], и, начиная с [math]t_2[/math] до [math]t_3 \ge t_2[/math], на станке [math]M_1[/math]. Также поступаем со всеми оставшимися работами.

Псевдокод

a = 0
p[] // массив времен обработки работ отсортированный в невозрастающем порядке
v[] // массив скоростей обработки станков отсортированный в невозрастающем порядке
while p[1] > 0
   Находим наибольший i такой, что p[i] > 0
   t = p[i] / v[1]
   for j = i down to k = max(1, i - m + 1)
       Назначаем работу j на станок [math]M_{1+i-j}[/math] на время от a до a + t
       p[j] = p[j] - t * v[1 + i - j]
   a = a + t

Сложность алгоритма составляет [math] \mathcal{O}(n\log{n} + mn)[/math].

Доказательство корректности алгоритма

Лемма:

Существует оптимальное расписание, в котором [math]C_j \le C_k[/math], когда [math]p_j \le p_k[/math], для всех [math]j[/math] и [math]k[/math]

Доказательство:

[math]\triangleright[/math]

Рассмотрим расписание [math]S[/math], где для некоторых [math]j[/math] и [math]k[/math] верно, что [math]C_j \gt C_k[/math], но [math]p_j \le p_k[/math]. С помощью обмена частей обработки, полученной работами [math]j[/math] и [math]k[/math], мы можем изменить расписание [math]S[/math], получив новое оптимальное расписание [math]S'[/math], где обработка работ [math]j[/math] и [math]k[/math] завершается во времена [math]C'_j \le C_k[/math] и [math]C'_k = C_j[/math] соответственно, при этом время завершения обработки остальных работ остается прежним. Тот факт, что в расписании [math]S'[/math] работа [math]j[/math] заканчивается раньше [math]k[/math], при этом не нарушая оптимальности расписания, свидетельствует о существовании расписания, описанного в условии леммы. Для построения расписания [math]S'[/math] из расписания [math]S[/math] введем следующие обозначения: [math]p^1_j[/math], [math]p^1_k[/math] — количество обработки, полученной одновременно [math]j[/math] и [math]k[/math], когда работа [math]j[/math] была на более быстром станке или обе работы были на одинаковых станках. [math]p^2_j[/math], [math]p^2_k[/math] — количество обработки, полученной одновременно [math]j[/math] и [math]k[/math], когда работа [math]k[/math] была на более быстром станке. [math]p^3_j[/math], [math]p^3_k[/math] — количество обработки, полученной [math]j[/math] и [math]k[/math] до момента [math]C_k[/math] на непересекающихся участках времени. [math]p^+_j[/math] — количество обработки, полученной [math]j[/math] после момента [math]C_k[/math]. Далее существуют два случая: Если [math]p^+_j \le p^3_k[/math], то расписание [math]S'[/math] получается обменом обработки, полученной [math]j[/math] после момента [math]C_k[/math] с частью обработки, полученной [math]k[/math] не одновременно с [math]j[/math]. Если [math]p^+_j \gt p^3_k[/math], то для начала обмениваем всю обработку [math]p^3_k[/math] с частью [math]p^+_j[/math], чтобы получить новое расписании, где [math]C'_k = C_j[/math] и [math]\tilde{p}^+_j = p^+_j - p^3_k[/math] обработки [math]j[/math] после момента [math]C_k[/math]. Пусть [math]p^2_j[/math] и [math]p^2_k[/math] представлены числом [math]T[/math] непересекающихся временных интервалов длинной [math]t_i[/math] с [math]v^i_j[/math], [math]v^i_k[/math] — скоростями станков, обрабатывающих [math]j[/math] и [math]k[/math] в интервал [math]i[/math] и [math]p^{2,i}_j = v^i_j \cdot t_i[/math], [math]p^{2,i}_k = v^i_k \cdot t_i[/math] — количество обработки, полученной соответвующей задачей за этот интервал. Так как [math]p^1_j \ge p^1_k[/math] и [math]p_j \le p_k[/math], то [math]p^2_j + \tilde{p}^+_j \le p^2_k[/math]. Следовательно существует такой [math]\tilde{p}^{+,i}_j[/math], что верно: [math]\sum\limits_{i=1}^{T}{\tilde{p}^{+,i}_j} = \tilde{p}^+_j[/math], [math]p^{2,i}_j + \tilde{p}^{+,i}_j \le p^{2,i}_k[/math], [math]i = 1...T[/math] Для каждого [math]i = 1...T[/math] пусть [math]t^i_j = \cfrac{\tilde{p}^{+,i}_j}{v^i_k - v^i_j}[/math], [math]t^i_k = t^i_j \cdot \cfrac{v^i_j}{v^i_k}[/math]. Чтобы получить расписание [math]S'[/math] для каждого из [math]T[/math] интервалов нужно обменять: 1) обработку, полученную в начале интервала работой [math]k[/math] на более быстром станке, с обработкой [math]j[/math], полученной на медленном станке, на интервалы [math]t^i_k[/math] и [math]t^i_j[/math] соответственно 2) обработку [math]\tilde{p}^{+,i}_j[/math], полученной [math]j[/math] после момента [math]C_k[/math], с таким же количеством обработки, полученной работой [math]k[/math] на более быстром станке в этот интервал сразу после момента [math]t^i_k[/math].

[math]\triangleleft[/math]

Теорема:

Расписание, построенное по принципу SRPT-FM, оптимальное для задачи [math] Q \mid pmtn \mid \sum C_i [/math]

Доказательство:

[math]\triangleright[/math]

В разработке

[math]\triangleleft[/math]