Полный текст

Введение Задачи календарного планирования возникают в различных сферах деятельности, в том числе при проектировании новых изделий и запуске их в производство, составлении расписаний движения транспорта, планировании графиков выпуска и доставки продукции и т.д. Научный подход к календарному планированию проектов предложен и применен в конце 50-х гг. прошлого века [1]. Были разработаны такие технологии, как PERT (Project Evaluation and Review Technique) и CPM (Critical Path Method) [2] (в отечественной литературе - сетевое планирование и управление) [3]. Характерной особенностью этих технологий является представление проекта в виде комплекса взаимосвязанных работ. Известно, что большинство задач календарного планирования с учетом ограничений на ресурсы являются NP-трудными. Особую актуальность эти задачи приобретают при планировании крупномасштабных проектов, требующих больших затрат ресурсов [4, 5]. Одним из наиболее популярных и наглядных способов представления расписаний и календарных графиков являются диаграммы Гантта [6, 7]. На диаграммах Гантта на одной оси лентами изображаются все операции, выполняемые последовательно на данной машине для различных работ. Основное достоинство диаграммы Гантта состоит в удобном графическом представлении набора работ, позволяющем абсолютно точно идентифицировать: время начала операции, время завершения, исполнителя, набор предшествующих и набор последующих работ, способ выработки критического пути. Основными недостатками диаграмм Гантта можно считать недостаточную гибкость, невозможность отображения значимости или ресурсоемкости работ, сущности работ. Для крупных проектов диаграмма Гантта становится чрезмерно тяжеловесной и теряет всякую наглядность. Несмотря на указанные недостатки, в настоящее время диаграммы Гантта фактически являются стандартным средством представления календарных планов-графиков. С учетом сложности аналитического описания реальных систем для решения задач планирования производства целесообразно использовать методы имитационного моделирования [8, 9]. Для имитационного моделирования дискретных производственных систем широко применяется математический аппарат сетей Петри. Среди основных преимуществ сетей Петри можно отметить то, что они позволяют с требуемой точностью представлять ветвящиеся, параллельные, циклические процессы, обладают средствами анализа, а также моделирования в реальном масштабе времени. Сети Петри позволяют с достаточной степенью детализации моделировать процессы управления в параллельных системах и протоколы взаимодействия. В них имеются простые конструкции для описания структур параллелизма: последовательная композиция, выбор, параллельное слияние [8, 10]. Вместе с тем сети Петри имеют некоторые недостатки, полный анализ которых выходит за рамки данной статьи. Важным недостатком можно считать трудоемкость разработки моделей, и многие исследователи стараются максимально автоматизировать этот процесс [8, 11, 12]. Можно отметить также невыразительность и сложность аппарата сетей Петри, как средства визуализации моделируемого процесса, так и результатов имитационных экспериментов [13, 14]. Задачей представляемой работы является автоматизированное формирование диаграмм Гантта и, по возможности, других форм визуализации результатов по итогам имитационного эксперимента с сетью Петри как механизма минимизации отмеченного недостатка. 1. Модификация аппарата временных сетей Петри Формирование диаграммы Гантта требует наличия в качестве результатов моделирования данных об активности каждого ресурса системы либо каждого объекта. Применительно к сетям Петри такая информация в общем случае отсутствует. Сети Петри оперируют своими специфическими понятиями позиций, переходов, маркировки и др. Эти объекты напрямую не связаны с ресурсами [8, 15]. В некоторых реализациях сетей Петри вводятся дополнительные атрибуты позиций и переходов, связывающие их с ресурсами. В то же время, по мнению автора, требуется формализованный подход для контроля состояния сетевой модели на каждом шаге моделирования. Формально временные сети задаются набором из пяти элементов , где Р, Т, Е имеют обычный для сетей Петри смысл (позиции, переходы, дуги), x0 - начальная маркировка сети, а - функция времени задержки маркеров в позициях сети. Переходам tj сопоставлены значения времени zj, отражающие длительность выполнения соответствующих операций моделируемого процесса. Исходя из анализа приведенных правил можно предложить в качестве основы для формирования диаграммы Гантта использовать атрибуты занятости переходов. Поскольку с практической точки зрения целесообразно описывать сети Петри в матричном виде, введем векторы w и v, элементы которых будут определять занятость переходов и время занятости соответственно. Размерность вектора определяется количеством переходов. Таким образом, динамика имитационной модели на основе сети Петри будет определяться следующими ниже уравнениями изменения состояний. Условие запуска срабатывания переходов Правило изменения состояния входных позиций переходов Изменение атрибутов переходов Условие завершения срабатывания переходов Правило изменения состояния выходных позиций переходов Изменение значений таймеров активных переходов Здесь x - вектор состояния позиций (маркировка), B- - матрица входных инциденций сети, B+ - матрица выходных инциденций сети, z - вектор задержек переходов, u - вектор запуска срабатывания переходов, w - вектор флагов срабатывания переходов, v - вектор таймеров срабатывания переходов, m - количество переходов, n - количество позиций. 2. Пример решения задачи календарного планирования Имеется технологический агрегат (станок), осуществляющий обработку изделий; робот-манипулятор, осуществляющий установку заготовок и снятие готовых изделий с агрегата, а также оперативный накопитель для хранения объектов производства. Например, такую структуру имеют однопозиционные роботизированные технологические комплексы (РТК) на базе токарных станков моделей 16К20Ф3, Т5К20РФЗ или 16К20Т1 (рис. 1). Модель описанной системы приведена на рис. 2. Пояснения к элементам модели приведены в табл. 1. Параметры модели содержит табл. 2. Рис. 1. РТК на основе станка 16К20ФЗ Рис. 2. Сетевая модель системы Таблица 1 Назначение элементов модели Функциональное назначение позиций сети Позиция Назначение p1 Входной накопитель заготовок p2 Заготовка в станке p3 Готовая деталь в станке p4 Выходной накопитель деталей p5 Состояние станка (свободен/занят) p6 Состояние робота (свободен/занят) Функциональное назначение переходов сети Переход Назначение t1 Установка заготовки (роботом) в станок t2 Обработка заготовки t3 Снятие детали (роботом) со станка Таблица 2 Исходные данные для моделирования Параметры переходов Переход Назначение Длительность t1 Установка заготовки (роботом) в станок 0,2 t2 Обработка заготовки 1,2 t3 Снятие детали (роботом) со станка 0,4 Начальная маркировка позиций Позиция Назначение Маркировка x(p1) Входной накопитель заготовок 8 x(p5), x(p6) Состояние станка, робота (свободен) 1 Остальные 0 В программе MathCad были реализованы матричные уравнения изменения состояний и получены значения вектора маркировки сети. На основе интерпретации значений вектора v получены данные, требуемые для представления диаграммы Гантта. В данном примере интерпретация довольно проста, поскольку имеется всего два ресурса (робот и станок) и легко соотнести переходы сети с используемыми ресурсами. В реальных моделях одному ресурсу могут соответствовать десятки переходов. В таких случаях возможно в матричном виде описать отношение инцидентности ресурсов и переходов. Идентификация ресурсов в сетевой модели может быть реализована определением связи каждого перехода и соответствующего физического ресурса системы. Компьютерное моделирование предполагает матричное определение сетевой модели. В связи с этим целесообразно задать матрицу инцидентности ресурсов и переходов R: где - отношение инцидентности i-го ресурса и j-го перехода; k - количество ресурсов; m - количество переходов. Контроль используемых ресурсов может осуществляться по следующему правилу: где - вектор состояния ресурсов; - индикатор активности перехода на текущем такте. По результатам имитационного эксперимента построена диаграмма Гантта для производственной системы (рис. 3). Верхняя лента на графике отображает операции станка, нижняя - робота. Форма ее представления имеет некоторые особенности, связанные с используемой программой. Необходимо также отметить особенность визуализации, связанную с дискретным характером состояний временной сети Петри. Решение задачи оперативно-календарного планирования предполагает также определение графиков выпуска продукции. Применительно к терминологии теории сетей Петри они соответствуют графикам изменения маркировок позиций сети (рис. 4). С точки зрения определения объема готовой продукции анализируется маркировка позиции р4, при необходимости можно также оценить объем незавершенного производства и занятость ресурсов. Рис. 3. Диаграмма Гантта: - робот; - станок Рис. 4. График изменения маркировки сети: Заключение В представленной статье описаны следующие основные научные результаты: 1. Обоснована необходимость использования унифицированных форм представления результатов моделирования процессов сетями Петри. 2. Предложен формальный способ формирования диаграмм Гантта на основе вектора состояния сети Петри. 3. Описаны матричные уравнения изменения состояний временной сети Петри с пошаговым контролем ресурсов и их активности.

Об авторах

А. Н Сочнев

Сибирский федеральный университет

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

Статистика

Просмотры

Аннотация - 66

PDF (Russian) - 36

Ссылки

• Ссылки не определены.