Ppi1riintegerLmax — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
м
м (rollbackEdits.php mass rollback)
 
(не показаны 3 промежуточные версии 3 участников)
Строка 11: Строка 11:
 
Алгоритм принимает на вход массив пар, где первый элемент является временем появления <tex>r_i</tex> работы, а второй её дедлайном <tex>d_i</tex>, и возвращает расписание, представленное массивом, где на позиции <tex>i</tex> стоит момент обработки работы <tex>i</tex>.
 
Алгоритм принимает на вход массив пар, где первый элемент является временем появления <tex>r_i</tex> работы, а второй её дедлайном <tex>d_i</tex>, и возвращает расписание, представленное массивом, где на позиции <tex>i</tex> стоит момент обработки работы <tex>i</tex>.
  
  '''function''' scheduling(jobs: '''<int, int>'''[n]) -> '''int[n]'''
+
  '''function''' scheduling(jobs: '''<int, int>[n]''') -> '''int[n]'''
 
     sort(jobs) <font color=green>// сортируем работы в порядке неубывания времени появления</font>
 
     sort(jobs) <font color=green>// сортируем работы в порядке неубывания времени появления</font>
 
     '''int''' j = 1 <font color=green>// последняя невыполненная работа</font>
 
     '''int''' j = 1 <font color=green>// последняя невыполненная работа</font>
 
     '''int[n]''' ans <font color=green>// массив, куда будет записано расписание</font>
 
     '''int[n]''' ans <font color=green>// массив, куда будет записано расписание</font>
     '''heap''' M <font color=green>// куча, в которой будем хранить доступные на данный момент работы в порядке неубывания дедлайнов</font>
+
     '''Heap<int>''' M <font color=green>// [[Двоичная куча|куча]], в которой будем хранить доступные на данный момент работы в порядке неубывания дедлайнов</font>
 
     '''while''' j <= n
 
     '''while''' j <= n
 
         '''int''' time = jobs[j].first <font color=green>// время начала выполнения текущего блока работ</font>
 
         '''int''' time = jobs[j].first <font color=green>// время начала выполнения текущего блока работ</font>
Строка 23: Строка 23:
 
          
 
          
 
         '''int''' k = 0 <font color=green>// количество занятых станков в данный момент времени</font>
 
         '''int''' k = 0 <font color=green>// количество занятых станков в данный момент времени</font>
         '''while''' M.notEmpty()
+
         '''while''' M.notEmpty
 
             i = M.pop() <font color=green>// получаем доступную работу с наименьшим дедлайном </font>
 
             i = M.pop() <font color=green>// получаем доступную работу с наименьшим дедлайном </font>
 
             ans[i] = t <font color=green>// назначаем работу i на время t</font>
 
             ans[i] = t <font color=green>// назначаем работу i на время t</font>
Строка 36: Строка 36:
  
 
[[Файл:Ppi1riintegerLmax bad.png|320px|thumb|right|Пример работы алгоритма при вещественных <tex>r_i</tex>]]
 
[[Файл:Ppi1riintegerLmax bad.png|320px|thumb|right|Пример работы алгоритма при вещественных <tex>r_i</tex>]]
Внутренний цикл '''while''' распределяет работы блоками, в которых они выполняются без простоя станков. После окончания такого блока, время начала выполнения следующего будет равно текущему значению <tex>r_j</tex>.
+
Внутренний цикл <tex>\mathrm{while}</tex> распределяет работы блоками, в которых они выполняются без простоя станков. После окончания такого блока, время начала выполнения следующего будет равно текущему значению <tex>r_j</tex>.
 +
 
 
=== Асимптотика ===
 
=== Асимптотика ===
 
Сначала мы сортируем работы, что занимает <tex> \mathcal{O}(n\log{n})</tex>. Далее идёт цикл, в котором мы <tex>n</tex> раз кладём элемент в кучу и <tex>n</tex> раз извлекаем, что также занимает <tex> \mathcal{O}(n\log{n})</tex> времени. В итоге всё вместе составляет асимптотику алгоритма <tex> \mathcal{O}(n\log{n})</tex>.
 
Сначала мы сортируем работы, что занимает <tex> \mathcal{O}(n\log{n})</tex>. Далее идёт цикл, в котором мы <tex>n</tex> раз кладём элемент в кучу и <tex>n</tex> раз извлекаем, что также занимает <tex> \mathcal{O}(n\log{n})</tex> времени. В итоге всё вместе составляет асимптотику алгоритма <tex> \mathcal{O}(n\log{n})</tex>.

Текущая версия на 19:23, 4 сентября 2022

[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<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++
Пример работы алгоритма при вещественных [math]r_i[/math]

Внутренний цикл [math]\mathrm{while}[/math] распределяет работы блоками, в которых они выполняются без простоя станков. После окончания такого блока, время начала выполнения следующего будет равно текущему значению [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]

См. также

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

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