РАЗДЕЛ 2
МОДЕЛЬ РАБОТЫ АВТОМАТИЗИРОВАННЫХ ПРОИЗВОДСТВЕННЫХ СИСТЕМ С ИСПОЛЬЗОВАНИЕМ
ПРОИЗВОДСТВЕННО-ВРЕМЕННЫХ ГРАФОВ
2.1 Основные положения по составлению расписаний на базе
производственно-временных графов
Анализ существующих схем планирования и организации работ на производстве,
исследование их структурных составляющих и характеристик позволили
формализовано представить взаимодействие оборудования в АПС во времени в виде
производственно-временных графов (ПВГ).
Введем понятие производственно-временного графа [4, 6].
Производственно-временным графом назовем помеченный ориентированный граф G c p
вершинами, заданными множеством (множество элементов основного оборудования
АПС), и q ребрами, заданными множеством (множество перемещений элементов
вспомогательного оборудования между элементами основного). Множество вершин
состоит из двух непересекающихся подмножеств и , то есть , , .
Каждой вершине , поставлено в соответствие некоторое множество временных
интервалов где , . Множество ребер состоит из непересекающихся подмножеств и ,
то есть , , , .
Каждому ребру поставлен в соответствие некоторый временной интервал .
Производственно-временной граф G может состоять из подграфов , для каждого из
которых справедливы указанные выше условия.
Вершину , не имеющую инцидентных ей ребер, для которой множество временных
интервалов ?, назовем изолированной вершиной. Производственно-временной граф,
состоящий из изолированных вершин, будем называть нулевым
производственно-временным графом и обозначать .
Введем обозначение производственно-временного графа G в виде следующей четверки
параметров: G{V, B, W, R},
где V - множество вершин;
B - множество временных интервалов вершин;
W - множество ребер;
R - множество временных интервалов ребер.
Временной интервал назовем противоположным интервалу , если , и будем
обозначать .
Производственно-временной граф назовем противоположным графу , если , и для
любых временных интервалов и существуют единственные временные интервалы и
такие, что и где . Противоположный граф будем обозначать .
Пример производственно-временного графа приведен на рис. 2.1. Ребра,
принадлежащие множеству , показаны сплошными линиями, а ребра, принадлежащие
множеству - пунктирными.
Содержательное истолкование производственно-временного графа состоит в
следующем. Имеется некоторая производственная система, состоящее из p элементов
основного оборудования, i-му элементу соответствует на
производственно-временном графе вершина , а интервал времени, в течение
которого i-й элемент участвует в работе над производственной задачей,
соответствует интервалу . Множество таких интервалов работы i-го элемента
составляет множество . Множество элементов основного оборудования состоит из
объектов двух видов - активных и пассивных. Активным элементам на
производственно-временном графе соответствует множество вершин , а пассивным
множество вершин .
Рис.2.1. Пример производственно-временного графа
Существуют перемещения изделий между элементами основного оборудования,
выполняемые элементами вспомогательного оборудования. Перемещения бывают двух
видов: рабочие и холостые переходы. Рабочим переходам соответствуют на
производственно-временном графе ребра, принадлежащие множеству , холостым –
ребра, принадлежащие множеству . Интервал времени соответствует времени
реализации i-го перемещения. Если имеется элементов вспомогательного
оборудования, то производственно-временной граф разбивается на подграфов.
Будем говорить, что интервал непосредственно предшествует интервалу , если не
существует интервал такой, что , а при такой, что .
Введем на множестве производственно-временных графов специальные операции
объединения и пересечения [4].
Объединением графов и будем называть граф , в котором множества определяется
следующим образом
1. .
2. , где - подмножество взаимнопротивоположных интервалов множеств и , , то
есть, если , и , то , . Между элементами множества , , устанавливается
отношение непосредственного предшествования.
3. , где - подмножество взаимнопротивоположных интервалов множеств и ,
соответствующих одинаковым ребрам в и , то есть, если , и , то . Между
элементами множества устанавливается отношение непосредственного
предшествования.
4. , где - множество ребер, временные интервалы которых принадлежат множеству ,
то есть, если , то .
Отметим основные свойства операции объединения на множестве
производственно-временных графов .
Замкнутость. Если и , то .
Ассоциативность: .
Коммутативность: .
Наличие нулевого элемента в виде графа , причем .
Наличие для любого графа противоположного ему графа , причем .
Перечисленные свойства позволяют сделать вывод, что исходное множество
производственно-временных графов и введенная на нем операция объединения
образуют бесконечную абелеву группу [100, 101].
Проиллюстрируем операцию объединения на примере объединения графов и (рис.2.2).
Граф приведен на рис. 2.3.
Пересечением графов и будем называть граф , в котором множества определяются
следующим образом.
1.
2. Ш, , где - число элементов (мощность) множества .
3. Множества и определяются следующим образом:
а) формируется множество и соответствующее ему множество ;
б) множество упорядочивается в порядке возрастания начал интервалов, полученное
упорядоченное множество обозначаем ;
в) формируется множество в соответствии с полученным множеством ;
г) выбирается пара соседних элементов множества (и соответствующие элементы
множества ):
где - мощность множества .
G1
G2
- Київ+380960830922