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

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

Содержательный ответ:

Использование декомпозиции позволяет добиться приемлемой трудоемкости при решении реальных задач календарного планирования.

Предварительно определяется разбиение множества ребер (конфликтов) смешанной сети G на упорядоченный ряд подмножеств , то есть определяется количество подмножеств, количество и состав элементов каждого подмножества. Здесь рассмотрим два варианта:

1. Подмножества не пересекаются, тогда число элементов подмножества можно определить как целую часть частного от деления максимального индекса ребра на число подмножеств (можно считать целым среднего арифметического от числа ребер, если я правильно поняла). Для последнего подмножества Q число элементов тогда определится как оставшееся после выделения Q-1 подмножества число ребер.

2. Подмножества пересекаются. Тогда число элементов для разных подмножеств различно, а само разбиение может быть адаптивным.

Рассмотрим второй вариант. Включать ребра в подмножество можно двумя способами:

1. В порядке следования операций в М

2. В соответствии с рангами ребер (см. вопрос 8, ранжирование ребер)

Декомпозиционный алгоритм (рассмотрен сразу как для графического, так и для аналитического представления задачи):

1. Аналитика: Формируем задачу в постановке вопроса 7 по исходным данным (матрице маршрутов и матрице длительности обработки). Графика: По матрице маршрутов и матрице длительности обработки строим смешанный граф (используем все вершины, все дуги и все ребра).

2. На каждом этапе рассматривается одно подмножество ограничений неодновременности (подмножество ребер). Аналитика: Определяем очередное подмножество ограничений неодновременности, т.е. подзадачу в постановке вопроса 7. Графика: Определяем очередное подмножество ребер и подграф (в нем используем все вершины А, все дуги с предыдущего этапа и ребра из текущего подмножества). На начальном этапе из дуг подграф содержит только исходные дуги, которые строятся по матрице маршрутов. Далее при рассмотрении каждого подмножества ребер ребра заменяются дугами, эти дуги на следующем этапе включаются в новый подграф.

3. Аналитика: Находим оптимальное решение текущей подзадачи по одному из алгоритмов вопроса 8, добавляем определившиеся ограничения предшествования-следования (получающиеся при разрешении конфликтов, т.е. вместо ограничений неодновременности) в состав ограничений. Графика: Используя все вершины, а также дуги с первого по текущий этап (исходные дуги и дуги, заменившие ребра при рассмотрении подмножеств с первого по текущее), строим временнУю модель (подграф). Если удалены все ограничения неодновременности (все ребра заменены дугами, т.е рассмотрены все подмножества ребер), найдено оптимальное решение (построена оптимальная временнАя модель). Если нет, возвращаемся к п.2

10. Многостадийные параллельно-последовательные обслуживающие системы. Подходы к формализации задач управления.

Прим.:

1. Параллельная организация каналов – организация, при которой система имеет несколько каналов, все каналы обслуживания предлагают одни и те же услуги, и, следовательно, одновременно могут обслуживаться несколько заявок.

2. Последовательная организация каналов – организация, при которой система обслуживания может состоять из нескольких разнотипных каналов обслуживания, через которые должно пройти каждое обслуживаемое требование.

3. Последовательно-параллельная организация каналов облуживания – это сочетание последовательной и параллельной организации каналов.

4. Многостадийная система – система, содержащая в себе p количество подсистем, каждая из которых содержит в себе I кол-во каналов обслуживания (приборов).

Условия (2.12)–(2.19) содержат рекурсивные функции, при раскрытии которых любая задача, подобная (2.7)–(2.20), редуцируется в задачу частично целочисленного линейного программирования сверхбольшой размерности. Такая размерность ранее признана неразрешимой для объектов с реальными характеристиками размерности. Поэтому определение оптимальных расписаний посредством прямого применения глобальной модели ППОС (2.7)–(2.19) пока невозможно даже теоретически. Имеют смысл лишь отдельные локализации(2.7)–(2.20).

ПОДХОДЫ К ФОРМАЛИЗАЦИИ ЗАДАЧ УПРАВЛЕНИЯ.

Прим. Для решения данной задачи используются прямой и декомпозиционный алгоритм решения ЗТР ППОС.

Прим. Возможно, это не понадобится, но на всякий случай, для справки, немного о прямом алгоритме А2.4.

Содержательный ответ:

Неформальная постановка задачи была в вопросе 1. Длина технологических маршрутов (число операций) может быть разным для разных маршрутов.

Формальная постановка задачи опирается на постановку задачи в вопросе 2 (оптимизация расписаний параллельной системы с задержками поступления заявок) и постановку задачи в вопросе 7 (синтез оптимальных расписаний для последовательных многостадийных обслуживающих систем, Job Shop). То есть, мы идем по пунктам, описанным в вопросе 1.

2.7 Используется булева переменная назначения заявки j на прибор i подсистемы p на шаге динамической модели q при обращении k заявки j к подсистему p (1 — назначено, 0 — не назначено)

2.8 Каждая заявка (на шаге q при обращении k к подсистеме p) назначается только на один прибор i подсистемы p.

2.9 Количество назначений заявок на один прибор подсистемы p (на шаге q при обращении k к подсистеме p) ограничено сверху и снизу

2.10 вводятся неотрицательные компенсационные переменные (смысл — фактическое время ожидания заявкой j обработки на приборе i подсистемы p на шаге q при обращении k к подсистеме p)

2.11 Фактическая задержка поступления заявки j на прибор i подсистемы p на шаге q при обращении k к подсистеме p равна либо фактической ориентировочной задержке (в случае неотрицательности последней), либо 0. Измеряется от времени окончания обработки на приборе i подсистемы p (на шаге q при обращении k к подсистеме p) предшествующей заявки.

2.12 Вычисляем фактическую ориентировочную задержку поступления заявки j на прибор i подсистемы p на шаге q при обращении k к подсистеме p. На вход подсистемы p на шаге q для каждой заявки j идет расписание (с предыдущего шага), точнее, значение задержки поступления. При этом рассматриваемый прибор i до текущей заявки обрабатывал какие-то другие, суммарное время их обработки равно сумме фактических задержек этих заявок и длительностей их обработки (в рамках прибора i подсистемы p на шаге q при обращении k к подсистеме p). Соответственно, отняв от задержки по расписанию суммарное время обработки предшествующих заявок, получим фактическую ориентировочную задержку (которая может быть любого знака).

2.13 Выходное расписание обслуживания подсистемой p на шаге q заявки j при обращении k определяется суммой по всем приборам i подсистемы p, обрабатывавшим эту заявку, фактической задержки поступления заявки и длительности ее обработки (в рамках прибора i подсистемы p на шаге q при обращении k к подсистеме p)

2.14 Если ориентировочная фактическая задержка меньше 0, это значит, заявке j приходится ждать прибор i. Тогда фактическая задержка равна 0, т.е. вводится компенсационная переменная

2.15 ограничение, задающее непосредственное предшествование-следование двух технологических операций с учетом их фактических задержек по 2.14 и длительности обработки предшествующей операции (две операции обработки заявки j на этапе q — прибором i подсистемы p при обращении k и прибором i’ подсистемы p’ при обращении k’).

2.16 ограничение, задающее непосредственное предшествование-следование двух технологических операций с учетом их фактических задержек по 2.14, длительности обработки предшествующей операции и максимального времени задержки предшествующей операции (две операции обработки заявки j на этапе q — прибором i подсистемы p при обращении k и прибором i’ подсистемы p’ при обращении k’).

2.18 для всех конфликтов (условий неодновременности, связывающих пару технологических операций обработки на приборе i подсистемы p) вводится логическая переменная , разрешающая конфликт и задающая порядок следования двух конфликтующих операций. Здесь 1, когда операция (i, j, p, k) предшествует операции (i, j, p’, k’)

2.17 с помощью логических переменных для каждого конфликта вводится ограничение на порядок следования конфликтующих операций. Ограничение использует штраф, длительности обработки конфликтующих операций и их фактические задержки начала обработки и Например, если операция (i, j, p, k) предшествует операции (i, j, p’, k’), это значит, что последующая операция (i, j, p’, k’) начнет обрабатываться не раньше, чем закончится обработка предыдущей операции (i, j, p, k) с учетом ее фактической задержки начала выполнения (то есть, у последующей операции будет неотрицательная фактическая задержка начала выполнения).

2.19 Суммарное время обработки заявок на приборе i подсистемы p на этапе q (оно вычисляется как сумма длительностей обработки всех принятых заявок и их фактических задержек начала обработки) ограничено сверху числом λ (и так для каждого прибора), λ минимизируется (2.20). Критерий максимального быстродействия (минимаксный).

Мы разбирали, разбирали, наши мозги устали, а теперь грустим, потому что в модели присутствует рекурсия, ее надо раскрывать, что приводит к огромной размерности новой модели (без рекурсии), она будет неразрешимой для объектов с реальными характеристиками размерности. Поэтому определение оптимальных расписаний посредством прямого применения глобальной модели ППОС (2.7)–(2.19) пока невозможно даже теоретически. Имеют смысл лишь отдельные локализации (2.7)–(2.20), одна из которых рассмотрена ниже.