36.Задача двух станков и ее решение

Дано два рабочих места, nдеталей.

Первая операция продолжительностью a_i– на первом рабочем месте.

Вторая операция продолжительностью b_i– на втором рабочем месте.

Надо определить детали в той последовательности, чтобы общая продолжительность обработки была минимальной.

Пример:

i	1	2	3	4	5	6
Ai	3	1	3	2	5	3
Bi	2	2	3	1	4	4

График Гантта:

1стан. 1 2 3 4 5 6

2 стан. 1 2 3 4 5 6

Или можно построить граф:

0 3 4 7 9 14 17

3 5 7 10 11 18 22

• Операция выполняется без перерывов.

• Следующая операция может начаться только после окончания предыдущей.

• Две операции одновременно на рабочем месте выполняться не могут.

• Расписание является плотным, т.к. необоснованных перерывов не может быть.

Следовательно, можно найти оптимальную перестановку.

Последовательность обработки операций на 1 станке и на 2 станке одинакова в оптимальном решении, т.е.:

i j

i j

Не может быть так:

i j

j i

Это справедливо только для задач двух и трех станков (не более).

Выведем правило поиска оптимального решения.

Оптимальное расписание:

i j

i j

τ

Δ

Неоптимальное расписание:

j i

j i

Оптимальное решение:

- это время окончания обработкиj-ой детали на втором станке.

Пусть

Тогда

В перестановочном решении эта формула будет иметь вид:

Получим:

(1)

Рассмотрим три случая, когда должно выполняться это неравенство.

1.a_i<=b_i

Для них выполняется правило кратчайшей операции: a_i → min a_i. Первой будет обрабатываться деталь с кратчайшей первой операцией.

Если a_i<=b_i, то выбираем ту операцию, которая будет меньше (a_i<=a_j).

2.a_i>b_i

Выбираем ту, которая короче (b_j<b_i) – по правилу: последней будет обрабатываться деталь с кратчайшей второй операцией.

3. a_i<=b_i; a_i>b_i

В этом случае автоматически выполняется неравенство (1).

Проще говоря: выбираем самую короткую операцию, если она на первом станке, то ставим ее в начало, если она на втором станке, то ставим ее в конец.

Правило предпочтения: если есть множество конкурентов быть первыми, то выбрать тот, у которого минимально a_i и максимально b_i.

Оптимальное решение в примере - (2,3,6,5,1,4):

19

При решении более сложных задач задача о двух станках выступает как вспомогательная.

37.Задача трех станков и методы ее решения