Ppi1riintegerLmax

[math] P \mid p_i=1; r_i - integer \mid L_{max} [/math]

Задача:

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

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

Идея

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

Псевдокод

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

function scheduling(jobs: <int, int>[n]) -> int[n]
    sort(jobs) // сортируем работы в порядке неубывания времени появления
    int j = 1 // последняя невыполненная работа
    int[n] ans // массив, куда будет записано расписание
    heap 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++

Пример работы алгоритма при вещественных [math]r_i[/math]

Внутренний цикл while распределяет работы блоками, в которых они выполняются без простоя станков. После окончания такого блока, время начала выполнения следующего будет равно текущему значению [math]r_j[/math].

Асимптотика

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

Замечание

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

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

Теорема:

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

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

[math]\triangleright[/math]

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

[math]\triangleleft[/math]

См. также

• [math]P \mid intree, p_{i} = 1 \mid L_{max}[/math]
• [math]P \mid pmtn, r_i \mid L_{max}[/math]

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

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