42
правки
Изменения
м
Эта статья о задачах Flow shop. Для начала дадим Дадим определение этого типа задач:
грамматика
{{Определение
|definition =
Рассмотрим пример: <tex>F \mid p_{ij} = 1 \mid C_{max}</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'''
-------------------------------------------
Заметим, что в данном случае <tex>p_{ij}</tex> может быть равно не только единице, но и константе.
Так же, поскольку работа заканчивает выполняться всегда на последней машине, то для решения задач с <tex>p_{ij} = const</tex> нас интересует порядок выполнения работ только на последнем машине, и , таким образом , задачу можно свести к задаче об одной машине.
Задачи с произвольно заданными временами выполнения работ почти все являются NP-полными трудными и решаются приближённо в случае необходимости.
== <tex>F_2 \mid \mid C_{max}</tex> ==
