Тест№5. Теория расписаний. Задача распределения

Задача состоит в том, чтобы распределить совокупность работ

A = (a₁, a₂, …, a_n) по ресурсам (рабочим местам, расположенным в линию). Известны τ_i и множество предшествующих ей работ.

Критерии: число рабочих мест или время выполнения работ.

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

Для этой цели используется метод ветвей и границ. Рассмотрим на примере трех ресурсов A, B, C.

Общее время выполнения всех работ

T=max_{1≤u1≤u2≤n} [ ∑ ^u1_k=1 τ_ik^A + ∑^u2_k=u1 τ_ik^B + ∑^u3_k=u2 τ_ik^C ] (1)

Здесь k - очередность выполнения работы a_i на каждом из ресурсов: A, B, C.

Ресурс A завершает обслуживание последовательности π из r работ A^* за время

T_A(π) = ∑^r_k=1 τ_ik^A (2)

Ресурс B завершает обслуживание последовательности π из r работ A^* за время

T_B(π) = max_1≤u≤r [ ∑^u_k=1 τ_ik^A + ∑^r_k=u τ_ik^B ] (3)

Ресурс С завершает обслуживание последовательности π из r работ A^* за время

T_C(π) = max_1≤u≤r [ ∑^u1_k=1 τ_ik^A + ∑^u2_k=u1 τ_ik^B + ∑^r_k=u2 τ_ik^C ] (4)

На основе формул (2)-(4) формируется следующая оценка γ(π) времени выполнения работ по ресурсам:

T_A(π)+ ∑_kЄA\A^* τ^A_k + min _kЄA\A^*(τ^B_k + τ^C_k)

γ(π) = T_B(π) + ∑_kЄA\A^* τ^B_k + min _kЄA\A^* τ^C_k (5)

T_C(π) + ∑_kЄA\A^* τ^C_k

Функция γ(π) вычисляется для каждой из оставшихся работ A\A^* на r – том шаге построения перестановки работ. В перестановку включается работа, имеющая значение, меньшее γ(π).

Пример.Построить оптимальное по быстродействию расписание выполнения совокупности работ A=(a_1, a₂, a₃, a₄, a₅ ) на ресурсах A, B, C. Времена выполнения каждой работы на каждом ресурсе приведены в таблице

ak	a1	a2	a3	a4	a5
τAk
τBk
τCk

Процесс решения этой задачи методом ветвей и границ представлен на Рис.1. На первом этапе рассматриваются все пять работ (вершин дерева решения задачи) в качестве 1-го элемента перестановки. Для каждой из них вычисляются оценки γ(a₁) одноэлементной перестановки π=a₁ по формулам (5):

γ_A(a₁)= 5 + (4+7+2+3) + (1 + 1)=23;

γ_B(a₁)= (5+8) + (4+1+8+1) + 1 =28;

γ_C(a₁)= (5 + 8 + 1) + (9 + 4 + 4 +1)= 32.

Из них выбирается максимальная: γ(a₁) = γ_C(a₁)=32. Еюи помечается соответствующая вершина дерева (Рис. 1).

29

32

a1

32

a2

31

a3

34

a4

29

a5

30

a1

33

29

29

30

a2

a3

a5

29

a1

29

a3

29

a5

29

a3

a5

a5

Рис.1.

После вычисления оценок для всех работ по минимальной оценке γ_A(a_k)=29

в качестве 1-го элемента перестановки выбирается работа a₄. Аналогичным образом выбираются 2-й и последующие элементы перестановки π из оставшихся работ.

График Ганта оптимальной последовательности работ (Рис. 2) строится с использованием вышеприведенной таблицы. Каждой работе в графике ставится в соответствие потребляемый ею ресурс A, B, C.

Раб. Сроки

5

*

*

* A

* B

* C

4

*

* A

*

*

*

*

*

* B

*

*

*

* C

3

*

*

*

*

*

*

* A

* B

*

*

*

* C

2

*

*

*

* A

*

*

*

* B

*

*

*

*

*

*

*

*

* C

1

*

*

*

*

*

* A

*

*

*

*

*

*

*

* C

0 5 10 15 20 25 30

Задание

Построить оптимальное по быстродействию расписание выполнения совокупности работ A=(a_1, a₂, a₃, a₄, a₅ ) на ресурсах A, B, C. Времена выполнения каждой работы на каждом ресурсе приведены в таблице для каждого варианта.

№ 1
k	1	2	3	4	5
Ak
Bk
Ck

№2
k	1	2	3	4	5
Ak
Bk
Ck

№3
k	1	2	3	4	5
Ak
Bk
Ck

№4
k	1	2	3	4	5
Ak
Bk
Ck

№ 5
k	1	2	3	4	5
Ak
Bk
Ck

№ 6
k	1	2	3	4	5
Ak
Bk
Ck

№ 7
k	1	2	3	4	5
Ak
Bk
Ck

№ 8
k	1	2	3	4	5
Ak
Bk
Ck

№ 9
k	1	2	3	4	5
Ak
Bk
Ck

№ 10
k	1	2	3	4	5
Ak
Bk
Ck

№ 11
k	1	2	3	4	5
Ak
Bk
Ck

№ 12
k	1	2	3	4	5
Ak
Bk
Ck

№ 13
k	1	2	3	4	5
Ak
Bk
Ck

№ 14
k	1	2	3	4	5
Ak
Bk
Ck

№ 15
k	1	2	3	4	5
Ak
Bk
Ck

№ 16
k	1	2	3	4	5
Ak
Bk
Ck

№ 17
k	1	2	3	4	5
Ak
Bk
Ck

№ 18
k	1	2	3	4	5
Ak
Bk
Ck

№ 19
k	1	2	3	4	5
Ak
Bk
Ck