Opij1di — различия между версиями
Анна (обсуждение | вклад) (Новая страница: «<tex dpi = "200"> O \mid p_{i,j} = 1, d_i \mid - </tex> {{Задача |definition= Дано <tex>m</tex> одинаковых станков, которые ра...») |
м (rollbackEdits.php mass rollback) |
||
(не показано 12 промежуточных версий 2 участников) | |||
Строка 6: | Строка 6: | ||
== Описание алгоритма == | == Описание алгоритма == | ||
=== Идея === | === Идея === | ||
− | + | {| class="wikitable" style="float:right; margin-left: 10px;" | |
+ | |- | ||
+ | ! | ||
+ | ! style="width:50px;"|<tex>t = 1</tex> | ||
+ | ! style="width:50px;"|<tex>2</tex> | ||
+ | ! style="width:30px;"|<tex>...</tex> | ||
+ | ! style="width:50px;"|<tex>d_i - m + 1</tex> | ||
+ | ! style="width:50px;"|<tex>d_i - m + 2</tex> | ||
+ | ! style="width:30px;"|<tex>...</tex> | ||
+ | ! style="width:50px;"|<tex>d_i - 1</tex> | ||
+ | ! style="width:50px;"|<tex>d_i</tex> | ||
+ | |- | ||
+ | ! style="width:50px;"|<tex>m = 1</tex> | ||
+ | | | ||
+ | | | ||
+ | | | ||
+ | | style="text-align:center;"|<tex>i</tex> | ||
+ | | | ||
+ | | | ||
+ | | | ||
+ | | | ||
+ | |- | ||
+ | ! style="width:50px;"|<tex>2</tex> | ||
+ | | | ||
+ | | | ||
+ | | | ||
+ | | | ||
+ | | style="text-align:center;"|<tex>i</tex> | ||
+ | | | ||
+ | | | ||
+ | | | ||
+ | |- | ||
+ | ! style="width:50px;"|<tex>\vdots</tex> | ||
+ | | | ||
+ | | | ||
+ | | | ||
+ | | | ||
+ | | | ||
+ | | style="text-align:center;"|<tex>\ddots</tex> | ||
+ | | | ||
+ | | | ||
+ | |- | ||
+ | ! style="width:50px;"|<tex>m - 1</tex> | ||
+ | | | ||
+ | | | ||
+ | | | ||
+ | | | ||
+ | | | ||
+ | | | ||
+ | | style="text-align:center;"|<tex>i</tex> | ||
+ | | | ||
+ | |- | ||
+ | ! style="width:50px;"|<tex>m</tex> | ||
+ | | | ||
+ | | | ||
+ | | | ||
+ | | | ||
+ | | | ||
+ | | | ||
+ | | | ||
+ | | style="text-align:center;"|<tex>i</tex> | ||
+ | |- | ||
+ | ! colspan="9"|Табл. 1. Работа <tex>i</tex> назначена на интервалы <tex>d_i - m + 1 \ldots d_i</tex>. | ||
+ | |} | ||
Заметим, что если <tex>d_i < m</tex>, то очевидно, что <tex>C_i > d_i</tex>, следовательно, расписания не существует. Поэтому будем полагать, что <tex>m \leqslant d_i</tex> для <tex>i = 1 \ldots n</tex>. | Заметим, что если <tex>d_i < m</tex>, то очевидно, что <tex>C_i > d_i</tex>, следовательно, расписания не существует. Поэтому будем полагать, что <tex>m \leqslant d_i</tex> для <tex>i = 1 \ldots n</tex>. | ||
Строка 14: | Строка 77: | ||
Определим <tex>h(t)</tex> {{---}} количество работ во временном интервале <tex>t</tex>. | Определим <tex>h(t)</tex> {{---}} количество работ во временном интервале <tex>t</tex>. | ||
− | '''void''' checkExistenceOfSchedule('''int''' | + | '''void''' checkExistenceOfSchedule('''int[]''' <tex>d</tex>): |
<tex>T = \max\{d_i \mid i = 1 \ldots n\}</tex> | <tex>T = \max\{d_i \mid i = 1 \ldots n\}</tex> | ||
'''for''' <tex>t = 1</tex> '''to''' <tex>T</tex> | '''for''' <tex>t = 1</tex> '''to''' <tex>T</tex> | ||
Строка 26: | Строка 89: | ||
<tex>h(k_0) = m</tex> | <tex>h(k_0) = m</tex> | ||
'''if''' <tex>h(1) \leqslant m</tex> | '''if''' <tex>h(1) \leqslant m</tex> | ||
− | '''return''' true | + | '''return''' ''true'' |
'''else''' | '''else''' | ||
− | '''return''' false | + | '''return''' ''false'' |
''Замечание:'' если расписание существует, то оно может быть вычислено данным алгоритмом, если добавить в цикл (1) функцию, отвечающую за добавление работы <tex>i</tex> на момент <tex>j</tex> в расписании для соответствующей машины и в цикл (2) функцию, отвечающую за перемещение работы, которой нет во временном интервале <tex>k_0 - 1</tex>, но которая есть в <tex>k_0</tex>, на момент <tex>k_0 - 1</tex> в той же машине (этот шаг будет обоснован далее в доказательстве корректности). | ''Замечание:'' если расписание существует, то оно может быть вычислено данным алгоритмом, если добавить в цикл (1) функцию, отвечающую за добавление работы <tex>i</tex> на момент <tex>j</tex> в расписании для соответствующей машины и в цикл (2) функцию, отвечающую за перемещение работы, которой нет во временном интервале <tex>k_0 - 1</tex>, но которая есть в <tex>k_0</tex>, на момент <tex>k_0 - 1</tex> в той же машине (этот шаг будет обоснован далее в доказательстве корректности). | ||
Строка 50: | Строка 113: | ||
|proof= | |proof= | ||
Неравенство (1) равносильно <tex>(d_i - m)m \geqslant \sum\limits_{t = 1}^{d_i - m}h^U(t) + m - x(d_i)</tex>. По лемме имеем <tex>\sum\limits_{j = d_i - m + 1}^{d_i}h^V(j) = \sum\limits_{j = d_i - m + 1}^{d_i}h^U(j) + x(d_i)</tex>. Вычитая это равенство из <tex>\sum\limits_{j = 1}^{d_i}h^V(j) = \sum\limits_{j = 1}^{d_i}h^U(j) + m</tex>, получим <tex>\sum\limits_{t = 1}^{d_i - m}h^V(t) = m - x(d_i) + \sum\limits_{t = 1}^{d_i - m}h^U(t)</tex>. Следовательно, мы пришли к тому, что (1) равносильно <tex>(d_i - m)m \geqslant \sum\limits_{t = 1}^{d_i - m}h^U(t)</tex>. Обозначим <tex>T = d_i - m</tex>, тогда предыдущее равенство превращается в <tex>Tm \geqslant \sum\limits_{t = 1}^{T}h^U(t)</tex> (2).<br> | Неравенство (1) равносильно <tex>(d_i - m)m \geqslant \sum\limits_{t = 1}^{d_i - m}h^U(t) + m - x(d_i)</tex>. По лемме имеем <tex>\sum\limits_{j = d_i - m + 1}^{d_i}h^V(j) = \sum\limits_{j = d_i - m + 1}^{d_i}h^U(j) + x(d_i)</tex>. Вычитая это равенство из <tex>\sum\limits_{j = 1}^{d_i}h^V(j) = \sum\limits_{j = 1}^{d_i}h^U(j) + m</tex>, получим <tex>\sum\limits_{t = 1}^{d_i - m}h^V(t) = m - x(d_i) + \sum\limits_{t = 1}^{d_i - m}h^U(t)</tex>. Следовательно, мы пришли к тому, что (1) равносильно <tex>(d_i - m)m \geqslant \sum\limits_{t = 1}^{d_i - m}h^U(t)</tex>. Обозначим <tex>T = d_i - m</tex>, тогда предыдущее равенство превращается в <tex>Tm \geqslant \sum\limits_{t = 1}^{T}h^U(t)</tex> (2).<br> | ||
− | Остается показать, что если равенство (2) выполняется для <tex>T = d_i - m</tex>, тогда оно выполняется и для <tex>T = 1, \ldots d_i - m - 1</tex>. | + | Остается показать, что если равенство (2) выполняется для <tex>T = d_i - m</tex>, тогда оно выполняется и для <tex>T = 1, \ldots d_i - m - 1</tex>. Докажем индукцией по <tex>T</tex>, что равенство (2) выполняется для <tex>T = 1, \ldots d_i - m</tex>, взяв как базу <tex>T = d_i - m</tex>. |
+ | #''База.'' По теореме из [[Opij1di#доказательство корректности|доказательства корректности]] <tex>h^V(1) \leqslant m</tex> означает, что <tex>V</tex> может быть выполнено вовремя. С другой стороны, если <tex>h^V(1) \leqslant m</tex>, то выполняется (2), так как <tex>h^V(t) \leqslant m</tex> для всех <tex>t \geqslant 2</tex> по построению <tex>h^V</tex>. | ||
+ | #''Переход.'' Предположим, что (2) выполняется для некоторого <tex>T \in (1, d_i - m]</tex>. Покажем, что тогда неравенство выполняется и для <tex>T - 1</tex>. Рассмотрим два случая в зависимости от значения <tex>h^V(T)</tex>: | ||
+ | #:<tex>(a)</tex> Пусть <tex>h^V(T) = m</tex>. Так как равенство (2) выполняется для <tex>T</tex>, то верно <tex>(T - 1)m \geqslant \sum\limits_{t = 1}^{T}h^V(t) - m = \sum\limits_{t = 1}^{T - 1}h^V(t)</tex>. Следовательно, (2) выполняется и для <tex>T - 1</tex>. | ||
+ | #:<tex>(b)</tex> Пусть <tex>h^V(T) < m</tex>. В расписании для множества работ <tex>V</tex> все стадии обработки работы <tex>i</tex> (<tex>k</tex> стадия обработки {{---}} выполнение работы на <tex>k</tex> машине) должны быть назначены на временные интервалы из отрезка <tex>[T - 1, d_i]</tex>, так как <tex>T \leqslant d_i - m</tex> и в период времени <tex>[T - 1, T]</tex> есть свободная машина. Все стадии обработки работ в расписании для <tex>U</tex>, назначенные на временные интервалы из отрезка <tex>[T - 1, d_i]</tex>, в расписании для <tex>V</tex> назначены на временные интервалы из того же отрезка <tex>[T - 1, d_i]</tex>. И так как <tex>U</tex> по условию может быть выполнено вовремя, верно неравенство <tex>(T - 1)m \geqslant \sum\limits_{t = 1}^{T - 1}h^U(t) = \sum\limits_{t = 1}^{T - 1}h^V(t)</tex>. Следовательно, (2) выполняется и для <tex>T - 1</tex>. | ||
}} | }} | ||
+ | Пусть <tex>k = |U|</tex> {{---}} мощность множества <tex>U</tex>. Тогда <tex>\sum\limits_{j = 1}^{d_i - m}(m - h^U(j)) = m(d_i - m) - \sum\limits_{j = 1}^{d_i - m}h^U(j) = m(d_i - m) - (km - \sum\limits_{j = d_i - m + 1}^{d_i}h^U(j))</tex>. Таким образом, (1) равносильно <tex>m(d_i - m) - (km - \sum\limits_{j = 1}^{m}h^U(d_i - m + j)) + x(d_i) \geqslant m</tex> (3). Мы пришли к тому, что нам достаточно знать только значения <tex>h^U(d_i - m + 1) \ldots h^U(d_i)</tex> и мощность <tex>k</tex> множества <tex>U</tex>, чтобы проверить, выполняется ли (3), то есть может ли множество <tex>V = U \cup \{i\}</tex> быть выполнено вовремя. Очевидно, что (3) может быть вычислено за время <tex>O(m)</tex>.<br> | ||
+ | Чтобы решить задачу <tex> O \mid p_{i,j} = 1, d_i \mid - </tex> для работ <tex>i = 1, 2 \ldots n</tex> с временами окончаний <tex>d_1 \leqslant d_2 \leqslant \ldots \leqslant d_n</tex>, для каждого <tex>i \in [1, n]</tex> мы проверяем, может ли множество <tex>U_i = \{1 \ldots i\}</tex> быть выполнено вовремя, если <tex>U_{i - 1}</tex> было выполнено вовремя. Этот шаг осуществляется за <tex>O(m)</tex> проверкой условия (3). Более того, по лемме значения <tex>h^{U_i}(d_i - m + 1) \ldots h^{U_i}(d_i)</tex> могут быть так же вычислены за <tex>O(m)</tex>. Следовательно, алгоритм может быть реализован за время <tex>O(mn)</tex>, если на вход дают работы в порядке неубывания времен окончания. | ||
== Доказательство корректности == | == Доказательство корректности == | ||
Строка 63: | Строка 132: | ||
Изначально алгоритм присваивает все стадии обработки каждой работы <tex>i</tex> (то есть обработку на каждом станке) попарно различным временным интервалам. Если <tex>\exists k > 1 : h(k) = m + 1</tex> и <tex>h(k - 1) \leqslant m</tex>, то это значит, что существует как минимум одна работа, которая назначена временному интервалу <tex>k</tex>, но которой нет во временном интервале <tex>k - 1</tex>. Следовательно, после перемещения вектор <tex>h</tex> по-прежнему будет удовлетворять условию, что каждая работа принадлежит <tex>m</tex> разным временным интервалам, причем в каждом из них она будет выполняться на разных машинах, так как при перемещении работ машины остаются прежними. Таким образом, если <tex>h(1) \leqslant m</tex>, то <tex>h(t) \leqslant m</tex>, где <tex>t = 1 \ldots T</tex>, то есть существует решение, при котором все работы будут выполнены вовремя. | Изначально алгоритм присваивает все стадии обработки каждой работы <tex>i</tex> (то есть обработку на каждом станке) попарно различным временным интервалам. Если <tex>\exists k > 1 : h(k) = m + 1</tex> и <tex>h(k - 1) \leqslant m</tex>, то это значит, что существует как минимум одна работа, которая назначена временному интервалу <tex>k</tex>, но которой нет во временном интервале <tex>k - 1</tex>. Следовательно, после перемещения вектор <tex>h</tex> по-прежнему будет удовлетворять условию, что каждая работа принадлежит <tex>m</tex> разным временным интервалам, причем в каждом из них она будет выполняться на разных машинах, так как при перемещении работ машины остаются прежними. Таким образом, если <tex>h(1) \leqslant m</tex>, то <tex>h(t) \leqslant m</tex>, где <tex>t = 1 \ldots T</tex>, то есть существует решение, при котором все работы будут выполнены вовремя. | ||
}} | }} | ||
+ | == См. также == | ||
+ | * [[Opi1sumu|<tex>O \mid p_{ij} = 1 \mid \sum U_i</tex>]] | ||
+ | * [[O2Cmax|<tex>O2 \mid \mid C_{max}</tex>]] | ||
+ | == Источники информации == | ||
+ | * Peter Brucker «Scheduling Algorithms», fifth edition, Springer {{---}} с. 163-168 ISBN 978-3-540-69515-8 | ||
+ | |||
+ | [[Категория: Алгоритмы и структуры данных]] | ||
+ | [[Категория: Теория расписаний]] |
Текущая версия на 19:06, 4 сентября 2022
Задача: |
Дано | одинаковых станков, которые работают параллельно, и работ, которые необходимо выполнить в произвольном порядке на всех станках. Любая работа на любом станке выполняется единицу времени. Для каждой работы есть время окончания — время, до которого она должна быть выполнена. Необходимо проверить, существует ли расписание, при котором все работы будут выполнены вовремя.
Содержание
Описание алгоритма
Идея
Табл. 1. Работа | назначена на интервалы .
---|
Заметим, что если
, то очевидно, что , следовательно, расписания не существует. Поэтому будем полагать, что для .Определим
— количество временных интервалов , где . Будем обозначать как . Для каждого из них мы можем назначить не более работ (по одной на каждый станок). Для каждой работы будем назначать времена обработки на каждой из машин следующим образом: на машине работа займет временной интервал , на машине — интервал и так далее, на машине работа займет временной интервал . В случае коллизий, то есть если найдется временной интервал , содержащий работу, возьмем минимальный такой и перенесем лишнюю работу из него на ту же машину, но на один временной интервал левее. Будем повторять этот процесс, пока необходимо (и пока ). Таким образом, только первый временной интервал может содержать более работ. Причем это может произойти тогда и только тогда, когда задача не имеет решения, то есть не существует расписания, при котором все работы будут выполнены вовремя.Псевдокод
Определим
— количество работ во временном интервале .void checkExistenceOfSchedule(int[]): for to for to for to (1) while and (2) find if return true else return false
Замечание: если расписание существует, то оно может быть вычислено данным алгоритмом, если добавить в цикл (1) функцию, отвечающую за добавление работы
на момент в расписании для соответствующей машины и в цикл (2) функцию, отвечающую за перемещение работы, которой нет во временном интервале , но которая есть в , на момент в той же машине (этот шаг будет обоснован далее в доказательстве корректности).Асимптотика
Покажем, что данный алгоритм может быть реализован за время
Для начала рассмотрим следующий вопрос: пусть — множество работ, для которого существует расписание, в котором отсутствуют опаздывающие работы, пусть — работа, не принадлежащая , для которой выполняется неравенство для любой . Можно ли построить расписание для множества , в котором так же будут отсутствовать опаздывающие работы.
Введем несколько обозначений. Вектора , соответствующие множествам и обозначим как и соответственно. — количество временных интервалов со свойствами
- ,
- .
Будем говорить, что множество работ может быть выполнено вовремя, если существует расписание, в котором все работы из этого множества успевают выполниться без опозданий.
Лемма: |
Пусть даны работы с дедлайнами , и . Тогда для всех работ , для которых , будет верно, что . |
Доказательство: |
Рассмотрим вектора |
Теорема: |
Пусть — множество работ, которое может быть выполнено вовремя, пусть — работа, не принадлежащая , для которой выполняется неравенство для любой . Тогда множество работ может быть выполнено вовремя тогда и только тогда, когда (1). |
Доказательство: |
Неравенство (1) равносильно
|
Пусть
Чтобы решить задачу для работ с временами окончаний , для каждого мы проверяем, может ли множество быть выполнено вовремя, если было выполнено вовремя. Этот шаг осуществляется за проверкой условия (3). Более того, по лемме значения могут быть так же вычислены за . Следовательно, алгоритм может быть реализован за время , если на вход дают работы в порядке неубывания времен окончания.
Доказательство корректности
Теорема: |
Для множества работ с дедлайнами задача имеет решение тогда и только тогда, когда . |
Доказательство: |
|
См. также
Источники информации
- Peter Brucker «Scheduling Algorithms», fifth edition, Springer — с. 163-168 ISBN 978-3-540-69515-8