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++