Тест№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. Времена выполнения каждой работы на каждом ресурсе приведены в таблице

Процесс решения этой задачи методом ветвей и границ представлен на Рис.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).

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

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

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

№ 20
k	1	2	3	4	5
Ak
Bk
Ck