9
правок
Изменения
Нет описания правки
==Постановка задачи==
Дан один станок на котором нужно выполнить <tex>n</tex> работ. Для каждой работы известны моменты времени, когда можно начинать её выполнять - <tex>r_{i}</tex> и когда необходимо закончить её выполнение - <tex>d_{i}</tex>. Время выполнения <tex>p_{i}</tex> у всех работ одинаково и равно 1. Необходимо узнать, можно ли построить хорошее расписание (при котором все работы будут выполнены).
==Доказательство корректности алгоритма==
Пусть с помощью нашего алгоритма составить хорошее расписание не удалось. Докажем, что в этом случае хорошего расписания не существует.
Заметим, что расписание состоит из временных непрерывных блоков, между которыми есть пропуски - все поступившие работы выполнены, а новые новых работ ещё не появилось. Расписание может состоять из одного блока.
Рассмотрим первый блок, для которого не получилось составить расписание. Возьмем в нём первую работу, для которой не нашлось места. Пусть её индекс будет <tex>k</tex>. Попробуем вставить эту работу в расписание. До блока её вставить нельзя, так как <tex>r_{i}</tex> больше или равно началу времени начала блока. А в блоке нет пропусков, поэтому нужно поменять её с какой-то <tex>i-</tex>-ой, которая уже стоит в этом блоке расписания. У всех таких работ <tex>d_{i}</tex> меньше или равно <tex>d_{k}</tex>, так как в алгоритме мы каждый раз брали работу с минимальным <tex>d_{i}</tex>. Значит мы не можем поменять <tex>i</tex>-ую и <tex>k</tex>-ую работы, так как Но <tex>i</tex>-ую работу нельзя выполнить после <tex>k</tex>-ой. Значит <tex>k</tex>-ую работу выполнить нельзя.
==Литература==
* Peter Brucker. «Scheduling Algorithms» {{---}} «Springer», 2006 г. {{---}} 379 стр. {{---}} ISBN 978-3-540-69515-8
