Редактирование: Flow shop

Перейти к: навигация, поиск

Внимание! Вы не авторизовались на сайте. Ваш IP-адрес будет публично видимым, если вы будете вносить любые правки. Если вы войдёте или создадите учётную запись, правки вместо этого будут связаны с вашим именем пользователя, а также у вас появятся другие преимущества.

Правка может быть отменена. Пожалуйста, просмотрите сравнение версий, чтобы убедиться, что это именно те изменения, которые вас интересуют, и нажмите «Записать страницу», чтобы изменения вступили в силу.
Текущая версия Ваш текст
Строка 69: Строка 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 =  
Строка 77: Строка 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,_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-трудными]].
+
Задачи с произвольными временами выполнения работ почти все являются [[NP | NP-трудными]].
  
 
== Задача Джонсона о двух станках <tex>F_2 \mid \mid C_{max}</tex> ==
 
== Задача Джонсона о двух станках <tex>F_2 \mid \mid C_{max}</tex> ==
Строка 85: Строка 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] на страницах 174 {{---}} 178.</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] </ref>.
  
 
Оптимальное расписание для первой и второй машины будет совпадать. Таким образом, нам требуется найти порядок, в котором будут выполняться работы на каждой машине.
 
Оптимальное расписание для первой и второй машины будет совпадать. Таким образом, нам требуется найти порядок, в котором будут выполняться работы на каждой машине.
  
 
===Алгоритм===
 
===Алгоритм===
Обозначим за <tex>p_1</tex> время выполнения работы на первом станке, за <tex>p_2</tex> время выполнения работы на втором станке.
+
Алгоритм такой: возьмём два пустых списка и будем рассматривать работы в порядке возрастания <tex>\min(p_1, p_2)</tex>, то есть, минимума из времён выполнения данной работы на первой и второй машине. Если у работы <tex>p_1 \leqslant p_2</tex>, то добавим её в конец первого списка. В противном случае, добавим её в начало второго списка. Итоговое расписание — это конкатенация первого и второго списков.
 
 
Будем использовать следующий алгоритм: возьмём два пустых списка и будем рассматривать работы в порядке возрастания <tex>\min(p_1, p_2)</tex>, то есть, минимума из времён выполнения данной работы на первой и второй машине. Если у работы <tex>p_1 \leqslant p_2</tex>, то добавим её в конец первого списка. В противном случае, добавим её в начало второго списка. Итоговое расписание — это конкатенация первого и второго списков.
 
  
 
===Псевдокод===
 
===Псевдокод===
Для представления работы в памяти будем использовать следующую структуру:
+
J {{---}} список работ, которые надо выполнить, <tex> \mathrm{FirstList}</tex> и <tex> \mathrm{SecondList} </tex> {{---}} списки, в которые будем записывать порядок выполнения работ.
'''struct''' Job:
+
    <tex>\mathrm{FirstList} = \varnothing </tex>
    '''int''' <tex>p_1</tex>    <font color = green>// Время выполнения на первом станке</font>
+
    <tex>\mathrm{SecondList} = \varnothing </tex>
    '''int''' <tex>p_2</tex>    <font color = green>// Время выполнения на втором станке</font>
+
    '''while''' J <tex> \ne \varnothing </tex>  
 
+
         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> \mathtt{List1} = \mathtt{List1} \cup  I </tex>
+
             <tex>\mathrm{FirstList} = \mathrm{FirstList} \cup  I </tex>
 
         '''else'''  
 
         '''else'''  
             <tex>\mathtt{List2} = I \cup  \mathtt{List2} </tex>
+
             <tex>\mathrm{SecondList} = I \cup  \mathrm{SecondList} </tex>
 
         <tex>J = J \setminus I </tex>
 
         <tex>J = J \setminus I </tex>
    '''return''' <tex>\mathtt{List1} \cup  \mathtt{List2} </tex>
+
    <tex>\mathrm{Result} = \mathrm{FirstList} \cup  \mathrm{SecondList} </tex>
  
 
== Задача Джонсона о двух станках с прерываниями <tex>F_2 \mid pmtn \mid C_{max}</tex> ==
 
== Задача Джонсона о двух станках с прерываниями <tex>F_2 \mid pmtn \mid C_{max}</tex> ==
{{Теорема
+
{{Утверждение
 
|statement= Оптимальное решение этой задачи совпадает с решением задачи <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> .
 
|proof = Пусть у нас есть оптимальное расписание для задачи <tex>F_2 \mid pmtn \mid C_{max}</tex>. Покажем, что его за конечное число шагов можно преобразовать к расписанию без прерываний, не изменив при это значение <tex>C_{max}</tex> .
Строка 129: Строка 117:
 
Теперь избавимся от прерываний на второй машине. Точно так же рассмотрим работу, разбитую на два или более промежутка. Передвинем более поздний промежуток к концу более раннего, а работы между ними сдвинем вправо. Доказательство корректности измененного расписания аналогично доказательству для первой машины. Будем повторять данную операцию, пока на второй машине присутствуют прерывания.
 
Теперь избавимся от прерываний на второй машине. Точно так же рассмотрим работу, разбитую на два или более промежутка. Передвинем более поздний промежуток к концу более раннего, а работы между ними сдвинем вправо. Доказательство корректности измененного расписания аналогично доказательству для первой машины. Будем повторять данную операцию, пока на второй машине присутствуют прерывания.
  
Таким образом, мы получили корректное расписание без прерываний, не изменив при этом значение <tex>C_{max}</tex>.}}
+
Таким образом, мы получили корректное расписание без прерываний, не изменив при этом значение <tex>C_{max}</tex>, что и требовалось доказать.}}
  
 
== См. также ==
 
== См. также ==

Пожалуйста, учтите, что любой ваш вклад в проект «Викиконспекты» может быть отредактирован или удалён другими участниками. Если вы не хотите, чтобы кто-либо изменял ваши тексты, не помещайте их сюда.
Вы также подтверждаете, что являетесь автором вносимых дополнений, или скопировали их из источника, допускающего свободное распространение и изменение своего содержимого (см. Викиконспекты:Авторские права). НЕ РАЗМЕЩАЙТЕ БЕЗ РАЗРЕШЕНИЯ ОХРАНЯЕМЫЕ АВТОРСКИМ ПРАВОМ МАТЕРИАЛЫ!

Чтобы изменить эту страницу, пожалуйста, ответьте на приведённый ниже вопрос (подробнее):

Отменить | Справка по редактированию (в новом окне)

Шаблоны, используемые на этой странице: