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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Initial commit)
 
(F|pij=1|C_max)
Строка 2: Строка 2:
 
{{Определение
 
{{Определение
 
|definition =
 
|definition =
'''Flow shop''' ('''<tex>F_{m}</tex>''' в нотации Грэхема): В системе находится m машин, работающих параллельно. Машины упорядочены. Каждая работа должна быть выполнена сначала на первой машине, потом на второй и т.д. до последней.}}
+
'''Flow shop''' ('''<tex>F_{m}</tex>''' в нотации Грэхема): В системе находится m машин, работающих параллельно. Машины упорядочены. Каждая работа должна быть выполнена последовательно на всех машинах с первой по последнюю.}}
 +
 
 +
Рассмотрим пример:  <tex>F \mid p_{ij} = 1 \mid C_{max}</tex>
 +
 
 +
Допустим у нас <tex>n</tex> работ и <tex>m</tex> машин. В начальный момент времени мы можем начать обрабатывать любую работу на первом станке. В следующий момент на первом машине можно обрабатывать следующую работу, а на второй перейдёт предыдущая работа с перовой машины. И так далее. Таким образом на выполнение всех работ у нас уйдёт <tex>n + m - 1</tex> времени. Проиллюстрируем это диаграммой Гантта: (по горизонтали время, по вертикали машины, в ячейке номер выполняемой работы)
 +
        '''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
 +
 
 +
== См. также ==
 +
* [[Классификация задач]]
 +
* [[Fpij1sumwu|<tex>F \mid p_{ij} = 1 \mid \sum w_i u_i</tex>]]

Версия 20:55, 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] времени. Проиллюстрируем это диаграммой Гантта: (по горизонтали время, по вертикали машины, в ячейке номер выполняемой работы)

        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

См. также