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

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

Ausführliche Beschreibung

Gespeichert in:

Bibliographische Detailangaben
Datum:	2009
Hauptverfasser:	Згуровский, М.З., Павлов, А.А.
Format:	Artikel
Sprache:	Russian
Veröffentlicht:	Навчально-науковий комплекс "Інститут прикладного системного аналізу" НТУУ "КПІ" МОН та НАН України 2009
Schriftenreihe:	Системні дослідження та інформаційні технології
Schlagworte:	Проблеми прийняття рішень і управління в економічних, технічних, екологічних і соціальних системах
Online Zugang:	http://dspace.nbuv.gov.ua/handle/123456789/42226
Tags:	Tag hinzufügen Keine Tags, Fügen Sie den ersten Tag hinzu!
Назва журналу:	Digital Library of Periodicals of National Academy of Sciences of Ukraine
Zitieren:	Иерархическое планирование в системах, имеющих сетевое представление технологических процессов и ограниченные ресурсы, как задача принятия решений / М.З. Згуровский, А.А. Павлов // Систем. дослідж. та інформ. технології. — 2009. — № 3. — С. 70–75. — Бібліогр.: 26 назв. — рос.

Institution

Digital Library of Periodicals of National Academy of Sciences of Ukraine

id	irk-123456789-42226
record_format	dspace
spelling	irk-123456789-422262013-03-14T03:08:56Z Иерархическое планирование в системах, имеющих сетевое представление технологических процессов и ограниченные ресурсы, как задача принятия решений Згуровский, М.З. Павлов, А.А. Проблеми прийняття рішень і управління в економічних, технічних, екологічних і соціальних системах Исследуется проблема эффективного планирования в системах с сетевым представлением технологических процессов и ограниченными ресурсами. Обосновывается использование иерархических моделей планирования. Показано, что даже эффективное решение задачи по одному скалярному критерию является лишь начальным этапом реализации эффективного планирования как задачи принятия решений с плохо формализованной глобальной целью. Досліджується проблема ефективного планування в системах з мережним представленням технологічних процесів й обмеженими ресурсами. Обґрунтовується використання ієрархічних моделей планування. Показано, що навіть ефективне розв’язання задачі за одним скалярним критерієм є лише початковим етапом реалізації ефективного планування як задачі прийняття рішень із погано формалізованою глобальною метою. The effective planning problem in systems with network representation of technological processes and limited resources is researched. The use of hierarchic planning models is grounded. It has been shown that even the effective problem solution by one scalar criterion is only the first stage of effective planning realization as a decision making problem with a poorly formalized global goal. 2009 Article Иерархическое планирование в системах, имеющих сетевое представление технологических процессов и ограниченные ресурсы, как задача принятия решений / М.З. Згуровский, А.А. Павлов // Систем. дослідж. та інформ. технології. — 2009. — № 3. — С. 70–75. — Бібліогр.: 26 назв. — рос. 1681–6048 http://dspace.nbuv.gov.ua/handle/123456789/42226 519.854.2 ru Системні дослідження та інформаційні технології Навчально-науковий комплекс "Інститут прикладного системного аналізу" НТУУ "КПІ" МОН та НАН України
institution	Digital Library of Periodicals of National Academy of Sciences of Ukraine
collection	DSpace DC
language	Russian
topic	Проблеми прийняття рішень і управління в економічних, технічних, екологічних і соціальних системах Проблеми прийняття рішень і управління в економічних, технічних, екологічних і соціальних системах
spellingShingle	Проблеми прийняття рішень і управління в економічних, технічних, екологічних і соціальних системах Проблеми прийняття рішень і управління в економічних, технічних, екологічних і соціальних системах Згуровский, М.З. Павлов, А.А. Иерархическое планирование в системах, имеющих сетевое представление технологических процессов и ограниченные ресурсы, как задача принятия решений Системні дослідження та інформаційні технології
description	Исследуется проблема эффективного планирования в системах с сетевым представлением технологических процессов и ограниченными ресурсами. Обосновывается использование иерархических моделей планирования. Показано, что даже эффективное решение задачи по одному скалярному критерию является лишь начальным этапом реализации эффективного планирования как задачи принятия решений с плохо формализованной глобальной целью.
format	Article
author	Згуровский, М.З. Павлов, А.А.
author_facet	Згуровский, М.З. Павлов, А.А.
author_sort	Згуровский, М.З.
title	Иерархическое планирование в системах, имеющих сетевое представление технологических процессов и ограниченные ресурсы, как задача принятия решений
title_short	Иерархическое планирование в системах, имеющих сетевое представление технологических процессов и ограниченные ресурсы, как задача принятия решений
title_full	Иерархическое планирование в системах, имеющих сетевое представление технологических процессов и ограниченные ресурсы, как задача принятия решений
title_fullStr	Иерархическое планирование в системах, имеющих сетевое представление технологических процессов и ограниченные ресурсы, как задача принятия решений
title_full_unstemmed	Иерархическое планирование в системах, имеющих сетевое представление технологических процессов и ограниченные ресурсы, как задача принятия решений
title_sort	иерархическое планирование в системах, имеющих сетевое представление технологических процессов и ограниченные ресурсы, как задача принятия решений
publisher	Навчально-науковий комплекс "Інститут прикладного системного аналізу" НТУУ "КПІ" МОН та НАН України
publishDate	2009
topic_facet	Проблеми прийняття рішень і управління в економічних, технічних, екологічних і соціальних системах
url	http://dspace.nbuv.gov.ua/handle/123456789/42226
citation_txt	Иерархическое планирование в системах, имеющих сетевое представление технологических процессов и ограниченные ресурсы, как задача принятия решений / М.З. Згуровский, А.А. Павлов // Систем. дослідж. та інформ. технології. — 2009. — № 3. — С. 70–75. — Бібліогр.: 26 назв. — рос.
series	Системні дослідження та інформаційні технології
work_keys_str_mv	AT zgurovskijmz ierarhičeskoeplanirovanievsistemahimeûŝihsetevoepredstavlenietehnologičeskihprocessoviograničennyeresursykakzadačaprinâtiârešenij AT pavlovaa ierarhičeskoeplanirovanievsistemahimeûŝihsetevoepredstavlenietehnologičeskihprocessoviograničennyeresursykakzadačaprinâtiârešenij
first_indexed	2025-07-04T00:43:22Z
last_indexed	2025-07-04T00:43:22Z
_version_	1836675028905623552
fulltext	© М.З. Згуровский, А.А. Павлов, 2009 70 ISSN 1681–6048 System Research & Information Technologies, 2009, № 3 TIДC ПРОБЛЕМИ ПРИЙНЯТТЯ РІШЕНЬ І УПРАВЛІННЯ В ЕКОНОМІЧНИХ, ТЕХНІЧНИХ, ЕКОЛОГІЧНИХ І СОЦІАЛЬНИХ СИСТЕМАХ УДК 519.854.2 ИЕРАРХИЧЕСКОЕ ПЛАНИРОВАНИЕ В СИСТЕМАХ, ИМЕЮЩИХ СЕТЕВОЕ ПРЕДСТАВЛЕНИЕ ТЕХНОЛОГИЧЕСКИХ ПРОЦЕССОВ И ОГРАНИЧЕННЫЕ РЕСУРСЫ, КАК ЗАДАЧА ПРИНЯТИЯ РЕШЕНИЙ М.З. ЗГУРОВСКИЙ, А.А. ПАВЛОВ Исследуется проблема эффективного планирования в системах с сетевым представлением технологических процессов и ограниченными ресурсами. Обосновывается использование иерархических моделей планирования. Пока- зано, что даже эффективное решение задачи по одному скалярному критерию является лишь начальным этапом реализации эффективного планирования как задачи принятия решений с плохо формализованной глобальной целью. Эффективное планирование в системах с сетевым представлением техноло- гий и ограниченными ресурсами требует применения системных концепций планирования и управления. Действительно, в классической постановке эф- фективное планирование — это нахождение расписания выполнения работ, которому соответствует минимум некоторого функционала с учетом огра- ничений, задаваемых сетевым представлением технологического процесса. Точная математическая модель такой задачи — многоэтапная задача кален- дарного планирования. Размерность реальных сетевых систем приводит к трансвычислительной сложности обработки информации [1]. Известные эвристические методы решения многоэтапных задач кален- дарного планирования проблему трансвычислительной сложности решают ценой качества (они основаны на линейной или случайной комбинации раз- личных правил предпочтения и оптимизации на шаг вперед, что не гаранти- рует качества полученного решения). Многие исследователи к проблеме эффективного планирования в сетевых системах подходят в первую очередь как к проблеме планирования дискретного производства — мелкосерийного (80% мирового производства), производства на заказ и т.д. В такой постановке задача характеризуется системной сложностью [1] и решается [2, 3] с использованием принципов экономической, технологиче- ской, эргономической, информационной рациональности [1]. В работе [12] с учетом органической связи системной и вычислительной сложности обсуж- даемой проблемы сформулированы и обоснованы требования к математиче- скому обеспечению эффективного планирования в сетевых системах. Иерархическое планирование в системах … как задача принятия решений Системні дослідження та інформаційні технології, 2009, № 3 71 1. Реализация прогрессивной организации производства. 2. Иерархичность планирования. 3. Агрегация и дезагрегация как реализация иерархического планиро- вания. 4. Многокритериальность — умение в условиях жесткой рыночной конкуренции эффективно реализовывать расписания по критериям (выпол- нение заказов точно в срок), максимизация прибыли, минимизация суммар- ного штрафа как за опережение, так и за запаздывание заданий относитель- но директивных сроков и т.д. 5. Модульность алгоритмического обеспечения — выделение общих алгоритмических блоков базовых алгоритмов для решения различных задач и их комбинирование на основе очевидного конструктивного анализа с це- лью эффективного системного проектирования алгоритмов. 6. Универсальность алгоритмического обеспечения — возможность легко перестраиваться с одного критерия на другой, включать дополнитель- ные ограничения, адаптироваться к планированию различных объектов управления. Реализация планирования функционирования сложных объек- тов путем создания системы новых высокоэффективных взаимосвязанных алгоритмов на основе единой логики решения задач по различным критери- ям оптимальности, что позволит эффективно решать задачи планирования в комплексе. 7. Использование эффективных точных и приближенных методов ре- шения оптимизационных задач планирования, модели которых являются различного вида труднорешаемыми задачами комбинаторной оптимизации. Математическое обеспечение системы должно содержать современные тео- ретические достижения в области решения рассматриваемых труднорешае- мых комбинаторных задач планирования. 8. Адекватность реальному производству в его сложности и многооб- разии. Модель планирования должна отражать ограниченность ресурсов, фактическую загрузку оборудования, взаимосвязь между операциями в тех- нологическом процессе, большое количество разнообразных производст- венных связей, конструкторскую сложность продукции, неравномерность количественного выпуска изделий по плановым периодам, неодновремен- ность поступления заданий на выполнение и другие особенности производ- ства. В работах [9, 14, 18, 19] предложена трехуровневая модель планирова- ния в сетевых системах с ограниченными ресурсами, основанная на изло- женных выше принципах. Трехуровневая модель решает следующие задачи. Задача 1. Критерий оптимальности — максимизация суммарной при- были предприятия в случае отсутствия директивных сроков i n i iC∑ =1 min ω , где іC — время выполнения і -го изделия. М.З. Згуровский, А.А. Павлов ISSN 1681–6048 System Research & Information Technologies, 2009, № 3 72 Задача 2. Для всех изделий Іі∈ введены директивные сроки іD , ко- торые не могут быть нарушены (планирование «точно в срок»). Критерий оптимальности i n i iU∑ =1 max ω , где ⎩ ⎨ ⎧ ≠ = = .,0 ,,1 ii ii i DC DC U Задача 3. Для некоторых изделий Іі∈ заданы директивные сроки, ко- торые не могут быть нарушены. Для остальных изделий 0=іD . Критерий оптимизации jj i k i i C∑ =1 min ω , где { }кiі ,,1 … — множество номеров заданий, для которых отсутствуют ди- рективные сроки. Задача 4. Для всех изделий і І∈ введены директивные сроки іD . Не- обходимо изготовить n изделий, минимизируя суммарное взвешенное опо- здание изготовления изделий относительно директивных сроков ( ) 1 min max 0, n i i i i C Dω = −∑ . Задача 5. Постановка задачи соответствует постановке задачи 4. Вве- дено дополнительное условие: для некоторых изделий директивные сроки не могут быть нарушены. Критерий оптимальности ( ) jjj ii к j i DC −∑ = ,0maxmin 1 ω , где { }кіі ,,1 … — множество номеров заданий, для которых разрешается на- рушать директивные сроки. Задача 6. Для всех изделий і І∈ введены директивные сроки іD . Для каждого изделия указана величина iω — абсолютная прибыль от реализа- ции изделия, не зависящая от момента окончания выполнения изделия в том случае, если оно выполняется без опоздания относительно директивного срока, иначе прибыль предприятия по этому изделию равна нулю. Критерий оптимальности — максимизация суммарной прибыли предприятия i n i i U∑ =1 max ω , где ⎩ ⎨ ⎧ > ≤ = .,0 ,,1 ii ii i DC DC U Задача 7. Для всех изделий заданы директивные сроки іD . Необходи- мо минимизировать суммарный штраф предприятия как за опережение, так и за опоздание относительно директивных сроков Иерархическое планирование в системах … как задача принятия решений Системні дослідження та інформаційні технології, 2009, № 3 73 ii n i i DC −∑ =1 min ω . На первом уровне система агрегируется в задачу календарного плани- рования с одним станком и показателем качества задачи 1, у которой веса определяются содержательной постановкой задач 1–7. Ограничения на по- рядок выполнения работ задаются ориентированным ацикличным графом. Граф построен на критических путях, определенных сетевым представлени- ем технологических процессов. Иными словами, на первом уровне решается NP-трудная в сильном смысле задача комбинаторной оптимизации — «ми- нимизация суммарного взвешенного момента окончания выполнения работ при ограничениях на порядок их выполнения, заданных ориентированным ацикличным графом». Задача 1 с учетом агрегации строго решается эффек- тивным точным ПДС-алгоритмом [5]. Алгоритмы для задач 2–7 являются эвристическими с обоснованными эффективными эвристиками. Решение модели первого уровня определяет субоптимальные приори- теты выполнения групп работ. Модели второго и третьего уровня на основе этих приоритетов путем последовательной дезагрегации строят согласован- ный календарный план выполнения работ, учитывающий ограничения на ресурсы, сетевое представление технологического процесса и критерий оп- тимальности. Таким образом, общая многоэтапная модель календарного планирова- ния заменяется последовательностью дискретных математических моделей, совместимых с иерархией решений, которые должны быть приняты на каж- дом уровне планирования, а также порожденных ими систем новых высоко- эффективных взаимосвязанных алгоритмов решения задач планирования по различным критериям оптимальности. Этот подход позволяет использовать на разных уровнях иерархии эффективные точные ПДС-алгоритмы для одноэтапных задач календарного планирования [5, 10, 14, 17, 24]. Предло- женная трехуровневая модель планирования реализует стратегию поиска глобального оптимума, что позволяет получать решения, близкие к опти- мальным. Более глубокий анализ процедуры эффективного планирования в ре- альных сетевых системах с ограниченными ресурсами показывает, что на самом деле лицо, принимающее решение (ЛПР), определяет качество распи- сания работ не по одному, пусть и наиболее важному, критерию, а по их со- вокупности [11], общее количество которых превышает 40 [22, 23]. Поэтому возможность получать по различным скалярным критериям с помощью трехуровневой модели планирования близкие к оптимальным расписания работ нельзя считать завершающим этапом планирования. Действительно, каждое расписание становится альтернативой, которая оценивается ЛПР по всей совокупности критериев. Возникает задача выбора наилучшей альтернативы в соответствии со слабо формализованной гло- бальной целью. Решение проблемы эффективного планирования в сетевых системах с ограниченными ресурсами оказалось напрямую связанным с решением сис- темной проблемы отсутствия однозначной формализации задачи [1]. Метод анализа иерархий Саати [20, 21, 26] является одним из наиболее эффектив- М.З. Згуровский, А.А. Павлов ISSN 1681–6048 System Research & Information Technologies, 2009, № 3 74 ных методов разрешения сформулированной выше системной неопределен- ности, однако имеет одно существенное ограничение: он конструктивен только для случая хорошо обусловленных матриц парных сравнений малой размерности. Этого недостатка лишен модифицированный метод анализа иерархий [6–8], где веса объектов определяются на основании решений спе- циальным образом сформулированных задач оптимизации. Более того, если все критерии, по которым оценивается расписание, имеют численное выражение, то найденные модифицированным методом анализа иерархий результирующие веса альтернатив могут использоваться для нахождения функции принятия решений, т.е. для формализации гло- бальной цели [4, 15, 16]. ЗАКЛЮЧЕНИЕ Исследована с позиций системной и алгоритмической трансвычислительной сложности проблема эффективного планирования в системах, имеющих се- тевое представление технологических процессов и ограниченные ресурсы. Основываясь на принципах рациональности преодоления трансвычис- лительной сложности предложена и обоснована иерархическая модель пла- нирования и ее алгоритмическое обеспечение. Показано, что решение в классической постановке задачи планирова- ния как многоэтапной задачи календарного планирования является лишь начальным этапом задачи принятия решений, формализация которой приво- дит к использованию модифицированного метода анализа иерархий. ЛИТЕРАТУРА 1. Згуровський М.З., Панкратова Н.Д. Основи системного аналізу. — Київ: Ви- давнича група BHV, 2007. — 544 c. 2. ІТ-Предприятие®: система полного цикла автоматизации. — http://www.it.ua. 3. Котлер Ф. Основы маркетинга: Пер. с англ. / Под общ. ред. Е.М. Пеньковой. — М.: Прогресс, 1990. — 736 с. 4. Павлов А.А., Иванова А.А., Чеховский А.В. Восстановление функции приня- тия решения с использованием модифицированного метода анализа ие- рархий / // Вестн. НТУ «ХПИ»: Системный анализ, управление и информа- ционные технологии. — 2009. — № 4. — С. 17–23. 5. Конструктивные полиномиальные алгоритмы решения индивидуальных за- дач из класса NP / А.А. Павлов и др. // Киев: Техніка, 1993. — 128 с. 6. Павлов А.А., Кут В.И. Математические модели оптимизации для обоснования и нахождения весов объектов по неоднородным матрицам парных сравне- ний // Системні дослідження та інформаційні технології. — 2007. — № 3. — С. 28–37. 7. Павлов А.А., Лищук Е.И., Кут В.И. Математические модели оптимизации для обоснования и нахождения весов объектов в методе парных сравнений // Системні дослідження та інформаційні технології. — 2007.— № 2. — С. 13–21. 8. Павлов А.А., Лищук Е.И., Кут В.И. Многокритериальный выбор в задаче обра- ботки данных матрицы парных сравнений // Вісн. НТУУ «КПІ»: Інформа- тика, управління та обчислювальна техніка. — 2007. — № 46. — С. 84–88. 9. Организационная модель планирования мелкосерийного производства в усло- виях рынка / А.А. Павлов и др. // Проблемы информатизации и управления: Сб. науч. тp. — Киев: КМУГА, 1997. — С. 3–5. Иерархическое планирование в системах … как задача принятия решений Системні дослідження та інформаційні технології, 2009, № 3 75 10. Павлов А.А., Мисюра Е.Б. Эффективный точный ПДС-алгоритм решения зада- чи о суммарном запаздывании для одного прибора // Системні дослідження та інформаційні технології. — 2004. — № 4. — С. 30–59. 11. Математические модели иерархического планирования и принятия решений / А.А. Павлов и др. // Вісн. НТУУ «КПІ»: Інформатика, управління та обчис- лювальна техніка. — 2008. — № 48. — С. 63–66. 12. Требования к созданию систем производственного планирования и управления сложными объектами, имеющими сетевое представление технологических процессов и ограниченные ресурсы / А.А. Павлов и др. // Вісн. НТУУ «КПІ»: Інформатика, управління та обчислювальна техніка. — 2007. — № 46. — С. 3–12. 13. Общая модель и методы иерархического планирования функционирования сложных организационно-производственных систем с ограниченными ре- сурсами / А.А. Павлов и др. // Системні дослідження та інформаційні тех- нології. — 2005. — № 4. — С. 7–23. 14. Павлов А.А., Теленик С.Ф. Информационные технологии и алгоритмизация в управлении // Киев: Техніка. — 2002. — 344 с. 15. Павлов А.А., Чеховский А.В. Построение многомерной полиномиальной регрес- сии. Активный эксперимент с ограничениями // Вестн. НТУ «ХПИ»: Сис- темный анализ, управление и информационные технологии. — 2009. — № 4. — С. 174–186. 16. Павлов А.А., Штанькевич А.С. Восстановление закономерности по результатам пассивного эксперимента с ограниченным набором данных // Вестн. НТУ «ХПИ»: Системный анализ, управление и информационные технологии. — 2009. — № 4. — С. 160–169. 17. Павлов О.А., Аксьонова Л.О. Мінімізація сумарного зваженого моменту закінчення робіт як перший рівень моделі дрібносерійного виробництва та способи її розв’язання // Системні дослідження та інформаційні технології. — 2002. — № 1. — С. 119–130. 18. Багаторівнева система планування дрібносерійного виробництва в умовах ринку / О.А. Павлов та ін. // П’ята укр. конф. з автоматичного управління «Автоматика–98». — Ч.ІІ. — Київ: НТУУ «КПІ», 1998. — C. 182–186. 19. Павлов О.А., Місюра О.Б., Мельников О.В. Загальна схема розв’язання задач в багаторівневій системі планування дрібносерійного виробництва в умовах ринку // Вісн. НТУУ «КПІ»: Інформатика, управління та обчислювальна техніка. — 2000. — № 33. — С.27–33. 20. Саати Т. Принятие решений. Метод анализа иерархий: Tomas Saaty. The Ana- lytic Hierarchy Process: Пер. с англ. Р.Г. Вачнадзе. — М.: Радио и связь, 1993. — 315 с. 21. Саати Т., Кернс К. Аналитическое планирование. Организация систем: Пер. с англ. Р.Г. Вачнадзе / Под ред. И.А. Ушакова. — М.: Радио и связь, 1991. — 223 с. 22. Тоценко В.Г. Методы и системы поддержки принятия решений. Алгорит- мический аспект. — Киев: Наук. думка. — 2002. — 381 с. 23. Finke G., Gordon V., Proth J.-M. Scheduling with due dates (Annotated Bibliogra- phy of complexity and algorithms) // Les cahiers du laboratoire Leibniz. — 2002. — № 42. — 58 р. 24. Koulamas C. The total tardiness problem: review and extensions // Operations Re- search. — 42, № 6. — Р. 1025–1041. 25. Research efficiency of exact of PDS-algorithm of task of minimization of the total delay implementation of tasks by one device / А.A. Pavlov et al. // Committee on Data for Science and Technology CODATA’08: 21st International CODATA Conference (October 5–8, 2008, Kyiv, Ukraine). — P. 338–342. 26. Saaty T.L. Multycriteric decision making. The Analytic Hierarchy Process, McGraw Hill International. — N.Y., 1980. Translated to Russian, Portuguese, and Chi- nese. Revised edition, Paperback. — Pittsburgh, PA: RWS Publications, 1990, 1996. — 437 p. Поступила 10.04.2009

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

Institution

Ähnliche Einträge