Ppi1riintegerLmax

$P \mid p_i=1; r_i - integer \mid L_{max}$

Задача:

Дано $m$ однородных станков, работающих параллельно, и $n$ работ с временем выполнения $p_i = 1$, временем появления $r_i$, заданным целым числом, и моментом времени $d_i$, к которому нужно выполнить работу. Необходимо построить такое расписание, чтобы значение максимального опоздания $L_{max} = \max\limits_{i=1 \ldots n} (C_i - d_i)$ было минимальным.

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

Идея

Отсортируем все работы по времени появления в неубывающем порядке так, что $r_1 \leqslant r_2 \leqslant \ldots \leqslant r_n$. Теперь будем выполнять доступные на данный момент работы в порядке неубывания дедлайнов $d_i$. То есть, если в момент времени $t$ есть свободные станки и есть невыполненные работы такие, что $r_i \leqslant t$, то назначаем работу с наименьшим дедлайном $d_i$ на свободный станок.

Псевдокод

Алгоритм принимает на вход массив пар, где первый элемент является временем появления $r_i$ работы, а второй её дедлайном $d_i$, и возвращает расписание, представленное массивом, где на позиции $i$ стоит момент обработки работы $i$.

function scheduling(jobs: <int, int>[n]) -> int[n]
    sort(jobs) // сортируем работы в порядке неубывания времени появления
    int j = 1 // последняя невыполненная работа
    int[n] ans // массив, куда будет записано расписание
    Heap<int> M // куча, в которой будем хранить доступные на данный момент работы в порядке неубывания дедлайнов
    while j <= n
        int time = jobs[j].first // время начала выполнения текущего блока работ
        while jobs[j].first <= time // добавляем в кучу все невыполненные работы, доступные на данный момент
           M.push(j)
           j++
        
        int k = 0 // количество занятых станков в данный момент времени
        while M.notEmpty
           i = M.pop() // получаем доступную работу с наименьшим дедлайном 
           ans[i] = t // назначаем работу i на время t
           if k + 1 < m // если в момент t есть свободный станок, то назначаем работу i на него
               k++
           else // иначе увеличиваем время и обновляем список доступных работ
               t++
               k = 0
               while jobs[j].first <= time
                   M.push(j)
                   j++

Пример работы алгоритма при вещественных $r_i$

Внутренний цикл $\mathrm{while}$ распределяет работы блоками, в которых они выполняются без простоя станков. После окончания такого блока, время начала выполнения следующего будет равно текущему значению $r_j$.

Асимптотика

Сначала мы сортируем работы, что занимает $\mathcal{O}(n\log{n})$. Далее идёт цикл, в котором мы $n$ раз кладём элемент в кучу и $n$ раз извлекаем, что также занимает $\mathcal{O}(n\log{n})$ времени. В итоге всё вместе составляет асимптотику алгоритма $\mathcal{O}(n\log{n})$.

Замечание

Стоит отметить тот факт, что если снять ограничение на целочисленность $r_i$ и позволить им принимать вещественные значения, то представленный алгоритм перестанет строить оптимальное расписание, как видно из контрпримера.

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

Теорема:

Приведенный алгоритм строит оптимальное расписание для задачи $P \mid p_i=1; r_i - integer \mid L_{max}$.

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

$\triangleright$

Пусть $S$ — расписание построенное предложенным алгоритмом, а $S^*$ оптимальное расписание со следующими свойствами: первые $r-1$ работ из $S$ в обоих расписаниях назначены на одно и тоже время и значение $r-1$ — наибольшее. Таким образом работа $J_r$ в расписании $S$ назначена на время $t$, а в расписании $S^*$ на другой более поздний момент времени. Если в момент времени $t$ в расписании $S^*$ есть свободный станок, то работа $J_r$ может быть назначена на этот станок и выполнена в момент $t$. Иначе существует работа $J_k$ такая, что $d_r \leqslant d_k$, которая выполнится в расписании $S^*$ в момент $t$, а в $S$ в другое время. Тогда мы меняем местами работы $J_k$ и $J_r$ в расписании $S^*$, что не нарушает оптимальность $S^*$, но является противоречием максимальности значения $r-1$.

$\triangleleft$

См. также

• $P \mid intree, p_{i} = 1 \mid L_{max}$
• $P \mid pmtn, r_i \mid L_{max}$

Источники информации

• Peter Brucker «Scheduling Algorithms», fifth edition, Springer — с. 111-112 ISBN 978-3-540-69515-8