1ridipi1

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

Дан один станок на котором нужно выполнить $n$ работ. Для каждой работы известны моменты времени, когда можно начинать её выполнять — $r_{i}$ и когда необходимо закончить её выполнение — $d_{i}$. Время выполнения $p_{i}$ у всех работ одинаково и равно 1. Необходимо узнать, можно ли построить расписание, при котором все работы будут выполнены.

Алгоритм

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

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

Алгоритм $1 | r_{i}, d_{i}, p_{i}=1 | -$:

 $S = \varnothing;$
 $j = 1;$
 $time = 1;$
 for $i = 1$ to $n$:
     if $S == \varnothing$:
         $time=r_{j}$
     while $time==r_{j}$:
         $S \leftarrow S \cup \{j\}$
         $j = j + 1;$
     $d_{k} = min\{d_{i}$ | $i \in S\}$
     if $d_{k} \le time$:
         Расписание составить невозможно
     else:
         $S \leftarrow S \setminus \{k\}$
         $time = time + 1;$

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

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

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

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

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

• P. Brucker. Scheduling Algorithms (2006), 5th edition, стр. 200