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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Новая страница: «<tex dpi = "200"> P \mid p_i=1; r_i - integer \mid L_{max} </tex> {{Задача |definition= Дано <tex>m</tex> однородных станков, рабо...»)
 
м (Псевдокод)
(не показано 5 промежуточных версий 3 участников)
Строка 2: Строка 2:
 
{{Задача
 
{{Задача
 
|definition=
 
|definition=
Дано <tex>m</tex> однородных станков, работающих параллельно, и <tex>n</tex> работ с временем выполнения <tex>p_i = 1</tex> и временем появления <tex>r_i</tex>, заданным целым числом. Необходимо построить такое расписание, чтобы значение максимального опоздания <tex>L_{max} = \max\limits_{i=1\ldots n} (C_i - d_i)</tex> было минимальным.
+
Дано <tex>m</tex> однородных станков, работающих параллельно, и <tex>n</tex> работ с временем выполнения <tex>p_i = 1</tex>, временем появления <tex>r_i</tex>, заданным целым числом, и моментом времени <tex>d_i</tex>, к которому нужно выполнить работу. Необходимо построить такое расписание, чтобы значение максимального опоздания <tex>L_{max} = \max\limits_{i=1 \ldots n} (C_i - d_i)</tex> было минимальным.
 
}}
 
}}
 +
== Описание алгоритма ==
 +
=== Идея ===
 +
Отсортируем все работы по времени появления в неубывающем порядке так, что <tex>r_1 \leqslant r_2 \leqslant  \ldots  \leqslant r_n</tex>. Теперь будем выполнять доступные на данный момент работы в порядке неубывания дедлайнов <tex>d_i</tex>. То есть, если в момент времени <tex>t</tex> есть свободные станки и есть невыполненные работы такие, что <tex>r_i \leqslant t</tex>, то назначаем работу с наименьшим дедлайном <tex>d_i</tex> на свободный станок.
 +
 +
=== Псевдокод ===
 +
Алгоритм принимает на вход массив пар, где первый элемент является временем появления <tex>r_i</tex> работы, а второй её дедлайном <tex>d_i</tex>, и возвращает расписание, представленное массивом, где на позиции <tex>i</tex> стоит момент обработки работы <tex>i</tex>.
 +
 +
'''function''' scheduling(jobs: '''<int, int>[n]''') -> '''int[n]'''
 +
    sort(jobs) <font color=green>// сортируем работы в порядке неубывания времени появления</font>
 +
    '''int''' j = 1 <font color=green>// последняя невыполненная работа</font>
 +
    '''int[n]''' ans <font color=green>// массив, куда будет записано расписание</font>
 +
    '''Heap<int>''' M <font color=green>// [[Двоичная куча|куча]], в которой будем хранить доступные на данный момент работы в порядке неубывания дедлайнов</font>
 +
    '''while''' j <= n
 +
        '''int''' time = jobs[j].first <font color=green>// время начала выполнения текущего блока работ</font>
 +
        '''while''' jobs[j].first <= time <font color=green>// добавляем в кучу все невыполненные работы, доступные на данный момент</font>
 +
            M.push(j)
 +
            j++
 +
       
 +
        '''int''' k = 0 <font color=green>// количество занятых станков в данный момент времени</font>
 +
        '''while''' M.notEmpty
 +
            i = M.pop() <font color=green>// получаем доступную работу с наименьшим дедлайном </font>
 +
            ans[i] = t <font color=green>// назначаем работу i на время t</font>
 +
            '''if''' k + 1 < m <font color=green>// если в момент t есть свободный станок, то назначаем работу i на него</font>
 +
                k++
 +
            '''else''' <font color=green>// иначе увеличиваем время и обновляем список доступных работ</font>
 +
                t++
 +
                k = 0
 +
                '''while''' jobs[j].first <= time
 +
                    M.push(j)
 +
                    j++
 +
 +
[[Файл:Ppi1riintegerLmax bad.png|320px|thumb|right|Пример работы алгоритма при вещественных <tex>r_i</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>r_i</tex> и позволить им принимать вещественные значения, то представленный алгоритм перестанет строить оптимальное расписание, как видно из контрпримера.
 +
 +
== Доказательство корректности алгоритма ==
 +
{{Теорема
 +
|statement=
 +
Приведенный алгоритм строит оптимальное расписание для задачи <tex> P \mid p_i=1; r_i - integer \mid L_{max} </tex>.
 +
|proof=
 +
Пусть <tex>S</tex> {{---}} расписание построенное предложенным алгоритмом, а <tex>S^*</tex> оптимальное расписание со следующими свойствами:
 +
* первые <tex>r-1</tex> работ из <tex>S</tex> в обоих расписаниях назначены на одно и тоже время и
 +
* значение <tex>r-1</tex> {{---}} наибольшее.
 +
Таким образом работа <tex>J_r</tex> в расписании <tex>S</tex> назначена на время <tex>t</tex>, а в расписании <tex>S^*</tex> на другой более поздний момент времени. Если в момент времени <tex>t</tex> в расписании <tex>S^*</tex> есть свободный станок, то работа <tex>J_r</tex> может быть назначена на этот станок и выполнена в момент <tex>t</tex>. Иначе существует работа <tex>J_k</tex> такая, что <tex>d_r \leqslant d_k</tex>, которая выполнится в расписании <tex>S^*</tex> в момент <tex>t</tex>, а в <tex>S</tex> в другое время. Тогда мы меняем местами работы <tex>J_k</tex> и <tex>J_r</tex> в расписании <tex>S^*</tex>, что не нарушает оптимальность <tex>S^*</tex>, но является противоречием максимальности значения <tex>r-1</tex>.
 +
}}
 +
 +
== См. также ==
 +
* [[Pintreepi1Lmax|<tex>P \mid intree, p_{i} = 1 \mid L_{max}</tex>]]
 +
* [[PpmtnriLmax|<tex>P \mid pmtn, r_i \mid L_{max}</tex>]]
 +
 +
== Источники информации ==
 +
* Peter Brucker «Scheduling Algorithms», fifth edition, Springer {{---}} с. 111-112 ISBN 978-3-540-69515-8
 +
 +
[[Категория: Алгоритмы и структуры данных]]
 +
[[Категория: Теория расписаний]]

Версия 23:31, 4 июня 2016

[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