Алгоритмическое обеспечение модели планирования и принятия решений - davaiknam.ru o_O
Главная
Поиск по ключевым словам:
Похожие работы
Название работы Кол-во страниц Размер
Трехуровневая модель планирования и принятия решений 5 586.24kb.
Принятие решения в управлении. Модели и процесс принятия управленческих... 1 131.85kb.
Модели принятия решения 1 19.3kb.
Лекция Системы поддержки принятия решений Тем Системы поддержки принятия... 1 100.49kb.
Рабочая учебная программа Выписка из гос 5 904.69kb.
Анализ и разработка схемы принятия решений в организации 1 152.46kb.
«Организация как функция менеджмента» «Модели и методы принятия решений» 1 102.42kb.
Учебное пособие по дисциплине «Математическое моделирование и теория... 8 1149.18kb.
Поддержка принятия решений для управления конкурентоспособностью... 1 58.98kb.
Модели и методы поддержки принятия решений по согласованию показателей... 4 587.06kb.
«Подходы к моделированию проблемных ситуаций принятия решений» 1 334.61kb.
Трехуровневая модель планирования и принятия решений 5 586.24kb.
Направления изучения представлений о справедливости 1 202.17kb.

Алгоритмическое обеспечение модели планирования и принятия решений - страница №1/6


Глава 9Алгоритмическое обеспечение модели планирования и принятия решений

9.1Общая схема реализации алгоритмического обеспечения иерархической модели планирования в сложных системах


В основу планирования функционирования сложных систем положена трехуровневая модель планирования, описанная в параграфе 8.5. Функциональная схема ее реализации представлена ниже на рисунке  9 .2.

Рассмотрим задачу, поставленную в главе 8, и соответствующую ей иерархическую модель планирования. Алгоритмическое обеспечение модели состоит из трех основных блоков, соответствующих трем уровням общей схемы планирования [0].



Блок 1

1. Построение на основе портфеля заказов входной информационной модели – графа заданий G;

2. Построение агрегированного графа взаимосвязи работ G';

3. Определение критических путей заданий;

4. Определение общих вершин на критических путях и построение графа на критических путях заданий GК – агрегированной модели­ первого уровня (с очевидным обобщением на 5 основных критериев оптимальности и 26 комбинированных, см. п. 9.2.2);

5. Построение для каждого из критериев 1–7 (п. 8.5, с обобщением на 31 критерий) аппроксимирующей задачи МВМ. Решение задачи МВМ, в результате которой формируется приоритетно-упорядоченная последовательность выполнения агрегированных работ ОПТ, содержащая вершины графа GК.



Блок 2

6. Предварительное распределение агрегированных работ последовательности ОПТ по мультиресурсам;

7. Переопределение набора общих вершин согласно фактической информации о распределении; если общие вершины не изменились, переход на шаг 9, иначе на шаг 8.

8. Формирование нового графа GН на критических путях заданий в связи с изменением набора общих вершин. Повторное решение задачи МВМ.

9. Дополнение последовательности ОПТ вершинами, не лежащими на критических путях заданий (последовательность *).

10. Распределение агрегированных работ последовательности * для обслуживания их множеством мультиресурсов с привязкой к плановому периоду (согласованное планирование).

11. Блок принятия решений: генерация серии возможных допустимых планов по разным критериям оптимальности в результате многократного выполнения шагов 1–10 и выбор наилучшего плана для передачи на Блок 3. Если план, удовлетворяющий поставленным требованиям, не получен, информация передается на Блок 1 для коррекции модели.

Блок 3

12. Дезагрезация мультиресурсов и агрегированных работ, формирование согласованного плана выполнения работ для каждого ресурса с учетом выбранного критерия оптимизации.

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

На шаге 2 выполняется процедура агрегации для уменьшения размерности начального графа. На этом этапе решаются следующие задачи:



  • выбор приема агрегирования;

  • определение уровня агрегации работ и ресурсов;

  • формирование структуры агрегированных технологических моделей;

  • формирование агрегированных нормативов.

При построении модели технологической агрегации выполня­ется агрегация до уровня мультиресурсов (устойчивая группа совместно работающих ресурсов) и построение агрегированных работ. Входной ацикличный ориентированный граф представляется в виде списка технологических операций (перечня работ) и перечня их взаимосвязей. Технологическая агрегация выполняет объединение в один элемент – агрегированную работу – смежных операций, проводимых в одном и том же мультиресурсе по одному заданию. Длительность выполнения агрегированной работы i-м мультиресурсом определяется ее критическим путем в данном мультиресурсе (формула ( 9 .0), п. 9.2.1).

В результате выполнения шагов 3 и 4 строится граф на критических путях выполнения заданий. Некоторые агрегированные работы, проводимые в мультиресурсах, которые требуют переналадки (подготовительных работ) при выполнении работ с различающимися характеристиками, объединяются по описанным ниже правилам в общие агрегированные работы, если при этом не требуется наладка мультиресурса при переходе от одной работы к другой. Это отображено на графе связности общими вершинами. В этом случае наладка требуется только в начале расписания и каждый раз, когда мультиресурс переключается от выполнения работ в «общей вершине» к выполнению других агрегированных работ.

Для определения очередности назначения заданий на выполнение на построенном графе на критических путях заданий решается задача минимизации суммарного взвешенного момента окончания выполнения работ одним прибором (МВМ) при условии, что веса всех вершин, кроме конечных, равны нулю. Результатом решения этой задачи является приоритетно-упорядоченная последовательность выполнения агрегированных работ ОПТ (шаг 5). С этой целью для каждого из критериев 1–7 (п. 8.5, с обобщением на 31 критерий) строится аппроксимирующая задача МВМ, в которой длительности и веса работ определяются длительностями и весами агрегированных работ в графе на критических путях. Для решения задачи МВМ при условии, что веса всех вершин, кроме конечных, равны нулю, разработан эвристический алгоритм (п. 9.3) на основе ПДС-алгоритма решения задачи минимизации суммарного взвешенного момента окончания выполнения работ одним прибором при отношении порядка, заданном ориентированным ацикличным графом (глава 2).

Полученная в результате решения аппроксимирующей задачи МВМ приоритетно-упорядо­ченная последовательность ОПТ является основной информацией при реализации согласованного планирования функционирования системы. Выполняется двукратное распределение агрегированных работ по мультиресурсам. При первом из них (шаг 6) по мультиресурсам в порядке, заданном последовательностью ОПТ, распределяются все агрегированные работы, лежащие на критических путях заданий. При этом определяются моменты начала выполнения агрегированных работ и привязка их к конкретным мультиресурсам. Общие вершины при распределении представляются в виде последовательности агрегированных работ, входящих в их состав, упорядоченной в соответствии с приоритетами заданий, которым они принадлежат.

Первое распределение служит для определения фактической информации об объединении общих вершин на стадии распределения, т. е. уточнения состава общих вершин (шаг 7). Те вершины, для которых при распределении нарушены правила объединения, исключаются из состава «общих вершин», и наоборот, вершины, для которых в результате распределения выполняются правила объединения, дополнительно включаются в новый состав «общих вершин».

Второе распределение осуществляется на уточненном графе с новым составом общих вершин и может решаться либо на графе на критических путях (шаги 8 и 10) – для определения состава портфеля заказов, либо после дополнения этого графа остальными вершинами, не лежащими на критических путях (шаги 8, 9, 10) – для реализации согласованного планирования. В этом случае агрегированные работы, не лежащие на критических путях, также могут объединяться в общие агрегированные работы, если они выполняются в одном мультиресурсе и моменты начала их выполнения отличаются на величину, меньшую, чем время переналадки в мультиресурсе.

На шаге 11 в блоке принятия решений (п. 9.5) в результате многократного выполнения шагов 1–10 генерируется серия возможных допустимых планов, различающихся конкретным видом критерия, исходными данными и технологией реализации. Осуществляется обоснованный выбор плана выполнения заданий из множества допустимых в условиях неопределенности на основе построения дерева иерархий, что является эффективным способом решения поставленной задачи. В результате выбирается один план, передающийся на шаг 12 для реализации. Если же план, удовлетворяющий поставленным требованиям, не получен, информационная модель первого уровня подвергается корректировке (могут исключаться или добавляться новые задания, приобретаться новое оборудование, изменяться технология выполнения работ и т.п.) и выполняется переход на шаг 2.

На шаге 12 выполняется дезагрезация мультиресурсов и агрегированных работ и формирование согласованного плана выполнения работ для каждого ресурса с учетом выбранного критерия оптимизации (точное планирование). На этом уровне решаются задачи как для одного, так и для параллельных станков в случае независимых или взаимосвязанных заданий по критериям 1–7 с обобщением на 31 критерий.

Таким образом, в процессе решения задачи планирования на основе иерархической модели осуществляется стратегия поиска глобального оптимума, в отличие от существующих методов, основанных на эвристических правилах, что позволяет получить эффективные решения.


следующая страница >>



Критицизм может сделать тебя философом, но только вера может сделать тебя апостолом. Мария Эбнер-Эшенбах
ещё >>