1ridipi1

Эта статья находится в разработке!

Постановка задачи

Дан один станок на котором нужно выполнить [math]n[/math] работ. Для каждой работы известны моменты времени, когда можно начинать её выполнять - [math]r_{i}[/math] и когда необходимо закончить её выполнение - [math]d_{i}[/math]. Время выполнения [math]p_{i}[/math] у всех работ одинаково и равно 1. Необходимо узнать, можно ли построить хорошее расписание (при котором все работы будут выполнены).

Алгоритм

Идея алгоритма в том, чтобы из тех работ, которые уже можно выполнить, ставить в расписание ту, у которой наименьшее [math]d_{i}[/math]. Если эта работа уже просрочена, значит хорошее расписание построить нельзя.

Пусть [math]S[/math] - множество ещё не включенных в расписание работ, к выполнению которых уже можно приступить. Изначально [math]S[/math] пустое. Отсортируем работы по порядку их появления.

Алгоритм [math]1 | r_{i}, d_{i}, p_{i}=1 | -[/math]

    [math]S:=\varnothing;[/math]
    [math]j\leftarrow1;[/math]
    [math]time\leftarrow1;[/math]
    [math]FOR[/math]  [math]i := 1[/math] [math]TO[/math] [math]n[/math] [math]DO[/math]
         [math]BEGIN[/math]
         [math]IF[/math] [math]S=\varnothing[/math] [math]THEN[/math]
              [math]BEGIN[/math] [math]time:=r_{j}[/math] [math]END[/math]
         [math]WHILE[/math] [math]time=r_{j}[/math] [math]DO[/math]
              [math]BEGIN[/math]
              Добавить [math]j[/math] в [math]S[/math]
              [math]j:=j+1;[/math]
              [math]END[/math]
         Пусть [math]k\in S[/math] и [math]d_{k}[/math] минимально
         [math]IF[/math] [math]d_{k}\le time[/math] [math]THEN[/math]
              Расписание составить невозможно
         [math]ELSE[/math]
              [math]BEGIN[/math]
              Удалить [math]k[/math] из [math]S[/math]
              [math]time:=time+1;[/math]
              [math]END[/math]
         [math]END[/math]

Сложность алгоритма [math]O(n\log n)[/math] если в качестве [math]S[/math] использовать структуру, которая позволяет поиск элемента с минимальным [math]d_{i}[/math] за [math]O(\log n)[/math].

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

Пусть с помощью нашего алгоритма составить хорошее расписание не удалось. Докажем, что в этом случае хорошего расписания не существует. Заметим, что расписание состоит из временных блоков, между которыми есть пропуски - все поступившие работы выполнены, а новые работ ещё не появилось. Расписание может состоять из одного блока.

Рассмотрим первый блок, для которого не получилось составить расписание. Возьмем первую работу, для которой не нашлось места. Пусть её индекс будет [math]k[/math]. Попробуем вставить эту работу в расписание. До блока её вставить нельзя, так как [math]r_{i}[/math] больше или равно началу блока. А в блоке нет пропусков, поэтому нужно поменять её с какой-то [math]i-[/math]ой, которая уже стоит в этом блоке расписания. У всех таких работ [math]d_{i}[/math] меньше или равно [math]d_{k}[/math], так как в алгоритме мы каждый раз брали работу с минимальным [math]d_{i}[/math]. Значит мы не можем поменять [math]i[/math]-ую и [math]k[/math]-ую работы, так как [math]i[/math]-ую нельзя выполнить после [math]k[/math]-ой. Значит [math]k[/math]-ую работу выполнить нельзя.

Литература

• Peter Brucker. «Scheduling Algorithms» — «Springer», 2006 г. — 379 стр. — ISBN 978-3-540-69515-8