Оптимизация последовательности обработки деталей на двух станках

1. Оптимизация последовательности обработки деталей на двух станках

Задача Джонсона

2. Содержательная постановка задачи.

На конвейере, состоящем из
транспортера и двух станков
«А» и «В» следует за
минимальное время
обработать n деталей. Каждая
деталь обрабатывается
сначала на станке «А», а затем
на станке «В», причем известно
время обработки каждой
детали на каждом станке.

3. Форма представления исходных данных и графики Ганта

Конвейер
Таблица
Графики Ганта

4. Обозначения, используемые в формальной постановке задачи

t iAH
Обозначения, используемые в
формальной постановке задачи
t iAH - начало обработки i –ой детали на станке А;
t iAK
- завершение обработки i –ой детали на станке А;
t iBH - начало обработки i –ой детали на станке В.
t iBK
- завершение обработки i –ой детали на станке В;
tiA
- время обработки i –ой детали на станке А;
t iB
- время обработки i –ой детали на станке В;

5. Формальная постановка задачи

max max t iK,C min; - минимизация времени обработки всей партии
i 1, 2,... C A, B
t iK, A t iH, A t i , A ; i 1,2,..., n; - время обработки i - ой детали на станке А;
t iK, B t iH, B t i , B ; i 1,2,..., n; - время обработки i - ой детали на станке В
H
K
i j , t i , B t i , A ; - последовательность обработки детали i на станках А и В
H
H
i j , t i ,C t j ,C ; C A, B
i j , t H t H t K t H ; C A, B;
i ,C
j ,C
i ,C
j ,C
i, t H 0; t K 0; C A, B. - неотрицательность переменных
i ,C
i ,C

6. Блок – схема алгоритма поиска оптимального упорядочения П. (алгоритм Джонсона).

Ввод времен
3 обработки
дет. tia и tiв
Ввод числа
2 деталей n
1
4 k=1
5
начало
6
10 k=k+1
9 П(k)=l
q=n
Выбор минимального элемента t(p,l)
да 7 t(p,l)=
нет
нет
да
да
8
p=1
11
П(q)=l
16 печать П, конец
нет
15
k>q
14
t(2,l)=
13
t(1,l)=
12 q=q-1

7. Пример

Последовательность итераций
После получения перестановки П строится график Ганта:

8. САМОСТОЯТЕЛЬНО

Решить задачу Джонсона для
двух станков и пяти деталей:
i
1
2
3
4
5
tiA
9
1
5
10
4
t iB
3
7
2
6
8
Определить время обработки
этой партии деталей с
помощью графика Ганта