Тест№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≤u≤r [ ∑uk=1 τikA + ∑rk=u τikB ] (3) Ресурс С завершает обслуживание последовательности π из r работ A* за время TC(π) = max1≤u≤r [ ∑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. Времена выполнения каждой работы на каждом ресурсе приведены в таблице
Процесс решения этой задачи методом ветвей и границ представлен на Рис.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).
После вычисления оценок для всех работ по минимальной оценке γA(ak)=29 в качестве 1-го элемента перестановки выбирается работа a4. Аналогичным образом выбираются 2-й и последующие элементы перестановки π из оставшихся работ. График Ганта оптимальной последовательности работ (Рис. 2) строится с использованием вышеприведенной таблицы. Каждой работе в графике ставится в соответствие потребляемый ею ресурс A, B, C. Раб. Сроки
0 5 10 15 20 25 30
Задание Построить оптимальное по быстродействию расписание выполнения совокупности работ A=(a1, a2, a3, a4, a5 ) на ресурсах A, B, C. Времена выполнения каждой работы на каждом ресурсе приведены в таблице для каждого варианта.
Популярное: Почему человек чувствует себя несчастным?: Для начала определим, что такое несчастье. Несчастьем мы будем считать психологическое состояние... Организация как механизм и форма жизни коллектива: Организация не сможет достичь поставленных целей без соответствующей внутренней... ©2015-2024 megaobuchalka.ru Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. (676)
|
Почему 1285321 студент выбрали МегаОбучалку... Система поиска информации Мобильная версия сайта Удобная навигация Нет шокирующей рекламы |