Обсуждение участницы:Анна
Задача: |
Дано | одинаковых станков, которые работают параллельно, и работ, которые необходимо выполнить в произвольном порядке на всех станках. Любая работа на любом станке выполняется единицу времени. Для каждой работы есть время окончания — время, до которого она должна быть выполнена. Необходимо проверить, существует ли расписание, при котором все работы будут выполнены вовремя.
Содержание
Описание алгоритма
Идея
Заметим, что если
, то очевидно, что , следовательно, расписания не существует. Поэтому будем полагать, что для .Определим
— количество временных интервалов , где . Будем обозначать как . Для каждого из них мы можем назначить не более работ (по одной на каждый станок). Для каждой работы будем назначать времена обработки на каждой из машин следующим образом: на машине работа займет временной интервал , на машине — интервал и так далее, на машине работа займет временной интервал . В случае коллизий, то есть если найдется временной интервал , содержащий работу, возьмем минимальный такой и перенесем лишнюю работу из него на ту же машину, но на один временной интервал левее. Будем повторять этот процесс, пока необходимо (и пока ). Таким образом, только первый временной интервал может содержать более работ. Причем это может произойти тогда и только тогда, когда задача не имеет решения, то есть не существует расписания, при котором все работы будут выполнены вовремя.Псевдокод
Определим
— количество работ во временном интервале .void checkExistenceOfSchedule(int*): for to for to for to (1) while and (2) find if return true else return false
Замечание: если расписание существует, то оно может быть вычислено данным алгоритмом, если добавить в цикл (1) функцию, отвечающую за добавление работы
на момент в расписании для соответствующей машины и в цикл (2) функцию, отвечающую за перемещение работы, которой нет во временном интервале , но которая есть в , на момент в той же машине (этот шаг будет обоснован далее в доказательстве корректности).Асимптотика
Покажем, что данный алгоритм может быть реализован за время
Для начала рассмотрим следующий вопрос: пусть — множество работ, для которого существует расписание, в котором отсутствуют опаздывающие работы, пусть — работа, не принадлежащая , для которой выполняется неравенство для любой . Можно ли построить расписание для множества , в котором так же будут отсутствовать опаздывающие работы.
Введем несколько обозначений. Вектора , соответствующие множествам и обозначим как и соответственно. — количество временных интервалов со свойствами
- ,
- .
Будем говорить, что работы могут быть выполнены вовремя, если для них существует расписание, в котором эти работы успевают выполниться без опозданий.
Лемма: |
Пусть даны работы с дедлайнами , и . Тогда для всех работ , для которых , будет верно, что . |
Доказательство: |
Рассмотрим вектора | и после и итераций алгоритма. Заметим, что значения вектора , не превосходящие , то есть , никогда не уменьшаются. Следовательно, если и , то . Чтобы показать, что ситуация, когда при тех же условиях , невозможна, рассмотрим расписание, построенное алгоритмом.
Доказательство корректности
Теорема: |
Для множества работ с дедлайнами задача имеет решение тогда и только тогда, когда . |
Доказательство: |
|