Flow shop — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
м (Задача Джонсона о двух станках F_2 \mid \mid C_{max})
(Псевдокод)
(не показано 19 промежуточных версий 1 участника)
Строка 1: Строка 1:
 
== Описание ==
 
== Описание ==
{{Определение
 
|definition =
 
'''Flow shop''' ('''<tex>F_{m}</tex>''' в нотации Грэхема): В системе находится <tex> m </tex> машин, работающих параллельно. Машины упорядочены. Каждая работа должна быть выполнена последовательно на всех машинах с первой по последнюю.}}
 
 
 
Рассмотрим пример:  <tex>F \mid p_{ij} = 1 \mid C_{max}</tex>
 
Рассмотрим пример:  <tex>F \mid p_{ij} = 1 \mid C_{max}</tex>
  
Строка 73: Строка 69:
 
Заметим, что в данном случае <tex>p_{ij}</tex> может быть равно не только единице, но и любой константе.
 
Заметим, что в данном случае <tex>p_{ij}</tex> может быть равно не только единице, но и любой константе.
 
   
 
   
{{Утверждение
+
{{Теорема
 
|statement = Любая задача вида <tex>F \mid p_{ij} = 1 \mid ? </tex> сводится к соответствующей задаче вида <tex>1 \mid p_{ij} = 1 \mid ?</tex>.  
 
|statement = Любая задача вида <tex>F \mid p_{ij} = 1 \mid ? </tex> сводится к соответствующей задаче вида <tex>1 \mid p_{ij} = 1 \mid ?</tex>.  
 
|proof =  
 
|proof =  
Строка 81: Строка 77:
 
}}
 
}}
  
Примером применения этого утверждения может служить следующая [[Fpij1sumwu|задача: <tex>F \mid p_{ij} = 1 \mid \sum w_iu_i</tex>]].
+
Примером применения этой теоремы может служить следующая [[Fpij1sumwu|задача: <tex>F \mid p_{ij} = 1 \mid \sum w_iu_i</tex>]].
  
Задачи с произвольными временами выполнения работ почти все являются NP-трудными.
+
Задачи с произвольными временами выполнения работ почти все являются [[Классы_NP,_coNP,_Σ₁,_Π₁#.D0.9E.D0.BF.D1.80.D0.B5.D0.B4.D0.B5.D0.BB.D0.B5.D0.BD.D0.B8.D1.8F.2C_.D1.81.D0.B2.D1.8F.D0.B7.D1.8C_.CE.A3.E2.82.81_.D0.B8_NP | NP-трудными]].
  
 
== Задача Джонсона о двух станках <tex>F_2 \mid \mid C_{max}</tex> ==
 
== Задача Джонсона о двух станках <tex>F_2 \mid \mid C_{max}</tex> ==
Строка 89: Строка 85:
 
Это единственная из flow shop задач с произвольными временами выполнения работ, которая решается за полиномиальное время.
 
Это единственная из flow shop задач с произвольными временами выполнения работ, которая решается за полиномиальное время.
  
Приведём здесь решение задачи без доказательства <ref> Его можно посмотреть тут [http://books.google.ru/books?id=FrUytMqlCv8C&printsec=frontcover&dq=scheduling+algorithms&hl=ru&sa=X&ei=0MPMT4HqKYSk4gSBm6gp&sqi=2&ved=0CDEQ6AEwAA#v=onepage&q=scheduling%20algorithms&f=false Scheduling Algorithms, Peter Brucker] </ref>.
+
Приведём здесь решение задачи без доказательства<ref> Доказательство описано в книге [http://books.google.ru/books?id=FrUytMqlCv8C&printsec=frontcover&dq=scheduling+algorithms&hl=ru&sa=X&ei=0MPMT4HqKYSk4gSBm6gp&sqi=2&ved=0CDEQ6AEwAA#v=onepage&q=scheduling%20algorithms&f=false Scheduling Algorithms, Peter Brucker] на страницах 174 {{---}} 178.</ref>.
  
 
Оптимальное расписание для первой и второй машины будет совпадать. Таким образом, нам требуется найти порядок, в котором будут выполняться работы на каждой машине.
 
Оптимальное расписание для первой и второй машины будет совпадать. Таким образом, нам требуется найти порядок, в котором будут выполняться работы на каждой машине.
  
Алгоритм такой: возьмём два пустых списка. Будем рассматривать работы в порядке возрастания <tex>min(p_1, p_2)</tex>, то есть, минимума из времён выполнения данной работы на первой и второй машине. Если у работы <tex>p_1 \leqslant p_2</tex>, то добавим её в конец первого списка. В противном случае, добавим её в начало второго списка. Итоговое расписание — это конкатенация первого и второго списков.
+
===Алгоритм===
 +
Обозначим за <tex>p_1</tex> время выполнения работы на первом станке, за <tex>p_2</tex> время выполнения работы на втором станке.
 +
 
 +
Будем использовать следующий алгоритм: возьмём два пустых списка и будем рассматривать работы в порядке возрастания <tex>\min(p_1, p_2)</tex>, то есть, минимума из времён выполнения данной работы на первой и второй машине. Если у работы <tex>p_1 \leqslant p_2</tex>, то добавим её в конец первого списка. В противном случае, добавим её в начало второго списка. Итоговое расписание — это конкатенация первого и второго списков.
  
Псевдокод:
+
===Псевдокод===
    <tex> Head = \varnothing </tex>
+
Для представления работы в памяти будем использовать следующую структуру:
    <tex>Tail = \varnothing </tex>
+
'''struct''' Job:
    <font color = green>//J - множество работ</font>
+
    '''int''' <tex>p_1</tex>   <font color = green>// Время выполнения на первом станке</font>
    '''while''' J <tex> \ne \varnothing </tex>  
+
    '''int''' <tex>p_2</tex>    <font color = green>// Время выполнения на втором станке</font>
         I <tex> = </tex> работа с минимальным значением <tex>min(p_1, p_2)</tex>
+
 
 +
Приведём реализацию самого алгоритма:
 +
*<tex> \mathtt{J}</tex> {{---}} список работ, которые надо выполнить,
 +
*<tex> \mathtt{List1}</tex>, <tex> \mathtt{List2} </tex> {{---}} списки, в которые будем записывать порядок выполнения работ.
 +
 
 +
<font color = green>// Функция принимает список работ J и возвращает список с расписанием работ.</font>
 +
'''function''' scheduling(<tex>J</tex>: '''List<Job>'''): '''List<int>'''
 +
    <tex> \mathtt{List1} = \varnothing </tex>
 +
    <tex>\mathtt{List2} = \varnothing </tex>
 +
    '''while''' <tex>J \ne \varnothing </tex>  
 +
         <tex>I</tex> = работа с минимальным значением <tex>\min(p_1, \ \ p_2)</tex>
 
         '''if''' <tex>p_1 \leqslant p_2</tex>
 
         '''if''' <tex>p_1 \leqslant p_2</tex>
             <tex>Head = {Head } \cup  I </tex>
+
             <tex> \mathtt{List1} = \mathtt{List1} \cup  I </tex>
 
         '''else'''  
 
         '''else'''  
             <tex>Tail = I \cup  Tail </tex>
+
             <tex>\mathtt{List2} = I \cup  \mathtt{List2} </tex>
 
         <tex>J = J \setminus I </tex>
 
         <tex>J = J \setminus I </tex>
    <tex>\mathrm{Result} = Head \cup  Tail </tex>
+
    '''return''' <tex>\mathtt{List1} \cup  \mathtt{List2} </tex>
  
 
== Задача Джонсона о двух станках с прерываниями <tex>F_2 \mid pmtn \mid C_{max}</tex> ==
 
== Задача Джонсона о двух станках с прерываниями <tex>F_2 \mid pmtn \mid C_{max}</tex> ==
 
+
{{Теорема
Оптимальное решение этой задачи совпадает с решением задачи <tex>F_2 \mid \mid C_{max}</tex>, приведённой выше. Докажем это.
+
|statement= Оптимальное решение этой задачи совпадает с решением задачи <tex>F_2 \mid \mid C_{max}</tex>, приведённой выше.
 
+
|proof = Пусть у нас есть оптимальное расписание для задачи <tex>F_2 \mid pmtn \mid C_{max}</tex>. Покажем, что его за конечное число шагов можно преобразовать к расписанию без прерываний, не изменив при это значение <tex>C_{max}</tex> .
Пусть у нас есть оптимальное расписание для задачи <tex>F_2 \mid pmtn \mid C_{max}</tex>. Покажем, что его за конечное число шагов можно преобразовать к расписанию без прерываний, не изменив при это значение <tex>C_{max}</tex> .
 
  
 
Рассмотрим первую машину. Допустим, что некоторая работа <tex> J </tex> выполняется в <tex> 2 </tex> или более разных промежутка времени. Тогда передвинем более ранний промежуток вправо по оси времени так, чтоб он заканчивался в тот момент, когда начинается второй промежуток, при этом работы, которые были между этими двумя промежутками, сдвинем влево на длину первого промежутка. Расписание при этом осталось корректным, так как работы на машинах по-прежнему не пересекаются, и каждая работа на второй машине делается после того, как она сделана на первой: работа <tex> J </tex> может начать выполняться на второй машине только после того, как она целиком выполнится на первой, то есть уже после конца второго промежутка; а время окончания выполнения остальных работ на первой машине неувеличилось.
 
Рассмотрим первую машину. Допустим, что некоторая работа <tex> J </tex> выполняется в <tex> 2 </tex> или более разных промежутка времени. Тогда передвинем более ранний промежуток вправо по оси времени так, чтоб он заканчивался в тот момент, когда начинается второй промежуток, при этом работы, которые были между этими двумя промежутками, сдвинем влево на длину первого промежутка. Расписание при этом осталось корректным, так как работы на машинах по-прежнему не пересекаются, и каждая работа на второй машине делается после того, как она сделана на первой: работа <tex> J </tex> может начать выполняться на второй машине только после того, как она целиком выполнится на первой, то есть уже после конца второго промежутка; а время окончания выполнения остальных работ на первой машине неувеличилось.
Строка 121: Строка 129:
 
Теперь избавимся от прерываний на второй машине. Точно так же рассмотрим работу, разбитую на два или более промежутка. Передвинем более поздний промежуток к концу более раннего, а работы между ними сдвинем вправо. Доказательство корректности измененного расписания аналогично доказательству для первой машины. Будем повторять данную операцию, пока на второй машине присутствуют прерывания.
 
Теперь избавимся от прерываний на второй машине. Точно так же рассмотрим работу, разбитую на два или более промежутка. Передвинем более поздний промежуток к концу более раннего, а работы между ними сдвинем вправо. Доказательство корректности измененного расписания аналогично доказательству для первой машины. Будем повторять данную операцию, пока на второй машине присутствуют прерывания.
  
Таким образом, мы получили корректное расписание без прерываний, не изменив при этом значение <tex>C_{max}</tex>, что и требовалось доказать.
+
Таким образом, мы получили корректное расписание без прерываний, не изменив при этом значение <tex>C_{max}</tex>.}}
  
 
== См. также ==
 
== См. также ==
Строка 127: Строка 135:
 
* [[Fpij1sumwu|<tex>F \mid p_{ij} = 1 \mid \sum w_i u_i</tex>]]
 
* [[Fpij1sumwu|<tex>F \mid p_{ij} = 1 \mid \sum w_i u_i</tex>]]
  
==Примичания==
+
==Примeчания==
 
<references/>
 
<references/>
  
 
[[Категория: Дискретная математика и алгоритмы]]
 
[[Категория: Дискретная математика и алгоритмы]]
 
[[Категория: Теория расписаний]]
 
[[Категория: Теория расписаний]]

Версия 14:03, 19 мая 2016

Описание

Рассмотрим пример: [math]F \mid p_{ij} = 1 \mid C_{max}[/math]

Допустим, у нас [math]n[/math] работ и [math]m[/math] машин. В начальный момент времени мы можем начать обрабатывать любую работу на первой машине. В следующий момент на первой машине можно обрабатывать следующую работу, а на второй перейдёт предыдущая работа с первой машины, и так далее. Таким образом, на выполнение всех работ у нас уйдёт [math]n + m - 1[/math] единиц времени. Проиллюстрируем это диаграммой Гантта для случая [math]n = 6, m = 5[/math]:

0 1 2 3 5 6 7 8 9 10
[math]M_1[/math] 1 2 3 4 5 6
[math]M_2[/math] 1 2 3 4 5 6
[math]M_3[/math] 1 2 3 4 5 6
[math]M_4[/math] 1 2 3 4 5 6
[math]M_5[/math] 1 2 3 4 5 6

Заметим, что в данном случае [math]p_{ij}[/math] может быть равно не только единице, но и любой константе.

Теорема:
Любая задача вида [math]F \mid p_{ij} = 1 \mid ? [/math] сводится к соответствующей задаче вида [math]1 \mid p_{ij} = 1 \mid ?[/math].
Доказательство:
[math]\triangleright[/math]

Поскольку работа всегда заканчивает выполняться на последней машине, нас интересуют только времена завершения работ на последней машине. Также очевидно, что последняя машина может начать работать только в момент времени [math] m - 1 [/math]. Оказывается, что любое решение задачи [math] 1 \mid p_{ij} = 1 \mid ? [/math] с дедлайнами, уменьшенными на [math] m - 1 [/math] можно преобразовать в оптимальное расписание для задачи [math]F \mid p_{ij} = 1 \mid ? [/math]. Докажем это.

Возьмем оптимальное расписание для соответствующей задачи с одним станком, выполним работы в этом порядке на первой машине, затем на второй машине, начиная с момента времени [math] 1 [/math], и так далее, до выполнения на последней машине, начиная с [math] m - 1 [/math]. Это расписание корректно и соблюдает все дедлайны. Поскольку целевая функция совпадает с соответствующей функцией для задачи на одном станке, оно оптимально и для данной задачи.
[math]\triangleleft[/math]

Примером применения этой теоремы может служить следующая задача: [math]F \mid p_{ij} = 1 \mid \sum w_iu_i[/math].

Задачи с произвольными временами выполнения работ почти все являются NP-трудными.

Задача Джонсона о двух станках [math]F_2 \mid \mid C_{max}[/math]

Это единственная из flow shop задач с произвольными временами выполнения работ, которая решается за полиномиальное время.

Приведём здесь решение задачи без доказательства[1].

Оптимальное расписание для первой и второй машины будет совпадать. Таким образом, нам требуется найти порядок, в котором будут выполняться работы на каждой машине.

Алгоритм

Обозначим за [math]p_1[/math] время выполнения работы на первом станке, за [math]p_2[/math] время выполнения работы на втором станке.

Будем использовать следующий алгоритм: возьмём два пустых списка и будем рассматривать работы в порядке возрастания [math]\min(p_1, p_2)[/math], то есть, минимума из времён выполнения данной работы на первой и второй машине. Если у работы [math]p_1 \leqslant p_2[/math], то добавим её в конец первого списка. В противном случае, добавим её в начало второго списка. Итоговое расписание — это конкатенация первого и второго списков.

Псевдокод

Для представления работы в памяти будем использовать следующую структуру:

struct Job:
    int [math]p_1[/math]    // Время выполнения на первом станке
    int [math]p_2[/math]    // Время выполнения на втором станке

Приведём реализацию самого алгоритма:

  • [math] \mathtt{J}[/math] — список работ, которые надо выполнить,
  • [math] \mathtt{List1}[/math], [math] \mathtt{List2} [/math] — списки, в которые будем записывать порядок выполнения работ.
// Функция принимает список работ J и возвращает список с расписанием работ.
function scheduling([math]J[/math]: List<Job>): List<int> 
    [math] \mathtt{List1} = \varnothing [/math]
    [math]\mathtt{List2} = \varnothing [/math]
    while [math]J \ne \varnothing [/math] 
        [math]I[/math] = работа с минимальным значением [math]\min(p_1, \ \ p_2)[/math]
        if [math]p_1 \leqslant p_2[/math]
            [math] \mathtt{List1} = \mathtt{List1} \cup  I [/math]
        else 
            [math]\mathtt{List2} = I \cup  \mathtt{List2} [/math]
        [math]J = J \setminus I [/math]
    return [math]\mathtt{List1} \cup  \mathtt{List2} [/math]

Задача Джонсона о двух станках с прерываниями [math]F_2 \mid pmtn \mid C_{max}[/math]

Теорема:
Оптимальное решение этой задачи совпадает с решением задачи [math]F_2 \mid \mid C_{max}[/math], приведённой выше.
Доказательство:
[math]\triangleright[/math]

Пусть у нас есть оптимальное расписание для задачи [math]F_2 \mid pmtn \mid C_{max}[/math]. Покажем, что его за конечное число шагов можно преобразовать к расписанию без прерываний, не изменив при это значение [math]C_{max}[/math] .

Рассмотрим первую машину. Допустим, что некоторая работа [math] J [/math] выполняется в [math] 2 [/math] или более разных промежутка времени. Тогда передвинем более ранний промежуток вправо по оси времени так, чтоб он заканчивался в тот момент, когда начинается второй промежуток, при этом работы, которые были между этими двумя промежутками, сдвинем влево на длину первого промежутка. Расписание при этом осталось корректным, так как работы на машинах по-прежнему не пересекаются, и каждая работа на второй машине делается после того, как она сделана на первой: работа [math] J [/math] может начать выполняться на второй машине только после того, как она целиком выполнится на первой, то есть уже после конца второго промежутка; а время окончания выполнения остальных работ на первой машине неувеличилось. Важно, что подобная операция не увеличивает [math] C_{max} [/math].

Будем повторять эту операцию до тех пор, пока на первой машине все работы не станут выполняться без прерываний. Так как количество прерываний конечно, а такая операция уменьшает их количество на один, этот процесс конечен.

Теперь избавимся от прерываний на второй машине. Точно так же рассмотрим работу, разбитую на два или более промежутка. Передвинем более поздний промежуток к концу более раннего, а работы между ними сдвинем вправо. Доказательство корректности измененного расписания аналогично доказательству для первой машины. Будем повторять данную операцию, пока на второй машине присутствуют прерывания.

Таким образом, мы получили корректное расписание без прерываний, не изменив при этом значение [math]C_{max}[/math].
[math]\triangleleft[/math]

См. также

Примeчания

  1. Доказательство описано в книге Scheduling Algorithms, Peter Brucker на страницах 174 — 178.