Апробация работы
Содержание отдельных разделов и диссертации в целом было доложено и получило одобрение:
на Российских и межрегиональных научно-технических конференциях и семинарах (2003-2008г.г.);
на заседании кафедры «АСУ» МАДИ(ГТУ).
Совокупность научных положений, идей и практических результатов исследований в области автоматизации мониторинга работ на протяженных объектах составляет решение крупной научной проблемы в области создания информационно-аналитических систем поддержки принятия решений по управлению работами на протяженных объектах, имеющей важное значений для экономики страны.
Содержание работы
Структура работы соответствует списку перечисленных задач, содержит описание разработанных методов, моделей и методик.
Во введении обосновывается актуальность работы. Рассматриваются основные проблемы создания информационно-аналитических систем управления работами на протяженных объектах. Сформулирована цель работы и основные задачи. Приведено краткое описание содержания глав диссертации.
В первой главе диссертации проводится системный анализ функционирования предприятий, обеспечивающих выполнение работ на протяженных объектах. Рассмотрены методы и модели оценки состояния производственных процессов для решения задач организации и оптимизации процессов управления.
Главным принципом организации работ при этом считается максимальное использование комплекта технологических и транспортных машин и синхронной деятельности предприятий различных отраслей, обеспечивающих выполнение работ на протяженных объектах при условии строгого соблюдения технологии работ, операционного контроля качества, значительного повышения уровня организации и автоматизации производства.
Схема модели управления предприятием
-
Производственный процесс предприятий, обеспечивающих выполнение работ на протяженных объектах, с позиций системного подхода включает в свой состав не только производителей работ, но и поставщиков материальных ресурсов, различных обеспечивающих организаций, транспорт и т.п. Каждое из предприятий может иметь свои цели, задачи и функции. Поэтому в систему управления должны войти теми или иными способами все отмеченные объекты, что позволит применить комплексный подход к управлению производственной деятельностью. Такой комплексный подход к управлению предприятиями отражен на схеме модели управления (рис.1), которая позволяет выявить “узкие” места производственных процессов и предложить мероприятия по их устранению.
В диссертации проведен анализ формализованных моделей процессов транспортировки сырья, материалов и комплектующих на объекты с точки зрения планирования цепи поставок. В качестве базовой использована модель с двухуровневым представлением, где верхний уровень представляет передвижение транспортных средств (ТС), а нижний уровень перемещение грузов (материалов, деталей, комплектующих и др.). Топология сети верхнего уровня определяется схемой маршрутизации потоков ТС. Механизм блокировок (ожидание транспортировки) в общей сети (иерархическое представление) рассматривается как реализация случайного процесса.
В качестве базовых моделей управления запасами выбраны рекуррентные схемы случайных процессов. В общем случае, запас - это количество комплектующих, хранящихся на складе с целью будущего использования при реализации производственных процессов на объектах. В случае дискретного времени величина запаса Zn определяется рекуррентным соотношением:
Zn+1 = Zn + n+1 - f(Zn+1 + n+1 , n+1),
|
(1)
|
где n+1 – количество ресурсов на складе в момент n+1; n+1 - потребность в ресурсах в интервале (n, n+1]; f(Zn+1 + n+1 , n+1) - количество освоенных ресурсов в момент (n+1). Предполагается, что потребности в ресурсах 1, 2, … - взаимно независимые одинаково распределенные случайные величины; заказы осуществляются в соответствии с некоторой политикой заказывания, а функция f определяется этой политикой.
В качестве базовой модели отображения хода производственных процессов в диссертации принята модель сетевого планирования производственной деятельности.
Сетевая модель связности этапов
-
В модели предполагается, что имеется множество производственных этапов {Wi} i=1..I. Время реализации этапа - Ti. Параллельно может выполняться множество этапов. Между реализацией этапов существует логическая взаимосвязь, которая определяется технологическими особенностями. Формально сетевая модель представляет собой взвешенный орграф G (рис.2.):
G=<{Wi: i=1.. Io}, {Ej,j : i, j=1.. I}>,
|
(2)
|
где {Wi} - множество вершин графа G, соответствующих этапам производственного цикла; {Ei,j} - множество дуг графа G, которые определяются технологическими ограничениями к последовательности реализации этапов (наличие дуги определяет Ei,j=1). В качестве модели этапа в общей структуре сетевого планирования используется рекуррентная схема, концептуально подобная алгоритму имитационного дискретно-событийного моделирования, где OutWi – оператор, который реализуется по завершению этапа Wi; InWi(k) – оператор инициализации начала этапа i , где k – номер завершенного этапа.
В качестве инструментов оценки риска при принятии решений по планированию производственной деятельности используются дисперсия, стандартное отклонение и коэффициент вариации. Эти характеристики полезны в случае, когда можно сравнить меру рискованности нескольких альтернативных вариантов. При этом:
 ,
|
(3)
|
где NPVexp - ожидаемая чистая приведенная стоимость; CashFlowi- ожидаемая стоимость денежных потоков в году t, r - норма дисконтирования с учетом риска; n - срок жизни проекта (число лет).
Основой разработки для методов моделирования хода реализации работ на протяженном объекте является его распределенная структура с множеством компонентов и обслуживающих их предприятий (рис.3.)
Задачи размещения
Исходя из проведенного анализа, в диссертации ставится задача интеграции разнородных моделей. Так, статистические модели необходимы для представления результатов выполнения работ на протяженном объекте и планирования производственной деятельности. Имитация необходима для разработки адекватных моделей представления процессов транспортировки, складирования и др. Параметризация имитационных моделей осуществляется на основе статистических моделей вместе с системой мониторинга, которая имеет соответствующую информационную поддержку. В свою очередь имитационные модели, как модели анализа, являются основой для аналитических моделей оптимизации (рис. 4.).
Взаимосвязь методов и моделей
-
Во второй главе диссертации решаются задачи первичного географического размещения элементов протяженного объекта, которые связаны с решением проблем наилучшего расположения таких систем, как промышленные предприятия, объекты обслуживания, склады и т.д. Математическая структура задачи размещения определяется конфигурацией области допустимых точек и способом оценки качества размещения. В работе рассмотрены такие задачи размещения, для которых область допустимых точек размещения центров обслуживания представляет некоторый граф, т.е. элементы протяженного объекта могут располагаться в какой-либо вершине или на какой-либо дуге графа.
При этом имеют место четыре постановки задачи, которые параметризуются различными сочетаниями весовых коэффициентов графа:
1. Предполагается, что необходимо построить, например, новый пост технического обслуживания, который должен обслуживать несколько объектов. Этот пост должен располагаться возле какой-либо из автомагистралей, но так, чтобы минимизировать расстояние до наиболее отдаленного от нее объекта. Если автомагистраль изображается ребром графа, то задача размещения пункта становится задачей такого размещения точки на ребре графа, при котором минимизируется расстояние вдоль ребер (автомагистралей) от этой точки до наиболее удаленной вершины графа (объекты).
2. Предполагается, что на протяженном объекте должен быть размещен, например, склад таким образом, чтобы минимизировалось суммарное расстояние от него до каждого из объектов. В данных случаях по существу рассмотрены одинаковые задачи. Они отличаются только критерием оценки качества размещения. В варианте 1 минимизируется максимальное расстояние; в варианте 2 минимизируется сумма расстояний. Точка размещения, выбранная в соответствии с первым критерием, т. е. точка, в которой минимизируется максимальное расстояние до всех вершин графа, представляет центр. Точка же, выбранная в соответствии со вторым критерием, т. е. точка, в которой минимизируется сумма расстояний до всех вершин графа, представляет медиану.
3. Предполагается, что необходимо разместить, например, станцию технического обслуживания для оказания помощи водителям, нуждающимся в помощи на каком-либо из участков протяженного объекта. Предположим, также, что критерием качества размещения этой станции является минимум максимального расстояния, которое автомобиль-тягач должен преодолеть до возможного места аварии. В этом случае вместо максимального расстояния до всех вершин графа (как это делается в варианте 1) должно рассматриваться максимальное суммарное расстояние до всех точек всех ребер графа.
4. Предполагается, что на протяженном объекте для размещения, например, диспетчерского пункта должно быть выбрано место в каком-либо месте вдоль какой-либо автомагистрали. Место размещения должно быть выбрано так, чтобы минимизировалась суммарная протяженность всех линий передачи данных, которые будут проложены между диспетчерским пунктом и объектами.
Множество рассматриваемых вершин в графе G содержит вершины с номерами от 1 до n. Рассмотрим произвольную дугу (i,j), длина которой равна a(i, j)>0. Пусть f обозначает точку (f-точка) на дуге (i,j), которая для всех 0≤f≤1 отстоит на fa(i, j) единиц от вершины i и на (1—f)a(i, j) единиц от вершины j. Таким образом, вершины графа также могут рассматриваться как точки дуг. Обозначим через X множество всех вершин графа. Пусть через Р обозначается множество всех точек. Таким образом, Р—X является множеством всех внутренних точек.
Пусть d(i,j) представляет длину кратчайшего пути из вершины i в вершину j. Через D обозначим матрицу nn, в которой элементом (i,j) является d(i, j). Элементы матрицы D представляют расстояния вершина — вершина. Для вычисления элементов матрицы D может быть использован алгоритм Флойда или алгоритм Данцига. Через d(f—(r,s)j) обозначим длину кратчайшего пути от f-точки на дуге (r,s) до вершины j. Эта величина представляет расстояние точка — вершина.
Рассмотрим далее наименьшее расстояние от вершины j до каждой точки на дуге (r, s). Для некоторой точки на дуге (r, s) это расстояние принимает максимальное значение. Обозначим его через d'(j,(r,s) - расстояние вершина—дуга. Если дуга (r,s) неориентированная, то имеются два маршрута движения из вершины j в f-точку на дуге (r, s): через вершину r или вершину s.
Пусть в графе имеется t дуг. Обозначим через D' матрицу размерности n X ту, у которой элемент, стоящий на пересечении i-й строки и k-столбца, является расстоянием вершина — дуга от j-й вершины до k-й дуги.
|
(4)
|
Пусть:
МВБ (j) = max {d (i,j)}
|
(5)
|
- максимальное расстояние от вершины i до вершин графа, т. е. расстояние от вершины i до наиболее отдаленной вершины графа, и
- суммарное расстояние от вершины i до всех вершин графа.
Аналогично:
МТВ(f — (r, s)) = max{d(f — (r, s),j},
|
(7)
|
где j - максимальное расстояние от f-точки на дуге (r, s) до вершин графа, т. е. расстояние от f-точки на дуге (r, s) до наиболее отдаленной вершины графа, и
|
(8)
|
- сумма расстояний от f-точки на дуге (r, s) до всех вершин графа. Аналогично определяем МВД(i), СВД(1), МТД(f—(r,s)), СТД(f—(r,s)), взяв максимум или сумму по всем дугам.
Введя определения этих расстояний, их максимумов и сумм, для решения вышеперечисленных четырех задач используются следующие формальные элементы графа.
Центр - любая вершина х, такая, что:
МВБ (х) =  {МВБ (i)},
|
(9)
|
т.е. центр — это любая вершина, расстояние от которой до наиболее отдаленной от нее вершины минимально.
Главный центр - любая вершина х, такая, что:
МВД (х) = {МВД (i)},
|
(10)
|
т. е. главный центр — это любая вершина, расстояние от которой до наиболее удаленной точки на дугах графа минимально.
Абсолютный центр - любая f-точка на произвольной дуге (r, s), такая, что:
МТВ(f — (r, s)) = {МТБ (f—(t, u))}
|
(11)
|
т. е. абсолютный центр — это любая точка на дуге, расстояние от которой до наиболее отдаленной вершины графа минимально.
Главный абсолютный центр - f-точка на произвольной дуге (r, s), такая, что:
МТД (f - (r, s)) = {MTД (f-(t, u))}.
|
(12)
|
Определения типов размещений, связанных с суммарными расстояниями совершенно аналогичны определениям соответствующих предыдущих типов размещений, за исключением того, что везде оператор максимизации [т. е. МВВ(г), МВД(i), МТВ(f—(i,u)), МТД(f— (t, u))] заменяется оператором суммирования, т. е. CBB(i), СВД(i), СТВ(f—(t, u)) СТД(f-(t, u))}.
В третьей главе диссертации ставится и решается задача разработки имитационных моделей системы управления комплексом работ на протяженном объекте. В диссертации разработана концепция построения и включения имитационных моделей в СППР управления работами на протяженных объектах. Модель объекта или процесса в системе моделирования представляет собой динамическую продукционную систему. В системе моделирования существует однозначное отображение моделируемого объекта или процесса в его информационное представление (рис.5.).
Представление объекта моделирования
-
Основным составляющим объекта моделирования, каковыми являются его элементы, процесс, законы функционирования, соответствуют информационные объекты: ресурсы, действия и нерегулярные события, операции. При этом используются некоторые черты объектно-ориентированного подхода . Из указанных элементов, множества ресурсов R и операций О образуют модель. Процесс в объекте моделирования представляет собой временную последовательность действий А и нерегулярных событий Е. Система управления объекта моделирования соответствует модулю вывода динамической продукционной системы.
Модель получается добавлением к динамической продукционной системе аппарата событий, аналогичного подобным аппаратам в системах и языках имитационного моделирования. Моменты окончания действий определяются блоками имитации элементов объекта моделирования, а моменты наступления нерегулярных событий блоком имитации этих событий. Система моделирования включает в себя также подсистему сбора показателей, служащую для сбора результатов моделирования и их первичной обработки.
Процесс функционирования сложной динамической системы (СДС) можно представить как временную последовательность действий и нерегулярных событий:
 ,
|
(13)
|
где А - множество действий;  - множество нерегулярных событий;  - отношение предшествования во времени.
Для регулярного события можно указать алгоритм F преобразования  , который определяется закономерностями функционирования СДС. Поэтому действие a можно представить следующим образом:
 ,
|
(14)
|
где  - алгоритмы преобразования параметров, описывающих состояние ресурсов при событиях  и  ;  - состояние ресурсов, релевантных действию a, до событий начала и конца действия.
Действие a может начаться, если значения параметров его релевантных ресурсов  отвечает некоторому условию. Например, действие обслуживания объекта может начаться, если объекта имеется и обслуживающее предприятие свободно. В противном случае действие начаться не может. Условие начала действия можно представить как некоторое логическое выражение  , принимающее значения ИСТИНА или ЛОЖЬ (TRUE, FALS), в зависимости от текущего состояния релевантных действию ресурсов.
Действие привязано к временной оси: начинается в момент  и кончается в  . Если в описании действия исключить привязку к временной оси, оставив лишь длительность его выполнения  , то получим виртуальное действие (возможное). Виртуальное действие может начаться (но не обязательно начнется), если для множества   релевантных ему ресурсов выполняется условие  . Таким образом, виртуальное действие можно представить как:
 .
|
(15)
|
Виртуальное действие отражает (алгоритмы и условие  ) логику взаимовлияния ресурсов СДС в процессе функционирования. Всякий раз, когда состояние СДС удовлетворяет условию начала виртуального действия, может произойти действие a, соответствующее данному виртуальному и имеющее определенные времена  . То есть виртуальное действие описывает, что может произойти в СДС и при каких условиях, а действие - что произошло/происходит/произойдет и в какое время.
Множество виртуальных действий  , относящихся к определенной системе, может быть разбито на небольшое число подмножеств действий, имеющих одинаковую природу. Виртуальные действия, принадлежащие такому подмножеству  , имеют одинаковую логику взаимодействия ресурсов, и различаются лишь конкретными ресурсами в них участвующими. Подмножество  описывается следующим образом:
 ,
|
(16)
|
где  - множество всех возможных множеств  релевантных ресурсов, с использованием которых можно выполнить виртуальное действие  , а  - длительность выполнения виртуального действия, зависящая от состояния используемых виртуальных ресурсов СДС.
Таким образом, принадлежность виртуальных действий к определенному типу означает, что для них ,  и  одинаковы, т.е. действия одного типа одинаковым образом меняют состояние релевантных ресурсов, требуют одинаковых условий начала по всем ресурсам, и отличаются лишь множествами  , используемых ресурсов и временем выполнения.
Для формального описания логики виртуальных действий, принадлежащих подмножеству  , введено понятие операции. Операция o есть формальное описание множества однотипных виртуальных действий:
 ,
|
(17)
|
где  - описание множества  ;  - множество формальных ресурсов операции.
Операцию o в некотором смысле можно уподобить подпрограмме, в которой  ,  и  - условие выполнения и алгоритмы, описанные в формальных параметрах.
При задании фактических параметров получаем из операции виртуальное действие. Для этого на место каждого формального ресурса  операции о необходимо подставить любой ресурс из некоторого непустого множества однотипных ресурсов.
Таким образом, операция отражает логику взаимодействия ресурсов системы в процессе функционирования. Всякий раз, когда состояние системы соответствует , может происходить действие а, описываемое операцией o, с различными и . Операция описывает, как происходит действие или виртуальное действие и с какими множествами релевантных ресурсов, т.е. что может произойти в СДС при определенных условиях, а действие - что произошло, происходит, произойдет и в какое время.
На основе предложенного подхода в диссертации разработана имитационная модель транспортировки, которая необходима для организации экспериментов по оценке эффективности маршрутизации. Основные требования к ТС это: эффективность, высокая надежность, высокая гибкость, под которой понимается легкость адаптации к изменению структуры грузопотока, рациональное использование ТС.
Транспортные маршруты могут иметь различную топологию и параметры, учитывающие качество подъездных путей, что, в свою очередь, накладывает ограничения на выбор видов ТС для транспортировки. Транспортный путь сложной сетевой конфигурации может быть в общем виде представлен как сеть или граф L=(N,A), где:
N - множество узлов сети, а А - множество дуг.
Узлы транспортной сети представляют собой места принятия решений (места погрузки, выгрузки, перегрузки, стоянки и т.п.). Дуги представляют собой отрезки транспортного пути ТС, не содержащие узлов.
Обозначим qn=|N| - количество узлов и qa=|N| - количество дуг в транспортной сети. Представим сеть в виде списка инцидентности: инцидентность дуг, где для каждой дуги проставлены номера узлов, которыми она заканчивается; инцидентность узлов, где для каждого узла указаны номера прилегающих к нему дуг.
Каждый узел niN транспортной сети описывается следующими параметрами:
{x, y, Fa, Un, M, Cn},
|
(18)
|
i - номер узла, i=1,2,...,qn;
x, y - координаты узла транспортной сети;
Fa - список дуг, прилегающих к данному узлу;
Un - тип узла (1 - склад поставщика; -1 - склад получателя);
M - множество ТС, которым разрешен доступ к данному узлу (вводится для ограничения сферы действия каждого ТС);
Cn - состояние узла.
Каждая дуга aiA транспортной сети описывается параметрами:
i - номер дуги, l=1,2,...,qa;
l - длина дуги;
Fn - список узлов, прилегающих к данной дуге;
e - тип дуги (ориентированная, неориентированная);
Ca - состояние дуги (занято некоторым ТС).
Маршруты w длины r от узла ni1 к узлу nir определим как последовательность узлов wi={ni1, ni2,..., nir}, по которым должно проследовать ТС для достижения узла nir из узла ni1.
По транспортной сети L перемещаются ТС. Каждое ТС viV определяется следующими параметрами:
{Np, Ns, Nl, s, tп, tв, Cv},
|
(20)
|
i - номер ТС, i=1,2,...,qn=|V|;
V - множество всех ТС;
Np - количество мест на ТС или количество грузов, которые можно погрузить на ТС в один ярус;
Ns - максимальная высота штабеля;
Nl - максимальный вес;
s - скорость ТС;
tп - время погрузки;
tв - время выгрузки;
Cv - состояние ТС.
Ограничения {Np, Ns, Nl} обусловлены конструкцией ТС, соображениями устойчивости и прочности тары, а также грузоподъемностью.
Состояние ТС Cv включает следующие параметры:
где cv - вид состояния ТС (свободно, занято, неисправно, заблокировано, и т.п.);
pv - местоположение ТС в транспортной сети;
zv - расположение грузов на ТС.
Учитываются ограничения размещения (высота, масса, максимальная нагрузка сверху, и т.п.). Местоположение ТС в транспортной сети задается номером узла или номером дуги, на которых находится ТС, и признаком, обозначающим, дуга это или узел (рис. 6.).
Пусть O - множество грузов или заявок, сопровождаемых в данный момент автоматизированной системой управления.
Схема маршрутов движения транспортных средств
Каждая заявка oiO описывается параметрами:
где i - номер заявки i=1,2,...,qo=|O|;
po - место нахождения груза;
do - место доставки груза;
to - срок доставки груза;
co - состояние заявки.
Места погрузки и доставки грузов задаются номерами узлов, которые имеют тип источника-приемника грузов: po, doN/Un=1. Итак, имитационная модель включает транспортный путь, множество ТС и множество заявок: S={L, V, O}.
Состояние модели может быть записано на языке предикатов и хранится в базе данных.
Основными задачами моделирования являются:
выбор количества ТС, необходимых для бесперебойной работы транспортных средств;
проверка алгоритмов маршрутизации и диспетчирования и другие.
Для анализа качества функционирования транспортной системы используются следующие показатели:
загрузка каждого ТС;
количество заявок на транспортировку, находящихся в системе;
длительность обслуживания заявок (время от появления запроса на транспортировку до окончания перевозки груза);
отклонения от требуемого срока доставки;
опоздания грузов (только для тех, которые доставлены после срока);
пройденный каждым ТС путь;
количество перевезенных каждым ТС грузов;
среднее расстояние, пройденное при перевозке одного груза.
Для моделирования процессов управления запасами в диссертации разработана имитационная модель, структура которой приведена на рис.7. При этом декомпозиция общей модели управления ПТО предполагает использование ряда компонентов: потока заказов на техническое обслуживание ТС; вероятности отказов в зависимости от гарантированных сроков выполнения работ и поставок комплектующих; прогнозирования заказов на техническое обслуживание; перераспределения финансовых ресурсов и другие.
Структура модели управления заказами
-
|
