Fpij1sumwu — различия между версиями
(Новая страница: «==Описание задачи== Дано <tex>m</tex> станков, на которых нужно обработать <tex>n</tex> деталей. Кажд...») |
(нет различий)
|
Версия 15:06, 18 июня 2012
Описание задачи
Дано
станков, на которых нужно обработать деталей. Каждую деталь нужно обработать по очереди на всех станках. Любая работа на любом станке выполняется единицу времени. Для каждой работы есть дедлайн — время, до которого она должна быть закончена, и штраф , который нужно будет выплатить в случае, если работа была закончена после . Необходимо минимизировать суммарный штраф, который придется выплатить.Описание алгоритма
Утверждение: |
Существует оптимальное расписание, в котором каждая работа делается непрерывно. |
Рассмотрим расписание, в котором есть работы, которые делаются не непрерывно. Рассмотрим самый ранний разрыв: работа делалась в моменты , где , но не делалась в момент времени . Докажем, что в момент времени , -й станок простаивает и можно продолжить делать -ю работу.Пусть в момент времени После устранения каждого разрыва получим расписание без разрывов, в котором каждая работа заканчивает выполняться не позже, чем в изначальном. на -м станке делается работа . В -й момент времени -й станок был занят выполнением -й работы, а значит, не мог выполнять -ю. Значит, разрыв был раньше, что противоречит тому, что был выбран самый ранний разрыв. Значит, в -й момент -й станок свободен и туда можно поставить -ю работу, устранив разрыв. |