Викиконспекты - Вклад участника [ru]

Обсуждение:J2pij1Lmax

2012-06-21T22:01:21Z

178.178.30.92: Новая страница: «Доказательства довольно крупные.»

Доказательства довольно крупные.

J2pij1Lmax

2012-06-21T22:00:23Z

178.178.30.92: /* Доказательство */

==Условие задачи==
В нотации Грэхема задача носит название <tex>J2\mid p_{ij} = 1\mid L_{max}</tex>

Дано <tex>n</tex> работ <tex>i = 1,\ldots,n</tex> и две машины, обозначенные как <tex>A</tex> и <tex>B</tex>.

<tex>i</tex>-тая работа состоит из <tex>n_i</tex> операций <tex>O_{ij}</tex> <tex>(j = 1,\ldots n_i)</tex>, которые должны быть выполнены последовательно и, при этом, если <tex>O_{ij} </tex> операция была совершена на машине <tex>A (B)</tex>, то операция <tex>O_{i,j-1}</tex> должна быть совершена на машине <tex>B (A)</tex>.

Задача заключается в том, что для данного каждой <tex>i</tex>-той работе дедлайна <tex>d_i \ge 0</tex> необходимо найти достижимое расписание с наименьшими максимальным временем опоздания:

<tex>\max\{C_i - d_i | i = 1, \ldots, n\}</tex>

==Описание решения==
Судя по условию, <tex>i</tex>-тая работа может характеризоваться двумя значениями: количество операций <tex>n_i</tex> и машиной, на которой была совершена первая операция. Пусть <tex>r = \sum_{i=1}^n N_i</tex> {{---}} общее количество операций.

Допустим, самым ранним моментом, когда операция может начать выполняться, будет момент времени 0, а верхнюю границу момента начала выполнения последней операции обозначим за <tex>t_{max}</tex>. К примеру, мы можем выбрать <tex>t_{max} = r</tex>. Тогда расписание можно представить как два списка <tex>A(t)</tex> и <tex>B(t) (t = 0,\ldots,t_{max})</tex>, где <tex>A(t) = O_{ij}</tex>, если операция <tex>O_{ij}</tex> должна выполниться на машине <tex>A</tex> в момент времени <tex>t</tex> и <tex>A(t) =</tex> <tex> \varnothing</tex>, если машина <tex>A</tex> простаивает в этот момент. И для каждой операции <tex>O_{ij}</tex>, выполняющейся на машине <tex>A</tex> существует <tex>t</tex>, для которого <tex>A(t) = O_{ij}</tex>. Аналогично для <tex>B_i</tex>. Расписание достижимо тогда и только тогда, когда из <tex>A(t) (B(t)) = O_{ij} , 1 < j \le n_i</tex> следует <tex>O_{i,j-1} = B(s) (A(s))</tex> для некоторого <tex>s < t</tex>, и первая операция для каждой работы запланирована на нужной машине. Перестановку всех операций будем называть списком. Для данный списка <tex>L</tex> осуществимое расписание может быть создано следующим способом: планируем выполнять операции в порядке, соответствующим <tex>L</tex>, причем каждую операцию стараемся выполнить как можно раньше. Подобное расписание будем называть соответствующим <tex>L</tex> расписанием.
<tex>C_i</tex> {{---}} время окончания работы <tex>i</tex> в достижимом расписании <tex>y = (A(t), B(t))</tex> можно рассчитать как:

<tex>C_i = \max\{t + 1 | A(t)\}</tex> или <tex>B(t)</tex> {{---}} операция <tex>i</tex>-той работы}

Задача заключается в том, что для данного каждой работе <tex>i</tex> дедлайна <tex>d_i \ge 0</tex> мы хотим найти достижимое расписание с наименьшими максимальным временем опоздания:

<tex>\max\{C_i - d_i | i = 1, \ldots, n\}</tex>

Следующий алгоритм решает эту задачу:

* Введём для каждой операции <tex>O_{ij}</tex> величину <tex>l(O_{ij}) = d_i - n_i + j</tex>
* Создадим список всех операций <tex>L</tex>, упорядоченный в порядке неубывания значений <tex>l(O_{ij})</tex>
* Найдем соответствующее списку <tex>L</tex> расписание.

Этот алгоритм может быть реализованным с асимптотикой <tex>O(r \log r)</tex>.

Мы предполагаем, что <tex>d_i \ge 0</tex> для <tex>i = 1,\ldots,n</tex> и хотя бы для одной работы <tex>i</tex> <tex>d_i = 0</tex>. Иначе, вычтем из всех <tex>d_i</tex> минимальное значение по <tex>d_i</tex>

Так как <tex>C_i \ge 1</tex> для всех <tex>i = 1,\ldots,n</tex> и <tex>d_i = 0</tex> справедливо <tex>L_i = C_i - d_i \ge 1</tex> как минимум для одной работы <tex>i</tex>. К тому же, можно предположить, что <tex>C_i \le r</tex>. Таким образом, работы с <tex>d_i > r - 1</tex>, то есть c <tex>L_i = C_i - d_i < 1</tex> можно смело игнорировать. Они не влияют на значение улучшаемой функции <tex>\max(L_i)</tex>, так как для некого <tex>i</tex> <tex>L_i \ge 1</tex> Можно выполнять эти работы в любом порядке после всех остальных. Для оставшихся операций <tex>O_{ij}</tex> мы имеем:

<tex>-r + 1 \le l(O_{ij}) = d_i - n_i + j \le r - 1</tex>

Каждую операцию мы кладём в соответствующий список (на самом деле это должен быть heap для хорошей асимптотики) <tex>L(k)</tex>, где <tex>k = l(O_{ij}) = d_i - n_i + j</tex> <tex>(-r + 1 \le k \le r - 1)</tex>. На втором шаге мы планируем операции соответственно возрастающему по номеру списка <tex>k</tex> порядку, где операции из одного списка могут выполнятся в произвольном порядке.

==Алгоритм==
Давайте детально рассмотрим алгоритм. <tex>T1</tex> и <tex>T2</tex> обозначают первый период времени <tex>t \ge 0</tex>, когда соответствующие машины <tex>A</tex> и <tex>B</tex> бездействуют. <tex>LAST(i)</tex> обозначает время окончания последней запланированной операции <tex>i</tex>-той работы. <tex>Z</tex> {{---}} множество работ, где <tex>d_i \ge r</tex>

'''main()'''
'''for''' k: -r + 1 '''to''' r - 1
<tex>L(k)</tex> = <tex>\emptyset</tex>;
Z = <tex>\emptyset</tex>;
'''for''' i: 1 '''to''' n
'''if''' <tex>d_i</tex> < r
'''for''' j: 1 '''to''' n_i
добавить <tex>O_{ij}</tex> в <tex>L(d_i - n_i + j)</tex>
'''else'''
добавить работу i в Z
'''for''' i: 1 '''to''' n
LAST(i) = 0;
T1 = 0;
T2 = 0;
'''for''' k: -r + 1 '''to''' r - 1
'''while''' <tex>L(k) \ne \emptyset</tex>
Выбрать задание <tex>O_{ij}</tex> из <tex>L(k)</tex>
<tex>L(k)</tex> = <tex>L(k)\setminus\{O_{ij}\}</tex>;
schedule(<tex>O_{ij}</tex>)
'''while''' <tex>z \ne \emptyset</tex>
Выбрать работу i из Z
Z = <tex>Z \setminus\{i\}</tex>;
'''for''' j: 1 '''to''' <tex>n_i</tex>
schedule(<tex>O_{ij}</tex>)

'''schedule(<tex>O_{ij}</tex>)'''
'''if''' <tex>\mu_{ij}</tex> == A
'''if''' T1 < LAST(i)
t = LAST(i)
A(t) = <tex>O_{ij}</tex> (*)
'''else'''
t = T1;
A(t) = <tex>O_{ij}</tex>;
'''while''' <tex>A(T_1)</tex> <tex>\ne \emptyset</tex>
T1 = T1 + 1;
'''else'''
'''if''' T2 < LAST(i)
t = LAST(i)
B(t) = <tex>O_{ij}</tex> (**)
'''else'''
t = T2;
A(t) = <tex>O_{ij}</tex>;
'''while''' <tex>B(T_2) \ne \emptyset</tex>
T2 = T2 + 1;
LAST(i) = t + 1

Очевидно, что количество шагов алгоритма ограничено <tex>O(r)</tex>

==Доказательство==

Для доказательство того, что алгоритм решения задачи корректен, необходимо показать то, что он строит достижимое расписание. Это справедливо тогда и только тогда, когда до исполнения строчек (*) и (**) пусты A(t) и B(t) соответственно. Иначе две разные операции будут выполняться в один момент времени на одной машине. Для того, чтобы показать достижимость докажем лемму.

{{Лемма
|id=lemma6.12
|statement=Пусть <tex>Y = (A(t), B(t))</tex> — расписание, где <tex>B(t) = \emptyset</tex> <tex>(A(t) = \emptyset)</tex>. Тогда для каждого <tex>s > t</tex>, где <tex>B(s) = O_{ij}</tex> <tex>(A(s) = O_{ij})</tex> выполняется <tex>A(s -1) = O_{i, j - 1}</tex> <tex>(B(s - 1) = O_{i, j -1}))</tex>
|proof={{в разработке}}
}}

{{Теорема
|id=theorem6.13.
|statement=Пусть <tex>O_{ij}</tex> — операция, которую планируют строчкой (*) или (**) и <tex>t = LAST(i) > T1(T2)</tex>. Тогда <tex>A(t) = \emptyset</tex> <tex>(B(t) = \emptyset)</tex>
|proof={{в разработке}}
}}

{{Лемма
|id=lemma6.14
|statement=Если существует расписание без опозданий, то данный алгоритм построит расписание без опозданий.
|proof={{в разработке}}
}}

{{Теорема
|id=theorem6.15.
|statement=Расписание, построенное данным алгоритмом, оптимально.
|proof={{в разработке}}
}}

==Источники==
* Peter Brucker. «Scheduling Algorithms» {{---}} «Springer», 2006 г. {{---}} 180 стр. {{---}} ISBN 978-3-540-69515-8

[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Теория расписаний]]

J2pij1Lmax

2012-06-21T21:47:35Z

178.178.30.92:

==Условие задачи==
В нотации Грэхема задача носит название <tex>J2\mid p_{ij} = 1\mid L_{max}</tex>

Дано <tex>n</tex> работ <tex>i = 1,\ldots,n</tex> и две машины, обозначенные как <tex>A</tex> и <tex>B</tex>.

<tex>i</tex>-тая работа состоит из <tex>n_i</tex> операций <tex>O_{ij}</tex> <tex>(j = 1,\ldots n_i)</tex>, которые должны быть выполнены последовательно и, при этом, если <tex>O_{ij} </tex> операция была совершена на машине <tex>A (B)</tex>, то операция <tex>O_{i,j-1}</tex> должна быть совершена на машине <tex>B (A)</tex>.

Задача заключается в том, что для данного каждой <tex>i</tex>-той работе дедлайна <tex>d_i \ge 0</tex> необходимо найти достижимое расписание с наименьшими максимальным временем опоздания:

<tex>\max\{C_i - d_i | i = 1, \ldots, n\}</tex>

==Описание решения==
Судя по условию, <tex>i</tex>-тая работа может характеризоваться двумя значениями: количество операций <tex>n_i</tex> и машиной, на которой была совершена первая операция. Пусть <tex>r = \sum_{i=1}^n N_i</tex> {{---}} общее количество операций.

Допустим, самым ранним моментом, когда операция может начать выполняться, будет момент времени 0, а верхнюю границу момента начала выполнения последней операции обозначим за <tex>t_{max}</tex>. К примеру, мы можем выбрать <tex>t_{max} = r</tex>. Тогда расписание можно представить как два списка <tex>A(t)</tex> и <tex>B(t) (t = 0,\ldots,t_{max})</tex>, где <tex>A(t) = O_{ij}</tex>, если операция <tex>O_{ij}</tex> должна выполниться на машине <tex>A</tex> в момент времени <tex>t</tex> и <tex>A(t) =</tex> <tex> \varnothing</tex>, если машина <tex>A</tex> простаивает в этот момент. И для каждой операции <tex>O_{ij}</tex>, выполняющейся на машине <tex>A</tex> существует <tex>t</tex>, для которого <tex>A(t) = O_{ij}</tex>. Аналогично для <tex>B_i</tex>. Расписание достижимо тогда и только тогда, когда из <tex>A(t) (B(t)) = O_{ij} , 1 < j \le n_i</tex> следует <tex>O_{i,j-1} = B(s) (A(s))</tex> для некоторого <tex>s < t</tex>, и первая операция для каждой работы запланирована на нужной машине. Перестановку всех операций будем называть списком. Для данный списка <tex>L</tex> осуществимое расписание может быть создано следующим способом: планируем выполнять операции в порядке, соответствующим <tex>L</tex>, причем каждую операцию стараемся выполнить как можно раньше. Подобное расписание будем называть соответствующим <tex>L</tex> расписанием.
<tex>C_i</tex> {{---}} время окончания работы <tex>i</tex> в достижимом расписании <tex>y = (A(t), B(t))</tex> можно рассчитать как:

<tex>C_i = \max\{t + 1 | A(t)\}</tex> или <tex>B(t)</tex> {{---}} операция <tex>i</tex>-той работы}

Задача заключается в том, что для данного каждой работе <tex>i</tex> дедлайна <tex>d_i \ge 0</tex> мы хотим найти достижимое расписание с наименьшими максимальным временем опоздания:

<tex>\max\{C_i - d_i | i = 1, \ldots, n\}</tex>

Следующий алгоритм решает эту задачу:

* Введём для каждой операции <tex>O_{ij}</tex> величину <tex>l(O_{ij}) = d_i - n_i + j</tex>
* Создадим список всех операций <tex>L</tex>, упорядоченный в порядке неубывания значений <tex>l(O_{ij})</tex>
* Найдем соответствующее списку <tex>L</tex> расписание.

Этот алгоритм может быть реализованным с асимптотикой <tex>O(r \log r)</tex>.

Мы предполагаем, что <tex>d_i \ge 0</tex> для <tex>i = 1,\ldots,n</tex> и хотя бы для одной работы <tex>i</tex> <tex>d_i = 0</tex>. Иначе, вычтем из всех <tex>d_i</tex> минимальное значение по <tex>d_i</tex>

Так как <tex>C_i \ge 1</tex> для всех <tex>i = 1,\ldots,n</tex> и <tex>d_i = 0</tex> справедливо <tex>L_i = C_i - d_i \ge 1</tex> как минимум для одной работы <tex>i</tex>. К тому же, можно предположить, что <tex>C_i \le r</tex>. Таким образом, работы с <tex>d_i > r - 1</tex>, то есть c <tex>L_i = C_i - d_i < 1</tex> можно смело игнорировать. Они не влияют на значение улучшаемой функции <tex>\max(L_i)</tex>, так как для некого <tex>i</tex> <tex>L_i \ge 1</tex> Можно выполнять эти работы в любом порядке после всех остальных. Для оставшихся операций <tex>O_{ij}</tex> мы имеем:

<tex>-r + 1 \le l(O_{ij}) = d_i - n_i + j \le r - 1</tex>

Каждую операцию мы кладём в соответствующий список (на самом деле это должен быть heap для хорошей асимптотики) <tex>L(k)</tex>, где <tex>k = l(O_{ij}) = d_i - n_i + j</tex> <tex>(-r + 1 \le k \le r - 1)</tex>. На втором шаге мы планируем операции соответственно возрастающему по номеру списка <tex>k</tex> порядку, где операции из одного списка могут выполнятся в произвольном порядке.

==Алгоритм==
Давайте детально рассмотрим алгоритм. <tex>T1</tex> и <tex>T2</tex> обозначают первый период времени <tex>t \ge 0</tex>, когда соответствующие машины <tex>A</tex> и <tex>B</tex> бездействуют. <tex>LAST(i)</tex> обозначает время окончания последней запланированной операции <tex>i</tex>-той работы. <tex>Z</tex> {{---}} множество работ, где <tex>d_i \ge r</tex>

'''main()'''
'''for''' k: -r + 1 '''to''' r - 1
<tex>L(k)</tex> = <tex>\emptyset</tex>;
Z = <tex>\emptyset</tex>;
'''for''' i: 1 '''to''' n
'''if''' <tex>d_i</tex> < r
'''for''' j: 1 '''to''' n_i
добавить <tex>O_{ij}</tex> в <tex>L(d_i - n_i + j)</tex>
'''else'''
добавить работу i в Z
'''for''' i: 1 '''to''' n
LAST(i) = 0;
T1 = 0;
T2 = 0;
'''for''' k: -r + 1 '''to''' r - 1
'''while''' <tex>L(k) \ne \emptyset</tex>
Выбрать задание <tex>O_{ij}</tex> из <tex>L(k)</tex>
<tex>L(k)</tex> = <tex>L(k)\setminus\{O_{ij}\}</tex>;
schedule(<tex>O_{ij}</tex>)
'''while''' <tex>z \ne \emptyset</tex>
Выбрать работу i из Z
Z = <tex>Z \setminus\{i\}</tex>;
'''for''' j: 1 '''to''' <tex>n_i</tex>
schedule(<tex>O_{ij}</tex>)

'''schedule(<tex>O_{ij}</tex>)'''
'''if''' <tex>\mu_{ij}</tex> == A
'''if''' T1 < LAST(i)
t = LAST(i)
A(t) = <tex>O_{ij}</tex> (*)
'''else'''
t = T1;
A(t) = <tex>O_{ij}</tex>;
'''while''' <tex>A(T_1)</tex> <tex>\ne \emptyset</tex>
T1 = T1 + 1;
'''else'''
'''if''' T2 < LAST(i)
t = LAST(i)
B(t) = <tex>O_{ij}</tex> (**)
'''else'''
t = T2;
A(t) = <tex>O_{ij}</tex>;
'''while''' <tex>B(T_2) \ne \emptyset</tex>
T2 = T2 + 1;
LAST(i) = t + 1

Очевидно, что количество шагов алгоритма ограничено <tex>O(r)</tex>

==Доказательство==

Для доказательство того, что алгоритм решения задачи корректен, необходимо показать то, что он строит достижимое расписание. Это справедливо тогда и только тогда, когда до исполнения строчек (*) и (**) пусты A(t) и B(t) соответственно. Иначе две разные операции будут выполняться в один момент времени на одной машине. Для того, чтобы показать достижимость докажем лемму.

{{Лемма
|id=lemma6.12
|statement=Пусть <tex>Y = (A(t), B(t))</tex> — расписание, где <tex>B(t) = \emptyset</tex> <tex>(A(t) = \emptyset)</tex>. Тогда для каждого <tex>s > t</tex>, где <tex>B(s) = O_{ij}</tex> <tex>(A(s) = O_{ij})</tex> выполняется <tex>A(s -1) = O_{i, j - 1}</tex> <tex>(B(s - 1) = O_{i, j -1}))</tex>
}}

==Источники==
* Peter Brucker. «Scheduling Algorithms» {{---}} «Springer», 2006 г. {{---}} 180 стр. {{---}} ISBN 978-3-540-69515-8

[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Теория расписаний]]

J2pij1Lmax

2012-06-21T21:28:12Z

178.178.30.92:

==Условие задачи==
В нотации Грэхема задача носит название <tex>J2\mid p_{ij} = 1\mid L_{max}</tex>

Дано <tex>n</tex> работ <tex>i = 1,\ldots,n</tex> и две машины, обозначенные как <tex>A</tex> и <tex>B</tex>.

<tex>i</tex>-тая работа состоит из <tex>n_i</tex> операций <tex>O_{ij}</tex> <tex>(j = 1,\ldots n_i)</tex>, которые должны быть выполнены последовательно и, при этом, если <tex>O_{ij} </tex> операция была совершена на машине <tex>A (B)</tex>, то операция <tex>O_{i,j-1}</tex> должна быть совершена на машине <tex>B (A)</tex>.

Задача заключается в том, что для данного каждой <tex>i</tex>-той работе дедлайна <tex>d_i \ge 0</tex> необходимо найти достижимое расписание с наименьшими максимальным временем опоздания:

<tex>\max\{C_i - d_i | i = 1, \ldots, n\}</tex>

==Описание решения==
Судя по условию, <tex>i</tex>-тая работа может характеризоваться двумя значениями: количество операций <tex>n_i</tex> и машиной, на которой была совершена первая операция. Пусть <tex>r = \sum_{i=1}^n N_i</tex> {{---}} общее количество операций.

Допустим, самым ранним моментом, когда операция может начать выполняться, будет момент времени 0, а верхнюю границу момента начала выполнения последней операции обозначим за <tex>t_{max}</tex>. К примеру, мы можем выбрать <tex>t_{max} = r</tex>. Тогда расписание можно представить как два списка <tex>A(t)</tex> и <tex>B(t) (t = 0,\ldots,t_{max})</tex>, где <tex>A(t) = O_{ij}</tex>, если операция <tex>O_{ij}</tex> должна выполниться на машине <tex>A</tex> в момент времени <tex>t</tex> и <tex>A(t) =</tex> <tex> \varnothing</tex>, если машина <tex>A</tex> простаивает в этот момент. И для каждой операции <tex>O_{ij}</tex>, выполняющейся на машине <tex>A</tex> существует <tex>t</tex>, для которого <tex>A(t) = O_{ij}</tex>. Аналогично для <tex>B_i</tex>. Расписание достижимо тогда и только тогда, когда из <tex>A(t) (B(t)) = O_{ij} , 1 < j \le n_i</tex> следует <tex>O_{i,j-1} = B(s) (A(s))</tex> для некоторого <tex>s < t</tex>, и первая операция для каждой работы запланирована на нужной машине. Перестановку всех операций будем называть списком. Для данный списка <tex>L</tex> осуществимое расписание может быть создано следующим способом: планируем выполнять операции в порядке, соответствующим <tex>L</tex>, причем каждую операцию стараемся выполнить как можно раньше. Подобное расписание будем называть соответствующим <tex>L</tex> расписанием.
<tex>C_i</tex> {{---}} время окончания работы <tex>i</tex> в достижимом расписании <tex>y = (A(t), B(t))</tex> можно рассчитать как:

<tex>C_i = \max\{t + 1 | A(t)\}</tex> или <tex>B(t)</tex> {{---}} операция <tex>i</tex>-той работы}

Задача заключается в том, что для данного каждой работе <tex>i</tex> дедлайна <tex>d_i \ge 0</tex> мы хотим найти достижимое расписание с наименьшими максимальным временем опоздания:

<tex>\max\{C_i - d_i | i = 1, \ldots, n\}</tex>

Следующий алгоритм решает эту задачу:

* Введём для каждой операции <tex>O_{ij}</tex> величину <tex>l(O_{ij}) = d_i - n_i + j</tex>
* Создадим список всех операций <tex>L</tex>, упорядоченный в порядке неубывания значений <tex>l(O_{ij})</tex>
* Найдем соответствующее списку <tex>L</tex> расписание.

Этот алгоритм может быть реализованным с асимптотикой <tex>O(r \log r)</tex>.

Мы предполагаем, что <tex>d_i \ge 0</tex> для <tex>i = 1,\ldots,n</tex> и хотя бы для одной работы <tex>i</tex> <tex>d_i = 0</tex>. Иначе, вычтем из всех <tex>d_i</tex> минимальное значение по <tex>d_i</tex>

Так как <tex>C_i \ge 1</tex> для всех <tex>i = 1,\ldots,n</tex> и <tex>d_i = 0</tex> справедливо <tex>L_i = C_i - d_i \ge 1</tex> как минимум для одной работы <tex>i</tex>. К тому же, можно предположить, что <tex>C_i \le r</tex>. Таким образом, работы с <tex>d_i > r - 1</tex>, то есть c <tex>L_i = C_i - d_i < 1</tex> можно смело игнорировать. Они не влияют на значение улучшаемой функции <tex>\max(L_i)</tex>, так как для некого <tex>i</tex> <tex>L_i \ge 1</tex> Можно выполнять эти работы в любом порядке после всех остальных. Для оставшихся операций <tex>O_{ij}</tex> мы имеем:

<tex>-r + 1 \le l(O_{ij}) = d_i - n_i + j \le r - 1</tex>

Каждую операцию мы кладём в соответствующий список (на самом деле это должен быть heap для хорошей асимптотики) <tex>L(k)</tex>, где <tex>k = l(O_{ij}) = d_i - n_i + j</tex> <tex>(-r + 1 \le k \le r - 1)</tex>. На втором шаге мы планируем операции соответственно возрастающему по номеру списка <tex>k</tex> порядку, где операции из одного списка могут выполнятся в произвольном порядке.

==Алгоритм==
Давайте детально рассмотрим алгоритм. <tex>T1</tex> и <tex>T2</tex> обозначают первый период времени <tex>t \ge 0</tex>, когда соответствующие машины <tex>A</tex> и <tex>B</tex> бездействуют. <tex>LAST(i)</tex> обозначает время окончания последней запланированной операции <tex>i</tex>-той работы. <tex>Z</tex> {{---}} множество работ, где <tex>d_i \ge r</tex>

'''main()'''
'''for''' k: -r + 1 '''to''' r - 1
<tex>L(k)</tex> = <tex>\emptyset</tex>;
Z = <tex>\emptyset</tex>;
'''for''' i: 1 '''to''' n
'''if''' <tex>d_i</tex> < r
'''for''' j: 1 '''to''' n_i
добавить <tex>O_{ij}</tex> в <tex>L(d_i - n_i + j)</tex>
'''else'''
добавить работу i в Z
'''for''' i: 1 '''to''' n
LAST(i) = 0;
T1 = 0;
T2 = 0;
'''for''' k: -r + 1 '''to''' r - 1
'''while''' <tex>L(k) \ne \emptyset</tex>
Выбрать задание <tex>O_{ij}</tex> из <tex>L(k)</tex>
<tex>L(k)</tex> = <tex>L(k)\setminus\{O_{ij}\}</tex>;
schedule(<tex>O_{ij}</tex>)
'''while''' <tex>z \ne \emptyset</tex>
Выбрать работу i из Z
Z = <tex>Z \setminus\{i\}</tex>;
'''for''' j: 1 '''to''' <tex>n_i</tex>
schedule(<tex>O_{ij}</tex>)

'''schedule(<tex>O_{ij}</tex>)'''
'''if''' <tex>\mu_{ij}</tex> == A
'''if''' T1 < LAST(i)
t = LAST(i)
A(t) = <tex>O_{ij}</tex>
'''else'''
t = T1;
A(t) = <tex>O_{ij}</tex>;
'''while''' <tex>A(T_1)</tex> <tex>\ne \emptyset</tex>
T1 = T1 + 1;
'''else'''
'''if''' T2 < LAST(i)
t = LAST(i)
B(t) = <tex>O_{ij}</tex>
'''else'''
t = T2;
A(t) = <tex>O_{ij}</tex>;
'''while''' <tex>B(T_2) \ne \emptyset</tex>
T2 = T2 + 1;
LAST(i) = t + 1

Очевидно, что количество шагов алгоритма ограничено <tex>O(r)</tex>

==Доказательство==

==Источники==
* Peter Brucker. «Scheduling Algorithms» {{---}} «Springer», 2006 г. {{---}} 180 стр. {{---}} ISBN 978-3-540-69515-8

[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Теория расписаний]]

J2pij1Lmax

2012-06-21T21:25:55Z

178.178.30.92:

==Условие задачи==
В нотации Грэхема задача носит название <tex>J2\mid p_{ij} = 1\mid L_{max}</tex>

Дано <tex>n</tex> работ <tex>i = 1,\ldots,n</tex> и две машины, обозначенные как <tex>A</tex> и <tex>B</tex>.

<tex>i</tex>-тая работа состоит из <tex>n_i</tex> операций <tex>O_{ij}</tex> <tex>(j = 1,\ldots n_i)</tex>, которые должны быть выполнены последовательно и, при этом, если <tex>O_{ij} </tex> операция была совершена на машине <tex>A (B)</tex>, то операция <tex>O_{i,j-1}</tex> должна быть совершена на машине <tex>B (A)</tex>.

Задача заключается в том, что для данного каждой <tex>i</tex>-той работе дедлайна <tex>d_i \ge 0</tex> необходимо найти достижимое расписание с наименьшими максимальным временем опоздания:

<tex>\max\{C_i - d_i | i = 1, \ldots, n\}</tex>

==Описание решения==
Судя по условию, <tex>i</tex>-тая работа может характеризоваться двумя значениями: количество операций <tex>n_i</tex> и машиной, на которой была совершена первая операция. Пусть <tex>r = \sum_{i=1}^n N_i</tex> {{---}} общее количество операций.

Допустим, самым ранним моментом, когда операция может начать выполняться, будет момент времени 0, а верхнюю границу момента начала выполнения последней операции обозначим за <tex>t_{max}</tex>. К примеру, мы можем выбрать <tex>t_{max} = r</tex>. Тогда расписание можно представить как два списка <tex>A(t)</tex> и <tex>B(t) (t = 0,\ldots,t_{max})</tex>, где <tex>A(t) = O_{ij}</tex>, если операция <tex>O_{ij}</tex> должна выполниться на машине <tex>A</tex> в момент времени <tex>t</tex> и <tex>A(t) =</tex> <tex> \varnothing</tex>, если машина <tex>A</tex> простаивает в этот момент. И для каждой операции <tex>O_{ij}</tex>, выполняющейся на машине <tex>A</tex> существует <tex>t</tex>, для которого <tex>A(t) = O_{ij}</tex>. Аналогично для <tex>B_i</tex>. Расписание достижимо тогда и только тогда, когда из <tex>A(t) (B(t)) = O_{ij} , 1 < j \le n_i</tex> следует <tex>O_{i,j-1} = B(s) (A(s))</tex> для некоторого <tex>s < t</tex>, и первая операция для каждой работы запланирована на нужной машине. Перестановку всех операций будем называть списком. Для данный списка <tex>L</tex> осуществимое расписание может быть создано следующим способом: планируем выполнять операции в порядке, соответствующим <tex>L</tex>, причем каждую операцию стараемся выполнить как можно раньше. Подобное расписание будем называть соответствующим <tex>L</tex> расписанием.
<tex>C_i</tex> {{---}} время окончания работы <tex>i</tex> в достижимом расписании <tex>y = (A(t), B(t))</tex> можно рассчитать как:

<tex>C_i = \max\{t + 1 | A(t)\}</tex> или <tex>B(t)</tex> {{---}} операция <tex>i</tex>-той работы}

Задача заключается в том, что для данного каждой работе <tex>i</tex> дедлайна <tex>d_i \ge 0</tex> мы хотим найти достижимое расписание с наименьшими максимальным временем опоздания:

<tex>\max\{C_i - d_i | i = 1, \ldots, n\}</tex>

Следующий алгоритм решает эту задачу:

* Введём для каждой операции <tex>O_{ij}</tex> величину <tex>l(O_{ij}) = d_i - n_i + j</tex>
* Создадим список всех операций <tex>L</tex>, упорядоченный в порядке неубывания значений <tex>l(O_{ij})</tex>
* Найдем соответствующее списку <tex>L</tex> расписание.

Этот алгоритм может быть реализованным с асимптотикой <tex>O(r \log r)</tex>.

Мы предполагаем, что <tex>d_i \ge 0</tex> для <tex>i = 1,\ldots,n</tex> и хотя бы для одной работы <tex>i</tex> <tex>d_i = 0</tex>. Иначе, вычтем из всех <tex>d_i</tex> минимальное значение по <tex>d_i</tex>

Так как <tex>C_i \ge 1</tex> для всех <tex>i = 1,\ldots,n</tex> и <tex>d_i = 0</tex> справедливо <tex>L_i = C_i - d_i \ge 1</tex> как минимум для одной работы <tex>i</tex>. К тому же, можно предположить, что <tex>C_i \le r</tex>. Таким образом, работы с <tex>d_i > r - 1</tex>, то есть c <tex>L_i = C_i - d_i < 1</tex> можно смело игнорировать. Они не влияют на значение улучшаемой функции <tex>\max(L_i)</tex>, так как для некого <tex>i</tex> <tex>L_i \ge 1</tex> Можно выполнять эти работы в любом порядке после всех остальных. Для оставшихся операций <tex>O_{ij}</tex> мы имеем:

<tex>-r + 1 \le l(O_{ij}) = d_i - n_i + j \le r - 1</tex>

Каждую операцию мы кладём в соответствующий список (на самом деле это должен быть heap для хорошей асимптотики) <tex>L(k)</tex>, где <tex>k = l(O_{ij}) = d_i - n_i + j</tex> <tex>(-r + 1 \le k \le r - 1)</tex>. На втором шаге мы планируем операции соответственно возрастающему по номеру списка <tex>k</tex> порядку, где операции из одного списка могут выполнятся в произвольном порядке.

==Алгоритм==
Давайте детально рассмотрим алгоритм. <tex>T1</tex> и <tex>T2</tex> обозначают первый период времени <tex>t \ge 0</tex>, когда соответствующие машины <tex>A</tex> и <tex>B</tex> бездействуют. <tex>LAST(i)</tex> обозначает время окончания последней запланированной операции <tex>i</tex>-той работы. <tex>Z</tex> {{---}} множество работ, где <tex>d_i \ge r</tex>

'''main()'''
'''for''' k: -r + 1 '''to''' r - 1
<tex>L(k)</tex> = <tex>\emptyset</tex>;
Z = <tex>\emptyset</tex>;
'''for''' i: 1 '''to''' n
'''if''' <tex>d_i</tex> < r
'''for''' j: 1 '''to''' n_i
добавить <tex>O_{ij}</tex> в <tex>L(d_i - n_i + j)</tex>
'''else'''
добавить работу i в Z
'''for''' i: 1 '''to''' n
LAST(i) = 0;
T1 = 0;
T2 = 0;
'''for''' k: -r + 1 '''to''' r - 1
'''while''' <tex>L(k) \ne \emptyset</tex>
Выбрать задание <tex>O_{ij}</tex> из <tex>L(k)</tex>
<tex>L(k)</tex> = <tex>L(k)\setminus\{O_{ij}\}</tex>;
schedule(<tex>O_{ij}</tex>)
'''while''' <tex>z \ne \emptyset</tex>
Выбрать работу i из Z
Z = <tex>Z \setminus\{i\}</tex>;
'''for''' j: 1 '''to''' <tex>n_i</tex>
schedule(<tex>O_{ij}</tex>)

'''schedule(<tex>O_{ij}</tex>)'''
'''if''' <tex>\mu_{ij}</tex> == A
'''if''' T1 < LAST(i)
t = LAST(i)
A(t) = <tex>O_{ij}</tex>
'''else'''
t = T1;
A(t) = <tex>O_{ij}</tex>;
'''while''' <tex>A(T_1)</tex> <tex>\ne \emptyset</tex>
T1 = T1 + 1;
'''else'''
'''if''' T2 < LAST(i)
t = LAST(i)
B(t) = <tex>O_{ij}</tex>
'''else'''
t = T2;
A(t) = <tex>O_{ij}</tex>;
'''while''' <tex>B(T_2) \ne \emptyset</tex>
T2 = T2 + 1;
LAST(i) = t + 1

Очевидно, что количество шагов алгоритма ограничено <tex>O(r)</tex>

==Источники==
* Peter Brucker. «Scheduling Algorithms» {{---}} «Springer», 2006 г. {{---}} 180 стр. {{---}} ISBN 978-3-540-69515-8

[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Теория расписаний]]