АЛГОРИТМИЧЕСКОЕ ОБЕСПЕЧЕНИЕ ТРЕТЬЕГО И ЧЕТВЕРТОГО УРОВНЕЙ ЧЕТЫРЕХУРОВНЕВОЙ МОДЕЛИ ПЛАНИРОВАНИЯ И ПРИНЯТИЯ РЕШЕНИЙ В СЕТЕВЫХ СИСТЕМАХ С ОГРАНИЧЕННЫМИ РЕСУРСАМИ



Павлов А.А., Мисюра Е.Б., Мельников О.В., Муха И.П., Лисецкий Т.Н. Приводятся предпосылки к созданию новой четырехуровневой модели планирования (включая оперативное)и принятия решений в системах с сетевым представлением технологических процессов и ограниченными ресурсами. Кратко описывается алгоритмическое обеспечение первого и второго уровней созданной модели и более подробно – методы решения задачи планирования на третьем и четвертом уровнях.

We give prerequisites to create a new four-level planning (including operational) and decision-making model for systems with networked representation of technological processes and limited resources. The algorithm ware of the first and second levels of the created modelis briefly described and the methods of the third and fourth levels in more details.

УДК 658.5:519.854.2

Предпосылки к созданию модели

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

Описание алгоритмического обеспечения

Алгоритмическое обеспечение модели вклю­чает блок принятия решений и четыре блока построения модели планирования. В статье [2] представлено алгоритмическое обеспечение первого и второго уровня четырехуровневой модели – формальные модели предварительного (агрегированного) и согласованного планирования. На первом уровне строится агрегированная модель планирования выполнения изделий, на втором уровне – согласованные планы выполнения аг­реги­ро­ванных работ в соответствии с одним из пяти базовых критериев оптимальности либо их произвольной линейной комбинации (26 синтетических критериев оптимальности). Для первого и второго уровней модели:

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

б) адаптированы процедуры выполнения двухуровневой агрегации сетевого представления [1]: первый уровень – агрегация работ, второй уровень – агрегация ресурсов до уровня одного прибора через пересечение критических путей изделий на общих агрегированных работах;

в) обосновано сведение задачи по каждому из базовых критериев оптимизации к задаче минимизации суммарного взвешенного момента окончания выполнения взаимосвязанных работ одним прибором (МВМ) (второй уровень агрегации), использован алгоритм ее решения из [1];

г) формализована процедура согласованного планирования (выполняется на сети первого уровня агрегации); решение задачи МВМ задает порядок выполнения изделий в согласованном плане по заданному базовому критерию.

Для третьего и четвертого уровня модели планирования авторами разработано несколько методов решения задачи:

а) если критерий оптимальности базовый, то задача пооперационного планирования фор­му­лируется и решается как многоэтапная сетевая задача календарного планирования, в которой моменты окончания выполнения изделий являются их директивными сроками, при этом строится субоптимальное расписание выполнения всех работ сети, начиная с элементов конечного ряда сети, через решение одноэтапных труднорешаемых задач календарного планирования на элементах сети с помощью ПДС‑алго­рит­мов [3, 4, 5], и до элементов начальной части сети.

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

1) директивные сроки работ на элементах исходной сети задаются моментами окончания агрегированных работ, в которые эти работы вошли в результате агрегации, в согласованном плане второго уровня, а моменты запуска агрегированных работ определяют минимальные моменты запуска работ на приборах. Многоэтапная сетевая задача календарного планирования решается, начиная с элементов последнего уровня входимости. В результате решения одноэтапных задач получаем моменты начала выполнения работ на всех элементах сети;

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

3) модификация метода для базового критерия: метод последовательно применяется для всех рассматриваемых изделий; если ресурс занят ранее назначенными конфликтующими работами, то их директивный срок уменьшается до момента запуска конфликтующих работ, либо моменты окон­чания конфликтующих работ уменьшаются до предполагаемого момента запуска назначаемых работ с корректировкой директивных сроков пред­шественников конфликтующих работ, если такая корректировка выгоднее (если величина уменьшения директивного срока меньше).

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

в) разработаны два алгоритма оперативной коррекции пооперационного плана: первый – модификация процедуры планирования на 1 – 3 уровнях модели (задача повторно решается по одному из четырех базовых критериев либо их линейной комбинации); второй – формальный алгоритм, включающий в себя ПДС-алгоритмы для труднорешаемых задач комбинаторной оптимизации и экспертное планирование, эффективный в случае возможности его реализации.

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

Список литературы

  1. Згуровский М.З., Павлов А.А. Принятие решений в сетевых системах с ограниченными ресур­сами: Монография.–К.: Наукова думка. – 2010. – 573 с.

  2. Згуровский М.З. Методология построения четырехуровневой модели планирования, принятия решенийи оперативного планирования в сетевых системах с ограниченными ресурсами / М.З.Згуровский, А.А. Павлов, Е.Б. Мисюра, О.В. Мельников, Т.Н. Лисецкий // ВісникНТУУ “КПІ”. Серія «Інформатика, управління та обчислювальна техніка». – К.:“ВЕК+”, 2014. – №61. – с.60–84.

  3. Павлов А.А. Составление допустимого расписания выполнения работ на одном приборе с целью минимизации суммарного опережения работ / А.А. Павлов, Е.А. Халус // ВісникНТУУ “КПІ”. Серія «Інформатика, управління та обчислювальна техніка». – К.:“ВЕК+”, 2014. – №61. – с.27–34

  4. Згуровский М.З. Задача построения допустимого расписания с максимально поздним моментом запуска и минимальным суммарным опережением / М.З. Згуровский, А.А. Павлов, Е.А. Халус // Системні дослідження та інформаційні технології, – 2015. – №3. – 8 с.

  5. Згуровский М.З. Минимизация лексикографического критерия для допустимого расписания на независимых параллельных приборах с произвольными директивными сроками / М.З. Згуровский, А.А. Павлов, Е.Б. Мисюра // Вісник НТУУ “КПІ”. Серія «Інформатика, управління та обчислювальна техніка». – К.: “ВЕК+”, 2014. – №61. – с.4–17
Jun 10, 2016