Главная Случайная страница


Категории:

ДомЗдоровьеЗоологияИнформатикаИскусствоИскусствоКомпьютерыКулинарияМаркетингМатематикаМедицинаМенеджментОбразованиеПедагогикаПитомцыПрограммированиеПроизводствоПромышленностьПсихологияРазноеРелигияСоциологияСпортСтатистикаТранспортФизикаФилософияФинансыХимияХоббиЭкологияЭкономикаЭлектроника






Последовательные многостадийные обслуживающие системы. Моделирование на смешанных сетях.

Задача синтеза расписаний для подобных систем является NP-полной и именуется JobShop (JS). Рассмотрим многостадийную обслуживающую систему, состоящую из K различных приборов, которая обслуживает J заявок. Маршруты обслуживания заявок приборами фиксированы, но различны. Длительность обслуживания каждой заявки каждым прибором также различна. Одновременно одним прибором может обслуживаться только одна заявка. Прерываний обслуживания не допускается. Дисциплина обслуживания очередей – произвольная. Введем обозначения:

A - мн-во элементарных операций, U – множество следования операций, V – мн-во условий неодновременности выполнения операций. G=(A,U,V) – смешанный граф с множеством вершин A, множеством дуг U и множеством ребер V. При замене ребра дугой устанавливается отношение следования между двумя операциями. В случае графического решения используем метод критического пути. Однако, несмотря на легкость данного метода, аналитическое представление играет главенствующую роль.



Модификации метода ветвей и границ оптимизации расписаний последовательных многостадийных обслуживающих систем (JSP)

Uij – дуга, соединяющая операции i и j. Vij – ребро между операциями. Wij = ij – пара дуг, заменяющие ребро. Задача состоит в нахождении такого мн-ва W*, которое определяет расписание мин. длины. Применим для этого метод ветвей и границ А11:

1) Строим смешанный сетевой граф и задаем начальное значение № шага алгоритма.

2) Ранжируем ребра по убывания конфликтности. Отбрасываем все ребра сети G. Получаемый при этом граф является временной моделью. Его расписание не является допустимым, но оно будет первоначальной оценкой нижней границы решения исходной задачи. Пишем данную оценку в корне дерева решений.

3) Увеличиваем номер шага алгоритма. Выбираем ребро V и заменяем его парой дуг Wij, ij, каждая из которых добавляется к текущей ослабленной задаче. В результате образуется пара новых подзадач.

4) Методом критического пути вычисляем нижние оценки каждой из подзадач, используя Подзадача соответствующая наименьшей нижней оценке может оказаться противоречивой (циклы в модели)

5) Подзадача, соответствующая наименьшей нижней оценке, проверяется на оптимальность. При оптимальном решении процесс завершается (переходим к п.7), иначе переходим к п. 6.

6) Выбираем решение для ветвления. Подзадача, соответствующая нижней оценке, выбирается для дальнейшего ветвления, затем переходим к п.3. Если список вершин пуст, исходная задача решения не имеет и переходим к п.7.

Рассмотрим другой А22 алгоритм. При замене ребра парой дуг мы производим выбор из альтернативных ограничений:

1) Задаем начальное значение шага алгоритма равное 0

2) Ранжируем ребра по убывания конфликтности. Отбрасываем все ребра сети G. Получаемый при этом граф является временной моделью. Его расписание не является допустимым, но оно будет первоначальной оценкой нижней границы решения исходной задачи. Пишем данную оценку в корне дерева решений.

3) Увеличиваем шаг алгоритма. Единственное условие заменяем парой альтернативных условий. В дереве решений создаются 2 вершины.

4) Любым методом ЛП находим опт. решения, вычисляем нижние оценки длины расписания для каждой подзадачи. Запоминаем оценки в созданных вершинах дерева.

5) Подзадача, соответствующая наименьшей нижней оценке, проверяется на оптимальность, которая достигается при исчерпании множества V для такой вершины. При оптимальном решении процесс завершается (переходим к п.7), иначе переходим к п.6.

6) Выбор вершины для ветвления. Подзадача, соответствующая наименьшей нижней оценке, выбирается для дальнейшего ветвления, после чего осуществляется переход к п. 6.


 

Последнее изменение этой страницы: 2016-06-09

lectmania.ru. Все права принадлежат авторам данных материалов. В случае нарушения авторского права напишите нам сюда...