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

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

A = (a1, a2, …, an) по ресурсам (рабочим местам, расположенным в линию). Известны τi и множество предшествующих ей работ.

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

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

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

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

T=max1≤u1≤u2≤n [ ∑ u1k=1 τikA + ∑u2k=u1 τikB + ∑u3k=u2 τikC ] (1)

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

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

TA(π) = ∑rk=1 τikA (2)

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

TB(π) = max1≤ur [ ∑uk=1 τikA + ∑rk=u τikB ] (3)

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

TC(π) = max1≤ur [ ∑u1k=1 τikA + ∑u2k=u1 τikB + ∑rk=u2 τikC ] (4)

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

TA(π)+ ∑kЄA\A* τAk + min kЄA\A*Bk + τCk)

γ(π) = TB(π) + ∑kЄA\A* τBk + min kЄA\A* τCk (5)

TC(π) + ∑kЄA\A* τCk

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

Пример.Построить оптимальное по быстродействию расписание выполнения совокупности работ A=(a1, a2, a3, a4, a5 ) на ресурсах A, B, C. Времена выполнения каждой работы на каждом ресурсе приведены в таблице

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

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

γA(a1)= 5 + (4+7+2+3) + (1 + 1)=23;

γB(a1)= (5+8) + (4+1+8+1) + 1 =28;

γC(a1)= (5 + 8 + 1) + (9 + 4 + 4 +1)= 32.

Из них выбирается максимальная: γ(a1) = γC(a1)=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(ak)=29

в качестве 1-го элемента перестановки выбирается работа a4. Аналогичным образом выбираются 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=(a1, a2, a3, a4, a5 ) на ресурсах A, B, C. Времена выполнения каждой работы на каждом ресурсе приведены в таблице для каждого варианта.

№ 1
Тест№5. Теория расписаний. Задача распределения - student2.ru k Тест№5. Теория расписаний. Задача распределения - student2.ru 1 Тест№5. Теория расписаний. Задача распределения - student2.ru 2 Тест№5. Теория расписаний. Задача распределения - student2.ru 3 Тест№5. Теория расписаний. Задача распределения - student2.ru 4 Тест№5. Теория расписаний. Задача распределения - student2.ru 5
Тест№5. Теория расписаний. Задача распределения - student2.ru Ak
Тест№5. Теория расписаний. Задача распределения - student2.ru Bk
Тест№5. Теория расписаний. Задача распределения - student2.ru Ck
№2
Тест№5. Теория расписаний. Задача распределения - student2.ru k Тест№5. Теория расписаний. Задача распределения - student2.ru 1 Тест№5. Теория расписаний. Задача распределения - student2.ru 2 Тест№5. Теория расписаний. Задача распределения - student2.ru 3 Тест№5. Теория расписаний. Задача распределения - student2.ru 4 Тест№5. Теория расписаний. Задача распределения - student2.ru 5
Тест№5. Теория расписаний. Задача распределения - student2.ru Ak
Тест№5. Теория расписаний. Задача распределения - student2.ru Bk
Тест№5. Теория расписаний. Задача распределения - student2.ru Ck
№3
Тест№5. Теория расписаний. Задача распределения - student2.ru k Тест№5. Теория расписаний. Задача распределения - student2.ru 1 Тест№5. Теория расписаний. Задача распределения - student2.ru 2 Тест№5. Теория расписаний. Задача распределения - student2.ru 3 Тест№5. Теория расписаний. Задача распределения - student2.ru 4 Тест№5. Теория расписаний. Задача распределения - student2.ru 5
Тест№5. Теория расписаний. Задача распределения - student2.ru Ak
Тест№5. Теория расписаний. Задача распределения - student2.ru Bk
Тест№5. Теория расписаний. Задача распределения - student2.ru Ck
№4
Тест№5. Теория расписаний. Задача распределения - student2.ru k Тест№5. Теория расписаний. Задача распределения - student2.ru 1 Тест№5. Теория расписаний. Задача распределения - student2.ru 2 Тест№5. Теория расписаний. Задача распределения - student2.ru 3 Тест№5. Теория расписаний. Задача распределения - student2.ru 4 Тест№5. Теория расписаний. Задача распределения - student2.ru 5
Тест№5. Теория расписаний. Задача распределения - student2.ru Ak
Тест№5. Теория расписаний. Задача распределения - student2.ru Bk
Тест№5. Теория расписаний. Задача распределения - student2.ru Ck
№ 5
Тест№5. Теория расписаний. Задача распределения - student2.ru k Тест№5. Теория расписаний. Задача распределения - student2.ru 1 Тест№5. Теория расписаний. Задача распределения - student2.ru 2 Тест№5. Теория расписаний. Задача распределения - student2.ru 3 Тест№5. Теория расписаний. Задача распределения - student2.ru 4 Тест№5. Теория расписаний. Задача распределения - student2.ru 5
Тест№5. Теория расписаний. Задача распределения - student2.ru Ak
Тест№5. Теория расписаний. Задача распределения - student2.ru Bk
Тест№5. Теория расписаний. Задача распределения - student2.ru Ck
№ 6
Тест№5. Теория расписаний. Задача распределения - student2.ru k Тест№5. Теория расписаний. Задача распределения - student2.ru 1 Тест№5. Теория расписаний. Задача распределения - student2.ru 2 Тест№5. Теория расписаний. Задача распределения - student2.ru 3 Тест№5. Теория расписаний. Задача распределения - student2.ru 4 Тест№5. Теория расписаний. Задача распределения - student2.ru 5
Тест№5. Теория расписаний. Задача распределения - student2.ru Ak
Тест№5. Теория расписаний. Задача распределения - student2.ru Bk
Тест№5. Теория расписаний. Задача распределения - student2.ru Ck
№ 7
Тест№5. Теория расписаний. Задача распределения - student2.ru k Тест№5. Теория расписаний. Задача распределения - student2.ru 1 Тест№5. Теория расписаний. Задача распределения - student2.ru 2 Тест№5. Теория расписаний. Задача распределения - student2.ru 3 Тест№5. Теория расписаний. Задача распределения - student2.ru 4 Тест№5. Теория расписаний. Задача распределения - student2.ru 5
Тест№5. Теория расписаний. Задача распределения - student2.ru Ak
Тест№5. Теория расписаний. Задача распределения - student2.ru Bk
Тест№5. Теория расписаний. Задача распределения - student2.ru Ck
№ 8
Тест№5. Теория расписаний. Задача распределения - student2.ru k Тест№5. Теория расписаний. Задача распределения - student2.ru 1 Тест№5. Теория расписаний. Задача распределения - student2.ru 2 Тест№5. Теория расписаний. Задача распределения - student2.ru 3 Тест№5. Теория расписаний. Задача распределения - student2.ru 4 Тест№5. Теория расписаний. Задача распределения - student2.ru 5
Тест№5. Теория расписаний. Задача распределения - student2.ru Ak
Тест№5. Теория расписаний. Задача распределения - student2.ru Bk
Тест№5. Теория расписаний. Задача распределения - student2.ru Ck
№ 9
Тест№5. Теория расписаний. Задача распределения - student2.ru k Тест№5. Теория расписаний. Задача распределения - student2.ru 1 Тест№5. Теория расписаний. Задача распределения - student2.ru 2 Тест№5. Теория расписаний. Задача распределения - student2.ru 3 Тест№5. Теория расписаний. Задача распределения - student2.ru 4 Тест№5. Теория расписаний. Задача распределения - student2.ru 5
Тест№5. Теория расписаний. Задача распределения - student2.ru Ak
Тест№5. Теория расписаний. Задача распределения - student2.ru Bk
Тест№5. Теория расписаний. Задача распределения - student2.ru Ck
№ 10
Тест№5. Теория расписаний. Задача распределения - student2.ru k Тест№5. Теория расписаний. Задача распределения - student2.ru 1 Тест№5. Теория расписаний. Задача распределения - student2.ru 2 Тест№5. Теория расписаний. Задача распределения - student2.ru 3 Тест№5. Теория расписаний. Задача распределения - student2.ru 4 Тест№5. Теория расписаний. Задача распределения - student2.ru 5
Тест№5. Теория расписаний. Задача распределения - student2.ru Ak
Тест№5. Теория расписаний. Задача распределения - student2.ru Bk
Тест№5. Теория расписаний. Задача распределения - student2.ru Ck
№ 11
Тест№5. Теория расписаний. Задача распределения - student2.ru k Тест№5. Теория расписаний. Задача распределения - student2.ru 1 Тест№5. Теория расписаний. Задача распределения - student2.ru 2 Тест№5. Теория расписаний. Задача распределения - student2.ru 3 Тест№5. Теория расписаний. Задача распределения - student2.ru 4 Тест№5. Теория расписаний. Задача распределения - student2.ru 5
Тест№5. Теория расписаний. Задача распределения - student2.ru Ak
Тест№5. Теория расписаний. Задача распределения - student2.ru Bk
Тест№5. Теория расписаний. Задача распределения - student2.ru Ck
№ 12
Тест№5. Теория расписаний. Задача распределения - student2.ru k Тест№5. Теория расписаний. Задача распределения - student2.ru 1 Тест№5. Теория расписаний. Задача распределения - student2.ru 2 Тест№5. Теория расписаний. Задача распределения - student2.ru 3 Тест№5. Теория расписаний. Задача распределения - student2.ru 4 Тест№5. Теория расписаний. Задача распределения - student2.ru 5
Тест№5. Теория расписаний. Задача распределения - student2.ru Ak
Тест№5. Теория расписаний. Задача распределения - student2.ru Bk
Тест№5. Теория расписаний. Задача распределения - student2.ru Ck
№ 13
Тест№5. Теория расписаний. Задача распределения - student2.ru k Тест№5. Теория расписаний. Задача распределения - student2.ru 1 Тест№5. Теория расписаний. Задача распределения - student2.ru 2 Тест№5. Теория расписаний. Задача распределения - student2.ru 3 Тест№5. Теория расписаний. Задача распределения - student2.ru 4 Тест№5. Теория расписаний. Задача распределения - student2.ru 5
Тест№5. Теория расписаний. Задача распределения - student2.ru Ak
Тест№5. Теория расписаний. Задача распределения - student2.ru Bk
Тест№5. Теория расписаний. Задача распределения - student2.ru Ck
№ 14
Тест№5. Теория расписаний. Задача распределения - student2.ru k Тест№5. Теория расписаний. Задача распределения - student2.ru 1 Тест№5. Теория расписаний. Задача распределения - student2.ru 2 Тест№5. Теория расписаний. Задача распределения - student2.ru 3 Тест№5. Теория расписаний. Задача распределения - student2.ru 4 Тест№5. Теория расписаний. Задача распределения - student2.ru 5
Тест№5. Теория расписаний. Задача распределения - student2.ru Ak
Тест№5. Теория расписаний. Задача распределения - student2.ru Bk
Тест№5. Теория расписаний. Задача распределения - student2.ru Ck
№ 15
Тест№5. Теория расписаний. Задача распределения - student2.ru k Тест№5. Теория расписаний. Задача распределения - student2.ru 1 Тест№5. Теория расписаний. Задача распределения - student2.ru 2 Тест№5. Теория расписаний. Задача распределения - student2.ru 3 Тест№5. Теория расписаний. Задача распределения - student2.ru 4 Тест№5. Теория расписаний. Задача распределения - student2.ru 5
Тест№5. Теория расписаний. Задача распределения - student2.ru Ak
Тест№5. Теория расписаний. Задача распределения - student2.ru Bk
Тест№5. Теория расписаний. Задача распределения - student2.ru Ck
№ 16
Тест№5. Теория расписаний. Задача распределения - student2.ru k Тест№5. Теория расписаний. Задача распределения - student2.ru 1 Тест№5. Теория расписаний. Задача распределения - student2.ru 2 Тест№5. Теория расписаний. Задача распределения - student2.ru 3 Тест№5. Теория расписаний. Задача распределения - student2.ru 4 Тест№5. Теория расписаний. Задача распределения - student2.ru 5
Тест№5. Теория расписаний. Задача распределения - student2.ru Ak
Тест№5. Теория расписаний. Задача распределения - student2.ru Bk
Тест№5. Теория расписаний. Задача распределения - student2.ru Ck
№ 17
Тест№5. Теория расписаний. Задача распределения - student2.ru k Тест№5. Теория расписаний. Задача распределения - student2.ru 1 Тест№5. Теория расписаний. Задача распределения - student2.ru 2 Тест№5. Теория расписаний. Задача распределения - student2.ru 3 Тест№5. Теория расписаний. Задача распределения - student2.ru 4 Тест№5. Теория расписаний. Задача распределения - student2.ru 5
Тест№5. Теория расписаний. Задача распределения - student2.ru Ak
Тест№5. Теория расписаний. Задача распределения - student2.ru Bk
Тест№5. Теория расписаний. Задача распределения - student2.ru Ck
№ 18
Тест№5. Теория расписаний. Задача распределения - student2.ru k Тест№5. Теория расписаний. Задача распределения - student2.ru 1 Тест№5. Теория расписаний. Задача распределения - student2.ru 2 Тест№5. Теория расписаний. Задача распределения - student2.ru 3 Тест№5. Теория расписаний. Задача распределения - student2.ru 4 Тест№5. Теория расписаний. Задача распределения - student2.ru 5
Тест№5. Теория расписаний. Задача распределения - student2.ru Ak
Тест№5. Теория расписаний. Задача распределения - student2.ru Bk
Тест№5. Теория расписаний. Задача распределения - student2.ru Ck
№ 19
Тест№5. Теория расписаний. Задача распределения - student2.ru k Тест№5. Теория расписаний. Задача распределения - student2.ru 1 Тест№5. Теория расписаний. Задача распределения - student2.ru 2 Тест№5. Теория расписаний. Задача распределения - student2.ru 3 Тест№5. Теория расписаний. Задача распределения - student2.ru 4 Тест№5. Теория расписаний. Задача распределения - student2.ru 5
Тест№5. Теория расписаний. Задача распределения - student2.ru Ak
Тест№5. Теория расписаний. Задача распределения - student2.ru Bk
Тест№5. Теория расписаний. Задача распределения - student2.ru Ck

Наши рекомендации