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

Материал из Викиконспекты
Перейти к: навигация, поиск
(F|pij=1|C_max)
м (правки)
Строка 6: Строка 6:
 
Рассмотрим пример:  <tex>F \mid p_{ij} = 1 \mid C_{max}</tex>
 
Рассмотрим пример:  <tex>F \mid p_{ij} = 1 \mid C_{max}</tex>
  
Допустим у нас <tex>n</tex> работ и <tex>m</tex> машин. В начальный момент времени мы можем начать обрабатывать любую работу на первом станке. В следующий момент на первом машине можно обрабатывать следующую работу, а на второй перейдёт предыдущая работа с перовой машины. И так далее. Таким образом на выполнение всех работ у нас уйдёт <tex>n + m - 1</tex> времени. Проиллюстрируем это диаграммой Гантта: (по горизонтали время, по вертикали машины, в ячейке номер выполняемой работы)
+
Допустим у нас <tex>n</tex> работ и <tex>m</tex> машин. В начальный момент времени мы можем начать обрабатывать любую работу на первом станке. В следующий момент на первом машине можно обрабатывать следующую работу, а на второй перейдёт предыдущая работа с перовой машины. И так далее. Таким образом на выполнение всех работ у нас уйдёт <tex>n + m - 1</tex> времени. Проиллюстрируем это диаграммой Гантта для случая <tex>n = 6, m = 5</tex>: (по горизонтали время, по вертикали машины, в ячейке номер выполняемой работы)
 
         '''0  1  2  3  4  5  6  7  8  9  10'''
 
         '''0  1  2  3  4  5  6  7  8  9  10'''
 
         -------------------------------------------
 
         -------------------------------------------
Строка 14: Строка 14:
 
   '''M_4'''  |    -  -  -  1  2  3  4  5  6  -
 
   '''M_4'''  |    -  -  -  1  2  3  4  5  6  -
 
   '''M_5'''  |    -  -  -  -  1  2  3  4  5  6
 
   '''M_5'''  |    -  -  -  -  1  2  3  4  5  6
 +
 +
Заметим, что в данном случае <tex>p_{ij}</tex> может быть равно не только единице, но и константе.
 +
 +
Так же, поскольку работа заканчивает выполняться всегда на последней машине, то для решения задач с <tex>p_{ij} = const</tex> нас интересует порядок выполнения работ только на последнем машине.
 +
  
 
== См. также ==
 
== См. также ==
 
* [[Классификация задач]]
 
* [[Классификация задач]]
 
* [[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>]]

Версия 23:21, 21 июня 2012

Эта статья о задачах Flow shop. Для начала дадим определение этого типа задач:

Определение:
Flow shop ([math]F_{m}[/math] в нотации Грэхема): В системе находится m машин, работающих параллельно. Машины упорядочены. Каждая работа должна быть выполнена последовательно на всех машинах с первой по последнюю.


Рассмотрим пример: [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   4   5   6   7   8   9   10
        -------------------------------------------
 M_1   |    1   2   3   4   5   6   -   -   -   -
 M_2   |    -   1   2   3   4   5   6   -   -   -
 M_3   |    -   -   1   2   3   4   5   6   -   -
 M_4   |    -   -   -   1   2   3   4   5   6   -
 M_5   |    -   -   -   -   1   2   3   4   5   6

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

Так же, поскольку работа заканчивает выполняться всегда на последней машине, то для решения задач с [math]p_{ij} = const[/math] нас интересует порядок выполнения работ только на последнем машине.


См. также