Изменения
Новая страница: «==Описание задачи== Дано <tex>m</tex> станков, на которых нужно обработать <tex>n</tex> деталей. Кажд...»
==Описание задачи==
Дано <tex>m</tex> станков, на которых нужно обработать <tex>n</tex> деталей. Каждую деталь нужно обработать по очереди на всех станках. Любая работа на любом станке выполняется единицу времени. Для каждой работы есть дедлайн <tex>d_i</tex> {{---}} время, до которого она должна быть закончена, и штраф <tex>w_i</tex>, который нужно будет выплатить в случае, если работа была закончена после <tex>d_i</tex>. Необходимо минимизировать суммарный штраф, который придется выплатить.
==Описание алгоритма==
{{Утверждение
|statement=Существует оптимальное расписание, в котором каждая работа делается непрерывно.
|proof=
Рассмотрим расписание, в котором есть работы, которые делаются не непрерывно. Рассмотрим самый ранний разрыв: работа <tex>i</tex> делалась в моменты <tex>t(i), t(i)+1, \ldots, t(i)+k</tex>, где <tex>k<m</tex>, но не делалась в момент времени <tex>t(i)+k+1</tex>. Докажем, что в момент времени <tex>t(i)+k+1</tex>, <tex>k+1</tex>-й станок простаивает и можно продолжить делать <tex>i</tex>-ю работу.
Пусть в момент времени <tex>t(i)+k+1</tex> на <tex>k+1</tex>-м станке делается работа <tex>j</tex>.
В <tex>t(i)+k</tex>-й момент времени <tex>k</tex>-й станок был занят выполнением <tex>i</tex>-й работы, а значит, не мог выполнять <tex>j</tex>-ю. Значит, разрыв был раньше, что противоречит тому, что был выбран самый ранний разрыв. Значит, в <tex>t(i)+k+1</tex>-й момент <tex>k+1</tex>-й станок свободен и туда можно поставить <tex>i</tex>-ю работу, устранив разрыв.
После устранения каждого разрыва получим расписание без разрывов, в котором каждая работа заканчивает выполняться не позже, чем в изначальном.
}}
Дано <tex>m</tex> станков, на которых нужно обработать <tex>n</tex> деталей. Каждую деталь нужно обработать по очереди на всех станках. Любая работа на любом станке выполняется единицу времени. Для каждой работы есть дедлайн <tex>d_i</tex> {{---}} время, до которого она должна быть закончена, и штраф <tex>w_i</tex>, который нужно будет выплатить в случае, если работа была закончена после <tex>d_i</tex>. Необходимо минимизировать суммарный штраф, который придется выплатить.
==Описание алгоритма==
{{Утверждение
|statement=Существует оптимальное расписание, в котором каждая работа делается непрерывно.
|proof=
Рассмотрим расписание, в котором есть работы, которые делаются не непрерывно. Рассмотрим самый ранний разрыв: работа <tex>i</tex> делалась в моменты <tex>t(i), t(i)+1, \ldots, t(i)+k</tex>, где <tex>k<m</tex>, но не делалась в момент времени <tex>t(i)+k+1</tex>. Докажем, что в момент времени <tex>t(i)+k+1</tex>, <tex>k+1</tex>-й станок простаивает и можно продолжить делать <tex>i</tex>-ю работу.
Пусть в момент времени <tex>t(i)+k+1</tex> на <tex>k+1</tex>-м станке делается работа <tex>j</tex>.
В <tex>t(i)+k</tex>-й момент времени <tex>k</tex>-й станок был занят выполнением <tex>i</tex>-й работы, а значит, не мог выполнять <tex>j</tex>-ю. Значит, разрыв был раньше, что противоречит тому, что был выбран самый ранний разрыв. Значит, в <tex>t(i)+k+1</tex>-й момент <tex>k+1</tex>-й станок свободен и туда можно поставить <tex>i</tex>-ю работу, устранив разрыв.
После устранения каждого разрыва получим расписание без разрывов, в котором каждая работа заканчивает выполняться не позже, чем в изначальном.
}}
