J2pij1Lmax

Эта статья находится в разработке!

Дано n работ i = 1,...,n и две машины, обозначенные как A и B. i-тая работа состоит из n_i операций O_{ij} (j = 1,..n_i), которые должны быть выполнены последовательно и, при этом, если O_{ij} операция была совершена на машине A (B), то операция O_{i,j-1} должна быть совершена на машине B (A). Таким образом, i-тая работа может характеризоваться двумя значениями: количество операций n_i и машина, на которой была совершена первая операция. Пусть r = \Sum(i=1..n) N_i — общее количество операций.

Допустим, самым ранним моментом, когда операция может начать выполняться, будет момент времени 0, а верхняя граница момента начала выполнения последней операции обозначим за t_{max}. К примеру, мы можем выбрать t_{max} = r. Тогда расписание можно представить как два массива A(t) и B(t) (t = 0,...,t_{max}), где A(t) = O_ij, если операция O_ij должна выполниться на машине A в момент времени t и A(t) = (пусто), если машина A простаивает в этот момент. Будем называть (пусто) пустой операцией. И для каждой операции O_ij, выполняющейся на машине A существует t, для которого A(t) = O_ij. Аналогично для B_i. Расписание достижимо тогда и только тогда, когда из A(t) (B(t)) = O_{ij} , 1 < j \le n_i следует O_{i,j-1} = B(s) (A(s)) для некоторого s < t, и первая операция для каждой работы запланирована на нужной машине. Перестановку всех операций будем называть списком. Для данный списка L осуществимое расписание может быть создано следующим способом: планируем выполнять операции в порядке, соответствующим L, причем каждую операцию стараемся выполнить как можно раньше. Подобное расписание будем называть соответствующим L расписанием. С_i — время окончания работы i в достижимом расписании y = (A(t), B(t)) можно рассчитать как:

C_i = max{t + 1 | A(t) или B(t) — операция i-той работы}

Задача заключается в том, что для данного каждой работе i дедлайна d_i \ge 0 мы хотим найти достижимое расписание с наименьшими максимальным временем опоздания:

max{C_i - d_i | i = 1, ..., n}

Следующий алгоритм решает эту задачу:

 * Введём для каждой операции [math]O_{ij}[/math] величину [math]l(O_{ij}) = d_i - n_i + j[/math]
 * Создадим список всех операций L, упорядоченный в порядке неубывания значений l(O_{ij}) 
 * Найдем соответствующее списку L расписание.

Этот алгоритм может быть реализованным с асимптотикой [math]O(r \log r)[/math]. Однако, мы будем использовать эвристику с хешами и улучшим асимптотику алгоритма до [math]O(r)[/math].