J2pij1Lmax — различия между версиями
Shersh (обсуждение | вклад) м (→Асимптотика) |
м (rollbackEdits.php mass rollback) |
(не показана 1 промежуточная версия 1 участника) | |
(нет различий)
|
Текущая версия на 19:05, 4 сентября 2022
Задача: |
Дано | работ и две машины, обозначенные как и . -тая работа состоит из операций , которые должны быть выполнены последовательно и, при этом, если операция была совершена на машине , то операция должна быть совершена на машине . Задача заключается в том, что для данного каждой -той работе дедлайна необходимо найти достижимое расписание с наименьшими максимальным временем опоздания: .
Необходимо отметить, что рассматриваемая задача более узкая, чем следует из ее названия по нотации Грэхема: машины в последовательности операций должны чередоваться.
Описание задачи
Из условия следует, что
-тая работа может характеризоваться двумя значениями: числом операций и машиной, на которой была совершена первая операция. Пусть — общее количество операций.Допустим, самым ранним моментом, когда операция может начать выполняться, будет момент времени
, а верхнюю границу момента начала выполнения последней операции обозначим за . К примеру, мы можем выбрать . Тогда расписание можно представить как два списка и , где , если операция должна выполниться на машине в момент времени и , если машина простаивает в этот момент. И для каждой операции , выполняющейся на машине существует , для которого . Аналогично для . Расписание достижимо тогда и только тогда, когда из следует для некоторого , и первая операция для каждой работы запланирована на нужной машине. Обозначим некоторую перестановку операций за . Для данного осуществимое расписание может быть создано следующим способом: планируем выполнять операции в порядке, соответствующем , причем каждую операцию стараемся выполнить как можно раньше. Подобное расписание будем называть соответствующим расписанием.— время окончания работы в достижимом расписании можно рассчитать как:
или — операция -той работы.
Задача заключается в том, что для данного каждой работе
дедлайна нужно найти достижимое расписание с наименьшим максимальным временем опоздания:
Описание алгоритма
Для решения задачи применим следующий алгоритм:
- введём для каждой операции величину — максимальное время завершения , при котором работа будет завершена не позднее дедлайна, при условии, что остальные операции выполняются без задержек вслед за ней,
- создадим список всех операций , упорядоченный в порядке неубывания значений ,
- найдем соответствующее списку расписание.
Этот алгоритм может быть реализован с асимптотикой
.Предположим, что
для и хотя бы для одной работы : . Иначе, вычтем из всех минимальное значение по .Заметим, что
: и : . Поэтому как минимум для одной работы . К тому же, можно предположить, что . Таким образом, работы с , то есть c , можно смело игнорировать. Они не влияют на значение улучшаемой функции , так как для некого : можно выполнять эти работы в любом порядке после всех остальных. Для оставшихся операций мы имеем:
Для того, чтобы найти расписание, соответствующее списку всех операций
, выполним следующие шаги:- на первом шаге каждую операцию кладём в соответствующий список , где ;
- на втором шаге планируем операции соответственно возрастающему по номеру списка порядку, где операции из одного списка могут выполнятся в произвольном порядке.
Алгоритм
Рассмотрим алгоритм. Пусть:
- и — первый период времени , когда соответствующие машины и бездействуют;
- — время окончания последней запланированной операции -той работы;
- — множество работ, где .
function solve(): // Шаг 1 // Инициализируем L и Z for k = -r + 1 to r - 1= Z = for i = 1 to n if < r for j = 1 to добавить в else добавить работу i в Z for i = 1 to n LAST[i] = 0 T1 = 0 T2 = 0 // Шаг 2 // Планируем операции соответственно возрастающему по номеру списка порядку for k = -r + 1 to r - 1 while Выбрать задание из = schedule( ) // Планируем операции, соответствующие работам с while Выбрать работу i из Z Z = ; for j = 1 to schedule( )
function schedule(): t = 0 if == A if T1 < LAST[i] t = LAST[i] A(t) = // else t = T1 A(t) = while T1 = T1 + 1 else if T2 < LAST[i] t = LAST[i] B(t) = // else t = T2 A(t) = while T2 = T2 + 1 LAST[i] = t + 1
Асимптотика
Суммарное количество операций равно
. Первый шаг алгоритма занимает , так как каждая операция добавляется либо в , либо в . На втором шаге каждая операция назначается единожды, то есть на втором шаге также выполняется действий. И, наконец, суммарное время всех вызовов функции также равно , так как суммарное количество итераций циклов внутри этой функции не превышает . Итого, время работы алгоритма .Доказательство
Для доказательства того, что алгоритм решения задачи корректен, необходимо показать то, что он строит достижимое расписание. Это справедливо тогда и только тогда, когда до исполнения строчек
и пусты и соответственно. Иначе две разные операции будут выполняться в один момент времени на одной машине. Для того, чтобы показать достижимость докажем лемму.Лемма: |
Пусть — расписание, где . Тогда для каждого , где выполняется |
Доказательство: |
Докажем по индукции по Предположим теперь что лемма верна для всех , что если и , то . Это, очевидно, верно при так как если и не соответствует работе , то означает что операция должна быть запланирована в расписании ранее. при и . Выберем максимальное , такое что и . По предположению индукции, и соответствуют одной и той же работе для . Пусть ) не соответствует работе . Тогда для каждого операция не соответствует работе . Таким образом, может быть обработан в момент , что противоречит тому, что является расписанием. |
Теорема: |
Пусть — операция, которую планируют строчкой (*) или (**) и . Тогда |
Доказательство: |
Предположим что | . Поскольку , из предыдущей леммы следует, что и и являются операциями одной и той же задачи . Так как , то должно быть значение . Это невозможно, т.к. при и , .
Лемма: |
Если существует расписание без опозданий, то данный алгоритм построит расписание без опозданий. |
Доказательство: |
Покажем, что если в расписании, построенном данным алгоритмом есть опоздание, то опоздание есть в каждом расписании. Если есть опоздание в , то существует операция или с или . Например, это неравенство верно для последней операции в конце работы. Выберем минимальное с этим свойством и предположим, что . Тогда мы докажем, что и . Таким образом, в каждом расписании должно существовать, по крайней мере, одно опоздание, т.к. если то при и мы должны запланировать операций во временном интервале , что невозможно. Если же , то все задачи начинаются на машине и операций должны обрабатываться в интервале времени , что тоже не возможно. Для доказательства заметим, что (***) верно, если является первой операцией для работы, так как если при некоторых , то алгоритм должен запланировать перед . Теперь положим для какого-нибудь и . Получим при , так как из следует , а это противоречит минимальности . Из этого следует, что при так как в противном случае должно быть запланировано ранее. Также поскольку в противном случае должно быть запланировано на время , так как и являются операциями различных задач. Для мы доказали (***). Иначе пусть . Если — первая операция задачи, мы закончили. В противном случае, если при , мы снова имеемЕсли . , тогда возьмем минимальное такое, что и являются последовательными операциями одной и той же задачи при . не соответствует задаче , и мы снова имеем .Если , мы закончили. Если , продолжаем таким же образом. |
Теорема: |
Расписание, построенное данным алгоритмом, оптимально. |
Доказательство: |
Пусть По первой лемме, данный алгоритм применительно к задаче с дедлайнами — максимальное опоздание оптимального расписания. Тогда эквивалентно . дает оптимальное расписание для исходной задаче. Кроме того, это расписание совпадает с расписанием, которое мы получим, применив данный алгоритм к исходной задаче. |
См. также.
Источники информации
- Peter Brucker. «Scheduling Algorithms» — «Springer», 2006 г. — 180 — 186 стр. — ISBN 978-3-540-69515-8