Пример решения задачи Джонсона (задачи о трех станках)

Пусть условия задачи заданы следующей таблицей:

Детали Станки	1	2	3	4
Станок 1	4	8	3	8
Станок 2	10	12	7	9
Станок 3	6	8	4	9

 0-й шаг, когда в последовательности 0 деталей:

Очевидно, что δ_A0 = δ_B0 = δ_C0.

Тогда

δ_A0= 0 +Σ a_i + min (b_i + c_i)=34, по всем i=1,n;

δ_B0= 0 +Σ b_i + min c_i= 42, по всем i=1,n;

δ_C0= 0 +Σ c_i = 27, по всем i=1,n;

Оценим перспективность каждого из подмножеств последовательностей обработки, т.е. для каждого из подмножеств необходимо вычислить их ξ_i, где i=1, 2, 3, 4.

Для i = 1:

A(σ₁) = A(σ_o)+a₁

B(σ₁) = max(A(σ₁),B(σ₀)) + b₁                     

C(σ₁) = max(B(σ₁),C(σ0)) + c₁

δ_A1= A(σ₁) +Σ a_i + min (b_i + c_i), по всем i ≠1;

δ_B1= B(σ₁) +Σ b_i + min c_i , по всем i ≠1;

δ_C1= C(σ₁) +Σ c_i , по всем i ≠1.

В таком случае, введем обозначение

ξ₁ = max(δ_A1, δ_B1, δ_C1) .

Теперь можно сказать, что если обработка деталей начнется с детали № 1, то закончится обработка не ранее чем через ξ₁.

Для i = 2:

A(σ₁) = A(σ_o)+a₂ ;

B(σ₁) = max(A(σ₁),B(σ₀)) + b₂                                                                                       

C(σ₁) = max(B(σ₁),C(σ₀)) + c₂

 

δ_A1= A(σ₁) +Σ a_i + min (b_i + c_i), по всем i ≠1;

δ_B1= B(σ₁) +Σ b_i + min c_i , по всем i ≠1;                                                  

δ_C1= C(σ₁) +Σ c_i , по всем i ≠1.

Найдем maxξ_2.

Аналогично вычисляем для других подмножеств.

Теперь можно сказать, какое подмножество на данном этапе является наиболее перспективным .

Все вычисления удобно проводить в такой таблице:

σk	A(σk)	B(σk)	C(σk)	ξk
	δAk	δBk	δCk

 

 Перспективным является множество 1.

Разбиваем это множество возможных последовательностей обработки на подмножества. В этих подмножествах все последовательности начинаются деталью № 1, а вторые детали у них разные из оставшихся (кроме №1). После вычислений и сравнения оценок множеств получим перспективное множество (последовательность деталей σ₂={1,2}, последовательность обработки, начинающаяся деталями 1,2). И так далее. После выполнения последовательности из четырех шагов , получаем оптимальную последовательность обработки деталей:

σ₅*={3,4,1,2}с наименьшим временем обработки 43 часа.

ттттттттттттт

Варианты задачи Джонсона о трех станках:

1. Решить с помощью табличного редактора Excel

1.                                                                                    

	1	2	3	4
а	20	8	7	15
в	48	18	20	40
с	24	10	6	20

2.

	1	2	3	4
а	20	20	10	6
в	11	12	5	4
с	22	23	12	8

3.

	1	2	3	4
а	4	8	3	8
в	10	12	7	9
с	6	8	4	9

4.

	1	2	3	4
а	1	7	9	5
в	1	2	5	1
с	1	1	4	1

5.

	1	2	3	4
а	20	8	7	15
в	48	18	20	40
с	24	10	6	20

6.

	1	2	3	4
а	4	2	5	5
в	8	5	10	7
с	9	3	6	6

7.

	1	2	3	4
а	10	13	9	8
в	6	7	1	2
с	15	14	5	7

8.

	1	2	3	4
а	12	15	11	10
в	8	9	3	4
с	17	16	7	9

9.

	1	2	3	4
а	15	3	2	10
в	43	13	15	35
с	19	5	1	15

10.

	1	2	3	4
а	17	7	7	6
в	8	9	2	1
с	19	20	9	5

11.

	1	2	3	4
а	2	6	1	6
в	8	10	5	7
с	4	6	2	3

12.

	1	2	3	4
а	13	6	7	8
в	9	4	5	5
с	12	6	8	4

13.

	1	2	3	4
а	6	4	7	7
в	10	7	12	9
с	11	5	8	8

 

14.

	1	2	3	4
а	15	10	10	7
в	8	6	9	10
с	6	7	15	6

15.

	1	2	3	4
а	10	5	5	2
в	3	1	4	5
с	1	2	10	1

16.

	1	2	3	4
а	15	8	9	10
в	11	6	7	7
с	14	8	10	4

17.

	1	2	3	4
а	8	6	11	8
в	5	7	10	4
с	8	9	13	7

18.

	1	2	3	4
а	10	5	7	5
в	5	15	10	7
с	6	10	12	7

19.

	1	2	3	4
а	6	1	3	1
в	1	11	6	3
с	2	6	8	3

20.

	1	2	3	4
а	8	3	5	3
в	3	13	8	5
с	4	8	10	5

 

---

Дата добавления: 2021-01-20; просмотров: 917; Мы поможем в написании вашей работы!

Поделиться с друзьями:

---

---

Мы поможем в написании ваших работ!