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


Категории:

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






Декомпозиционный алгоритм оптимизации расписаний многостадийных параллельно-последовательных обслуживающих систем

Множество ребер V смешанной сети G на ряд подмножествVq. Для этого устанавливается величина Q – кол-во подмножеств. Количество элементов mq подмножеств Vq может быть различным в зависимости от специфики задачи. Множество вершин, инцидентных ребрам из Vq называются q-м слоем сети G, количество элементов подмножества Vq (mq) - толщина слоя q.

Декомпозиционный алгоритм:

1) На исходных данных определяем множество слоев Gq и их толщину (mq) – кол-во элементов подмножества. Задаем начальное значение номера шага алгоритма: q=0.

2) Увеличиваем номер шага алгоритма переходим от множества слоев Gq к множеству слоев Gq+1. Переносим задний ряд элементов слоя, при этом предпоследние становятся последними, а первые исключаются. Переносим передний слой, т.е. к концу добавляем следующего по порядку элемента, если для маршрута j добавляемый элемент не приводит к увеличению длины расписания, иначе добавляемая строка будет эквивалентна последней строке. Наилучшие условия возникают, когда добавляемые вершины приводят в увеличению оценок длины расписания для всех маршрутов одновременно. При этих обстоятельствах исключаются все начальные вершины, а в качестве последнего столбца прибавляются очередные вершины. В противном случае исключаются только отдельные элементы.

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

4) Определяются оптимальные посредством решения задачи о назначениях для включенных в слой Gq операций.

5) Так как в текущем слое Gq определены все назначения и таким образом слой преобразуется в mq – стадийную последовательную обслуживающую систему. Определяем локально оптимальное расписание посредством алгоритма А23.

6) Проверка условия остановки алгоритма. Если текущий слой является последним, то получено локально оптимальное расписание, иначе перейти к п. 2.


Приложение моделей и алгоритмов оптимизации расписаний многостадийных параллельно-последовательных систем.

Рассмотрим второй подход к формализации задачи календарного планирования строительства скважин НГКМ с явным заданием последовательности бурения.

- время начала бурения куста скважин j.

 

Существует два подхода к построению алгоритмов оптимизации расписаний ППОС (параллельно-последовательные обслуживающие системы):

Первый: представление задачи синтеза расписаний в виде смешанной сети специального вида и основываестя на алгоритмах оптимизации расписаний последовательных систем. Наначение заявок на параллельные приборы определяются перебором вариантов. Применим при наличии небольшого кол-ва параллельных приборов. Т.е. ребра мы можем преобразовать в две дуги.

Второй: основа – комплекс моделей оптимизации расписаний парал-ых ОС с задержками гачала обслуживания (А11, А12, А13) и алгоритмов оптимизации расписаний послед-х систем (А22, А23).

 

Пр: Стр-во 7 кустов скважин осущ-ся двумя неидентичными буровыми установками. Время и послед-ть стр-ва приведены в табл. Результаты оптимизации задачи сведены в табл. 2.6. Оптимальный график работы на рис 2.13. Формирование данных модели не требует предварительного разбиения планового периода на этапы и дополнительного оценивания длительностей этих этапов. Однако полученное решение будет грубым приближением. При использовании 2-ого подхода затруднен учет ряда важных обстоятельств. Согласно ему нельзя начинать строительство технологически зависимых скважин до окончания строительства предшествующих кустов. Это не отвечает действительности. В первом подходе это возможно реализовать, которй применим для среднесрочного и оперативного планирования и регулирования процессов обустройства НГКМ. Вместе с тем, первый подход (поэтапный) требует тонких настроек модели и многовариантных модельных расчетов для уточнения длительности этапов (величин исходных задержек начала строительства кустов скважин). Первоначальные оценки длительностей можно получить на основе второго подхода. Таким образом, перечисленные подходы являются сопряженными и взаимно дополняющими друг друга.

 


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

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