Моделирование систем и процессов, 2013, №3

ISSN 2219-0767

МОДЕЛИРОВАНИЕ 

СИСТЕМ И ПРОЦЕССОВ

научно-технический журнал

2013

выпуск 3

2013

ВОРОНЕЖСКАЯ  ГОСУДАРСТВЕННАЯ 

ЛЕСОТЕХНИЧЕСКАЯ АКАДЕМИЯ

ОАО «НАУЧНО-ИССЛЕДОВАТЕЛЬСКИЙ 
ИНСТИТУТ ЭЛЕКТРОННОЙ ТЕХНИКИ»

Журнал зарегистрирован в Управлении по надзору в средствах массовых коммуникаций, связи 
и охраны культурного наследия по Воронежской области (ПИ № ФС 36-1008Р от 15.04.2008)

ISSN 2219-0767

Журнал издается 4 выпуска в год

МОДЕЛИРОВАНИЕ СИСТЕМ И ПРОЦЕССОВ

Редакционная коллегия
Главный редактор 
В.К. Зольников, д-р техн. наук, профессор, зав. кафедрой ВГЛТА

Ответственный секретарь
С.А. Евдокимова, канд. техн. наук, доцент ВГЛТА

Редакционный совет
Председатель 
В.Е. Межов, д-р техн. наук, профессор, профессор ВГЛТА

Члены редакционного совета

В.М. Бугаков, д-р техн. наук, доцент, ректор 
ВГЛТА
М.В. Драпалюк, д-р техн. наук, профессор, 
проректор по науке и инновациям ВГЛТА
Л.И.Бельчинская,  д-р хим. наук, профессор, 
зав. кафедрой ВГЛТА
В.Н.Гриднева, канд. филол. наук, доцент, зав. 
кафедрой ВГЛТА
А.В. Стариков, д-р техн. наук, доцент, зав. кафедрой ВГЛТА
В.В. Лавлинский канд. техн. наук, доцент, зам. 
зав. кафедрой ВГЛТА.
Ю.С. Сербулов, д-р техн. наук, профессор , 
профессор ВГЛТА
В.И. Анциферова, канд. техн. наук, доцент 
ВГЛТА
Е.А. Аникеев  канд. техн. наук, доцент ВГЛТА
Ю.Ю.Громов д-р техн. наук, профессор, директор Института автоматики и информационных 
технологий ТТГУ

А.И. Стоянов, генеральный директор 
ОАО «НИИЭТ»
В.С. Горохов, канд. техн. наук, ученый 
секретарь ОАО «НИИЭТ»
В.Н. Ачкасов, д-р техн. наук, зам. директора по науке - главный инженер ОАО 
«НИИЭТ»
А.В. Ачкасов, канд. техн. наук, зам. генерального директора ОАО «НИИЭТ»
В.П. Крюков, канд. техн. наук, начальник 
отделения ОАО «НИИЭТ»
И.П. Потапов, канд. техн. наук, начальник отдела ОАО «НИИЭТ»
А.И. Яньков, канд. техн. наук, начальник 
лаборатории ОАО «НИИЭТ»
В.С. Стародубцев, д-р техн. наук, профессор, заведующий кафедрой Российского государственного социального университета (Воронежский филиал)

Разделы журнала
Технические науки
Физико-математические науки
Филологические науки
Химические науки
Экономические науки

Статьи, поступающие в редакцию, рецензируются. Мнение редакции может не совпадать с мнением 
авторов. При перепечатке ссылка на журнал обязательна. Материалы публикуются в авторской редакции. За достоверность сведений, изложенных в публикациях, ответственность несут авторы.

Правила доступны на сайте http://www.vglta.vrn.ru/Pages/FreePages/kaf_VT/Default.htm
Адрес редакции: 394087, г. Воронеж, ул. Докучаева, 10, к. 203, тел 8 (473)-253-67-08.
ЛР ИД  №00437 от 10.11.99
Подписано в печать 02.09.13 Формат бум. 6084 1/16  Объем  5,7 п.л. Тираж 1000. Заказ № 496
Отпечатано с готового оригинал-макета в типографии ВГЛТА. 394087, Воронеж, ул. Тимирязева, 8.

 Моделирование систем и процессов, 2013
 Воронежская государственная лесотехническая академия, 2013
 ОАО «Научно-исследовательский институт электронной техники», 2013

Содержание

ТЕХНИЧЕСКИЕ НАУКИ

Акамсина Н.В., Лемешкин А.В., Сербулов Ю.С. Алгоритм выбора количественного состава 
оборудования технологических систем...........................................................................................5

Акамсина Н.В., Лемешкин А.В., Сербулов Ю.С. Алгоритм оптимального составления расписаний реализации операций технологических систем ...................................................................9

Бибиков Д.В., Лавлинский В.В., Табаков Ю.Г. Модифицированный алгоритм вейвлетпреобразования Морле для анализа НЧ сигналов ........................................................................12

Зольников В.К., Смерек В.А., Анциферова В.И., Евдокимова С.А. Алгоритмическая основа 
моделирования и обеспечения защиты типовых КМОП элементов в процессе проектирования......................................................................................................................................................14

Лавлинский В.В. Теоретические основы моделирования компонентов для систем автоматизации проектирования электронной базы на основе синтеза виртуальной реальности ...........16

Лавлинский В.В. Теоретические основы моделирования проектируемых объектов электронной компонентной базы для синтеза виртуальной реальности в виде воздействий тяжелыми 
заряженными частицами .................................................................................................................20

Лапшин Д.Д. Использование распределения Парето для расчета ущерба от катастроф .........25

Рембеза С.И., Кононов В.С. Использование усилителя для проектирования аналоговоцифрового преобразователя с ограниченным использованием переключаемых конденсаторов29

Рембеза С.И., Кононов В.С. Секционный цифро-аналоговый преобразователь для проектирования конвейерных КМОП-КНИ-АЦП при минимизации переключаемых конденсаторов ...32

Смерек В.А., Зольников К.В., Яньков А.И., Конарев М.В., Орликовский Н.А., Ачкасов А.В. 
Определение вероятности безотказной работы при структурной оптимизации элементов 
сложных функциональных блоков в САПР ..................................................................................35

Стородубцева Т.Н., Батурин К.В. Композиционные материалы для верхних покрытий железных дорог..........................................................................................................................................37

Стородубцева Т.Н., Томилин А.И., Аксомитный А.А. Теоретические и экспериментальные 
исследования композиционных материалов. Рекомендации по использованию......................42

Уткин Д.М., Зольников В.К. Проблемно-ориентированное программное обеспечение для 
расчета показателей надежности сложных блоков программно-технических комплексов и его 
интеграция в САПР сквозного проектирования ...........................................................................48

Уткин Д.М., Зольников К.В. Обобщенная методика проектирования сложных блоков, составляющих программно-технические комплексы специального назначения..........................51

Уткин Д.М., Лавлинский В.В., Скляр В.А. Математическая модель сложных функциональных блоков, функционирующих в условиях воздействия радиации ..........................................55

Федоров Д.М. Архитектура интегрированной информационной среды для автоматизированного проектирования воздушных линий электропередачи с учетом электромагнитной безопасности ..........................................................................................................................................58

Федоров Д.М. Организация программного обеспечения автоматизации проектирования воздушных линий электропередачи с учетом электромагнитной безопасности ............................61

Федоров Д.М. Структура процедур автоматизированного проектирования воздушных линий 
электропередачи с учетом электромагнитной безопасности.......................................................64

Чевычелов Ю.А. Организация вычислительных процессов в подсистеме планирования симметричных поставов ........................................................................................................................67

ТЕХНИЧЕСКИЕ НАУКИ

УДК 004
Алгоритм выбора количественного состава оборудования 

технологических систем

Н.В. Акамсина1, А.В. Лемешкин2, Ю.С. Сербулов3

1Воронежский государственный архитектурно-строительный университет, 

nvs2003@yandex.ru

2Воронежский государственный университет инженерных технологий, sansan55@mail.ru

3Воронежская государственная лесотехническая академия, userbulov@vglta.vrn.ru

Аннотация 
—
Рассмотрена реализация процесса 

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

нормирующих функций.

Ключевые слова — Выбор и распределение ресурсов, 

технологическая система, модель, метод нормирующих 
функций.

Общепризнанна фундаментальная роль понятия 

«ресурсы» в процессе системного моделирования 
технологических объектов и многие авторы разработали различные математические подходы для формализации описания этого понятия в контексте системы. 

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

Конкретная значимость понятия «технологическая 

система» непосредственно связана с другим понятием 
- «технология»; под которой подразумевается совокупность методов обработки, изготовления, изменения состояния, свойств, формы сырья, материала и 
полуфабриката, реализуемых в процессе производства продукции. Заметим, что продуктом такой системы в общем смысле может быть изделие отдельной технологической линии, план развития предприятия или его технический проект, пакет прикладных 
программ или результаты научных исследований и 
т.п. При этом под понятие ТС попадает широкий круг 
объектов, предназначенных для реализации различных целей проектирования, планирования и управления, например, промышленный комплекс и автоматизированная система управления этим комплексом; 

гибкая автоматизированная линия и система ее автоматизированного проектирования и т.п.

Типичной задачей выбора и распределения «дис
кретных» ресурсов является выбор количественного 
состава оборудования и его распределения по операциям технологических систем (задача ВКО). Необходимость в решении задачи ВКО возникает на этапе 
параметрического синтеза системы, когда ЛПР требуется на сформированные ранее технологические 
операции ТС выбрать и назначить типы и определенное количество единиц оборудования.

Основная особенность решения указанной пробле
мы связана с тем, что элементы dij искомой матрицы 
d могут принимать только целые положительные значения. Это существенно ограничивает возможности 
ЛПР в выборе метода оптимизации. В связи с этим 
при большой размерности задачи ЛПР обычно вынужден применять различные приближенные алгоритмы, которые не гарантируют ему получения оптимального результата.

Другие важные особенности, свойственные реали
зации ВКО ТС, обуславливаются следующими причинами. Осуществление таких задач, как правило, 
проводится для различного рода производственных 
систем, которые могут отличаться по сложности своей технологической структуры, а также по степени 
гибкости, составляющих эту структуру компонентов.

С понятием «гибкости» для производственных си
стем обычно связывают такие свойства, как – многономенклатурность обрабатываемых в системе изделий; возможность изменения маршрутов обработки 
этих изделий; взаимозаменяемость оборудования  и 
т.п. При этом, согласно [1], можно выделить широкий 
спектр ТС, обладающих различной степенью гибкости: от жестких автоматических линий до производственных комплексов, в которых изменению может 
подвергнуться даже их структура. 

Учитывая вышеизложенное, далее, в рамках ВКО 

ТС, рассмотрим: один из подходов к выбору и распределению «дискретных» ресурсов; пути преодоления ресурсных проблем для систем, характеризующихся сложной сетевой структурой; взаимодействие 
частных моделей, организуемое ЛПР при осуществлении процесса ВКО ТС.

На этапе синтеза систем такие статические харак
теристики ТС, как: суммарная стоимость единиц технологического оборудования; площадь, занимаемая 
под оборудование и т.п., могут выступать в качестве 
ограничений задачи оптимизации. Однако при этом 
ЛПР должен будет выбрать такие показатели, которые, хотя бы косвенно, определяли динамику функционирования объекта.

Заметим, что на этапе синтеза ЛПР не может вос
пользоваться «в чистом виде» динамическими характеристиками ТС, так как, для этого ему требуется 
произвести анализ функционирования объекта. Отсюда вытекает следующий подход к реализации рассматриваемого этапа: вычленить статические составляющие исследуемых динамических характеристик и 
попытаться их оптимизировать.

Из-за большого количества целей, преследуемых 

обычно в процессе синтеза ТС, решение задачи ВКО 
носит многокритериальный характер, постановка ее в 
общем виде соответствует совокупной векторной 
модели. Однако в частном случае реализация такой 
модели может быть сведена к последовательности 
решения задач скалярной оптимизации. Предположим, что исследуемая задача решается с помощью 
одного из методов, реализующих принцип покомпонентной оптимизации, например, метода последовательных уступок [2]. Тогда в процессе решения задачи вначале будет оптимизироваться один (наиболее 
важный) критерий, некоторым образом характеризующий, например, динамику функционирования объекта. В этом случае задача распределения ресурсов 
для ТС может быть сформулирована в виде задачи 
целочисленного выпуклого программирования и решаться с помощью метода нормирующих функций. 
Рассмотрим вначале решение этой задачи на примере 
линейной структуры исследуемой системы, а затем 
обобщим полученные результаты на сложную структуру ТС.

Линейная структура. Пусть в поцессе проектирования 

ТС определены: номенклатура обрабатываемых в системе видов изделий I = {1, 2, . . ., i, . . ., n} и совокупность технологических операций (ТО)  J = {1, 2, . . ., j, . . 
., m}. Каждой паре (i j) соответствуют pij – количество iх изделий, обрабатываемых на j-й ТО. Технологические 
операции являются элементами маршрутов обработки 
изделий, а обобщенный технологический маршрут 
представляет собой цепочку последовательно соединенных операций, что соответствует линейной структу
ре ТС. Для каждой j-й ТО выбран один тип оборудования 
L
l j
(где L – множество используемых в системе 

типов оборудования) и определено подмножество обрабатываемых на этой ТО видов изделий Ij = {1, 2, . . ., i, 
. . ., nj}, 
I
I j  .

Будем оптимизировать вектор целевых функций q , 

характеризующий эффективность формирования исходной структуры ТС. Тогда задачу статической оптимизации можно будет сформулировать в виде  задачи 
оптимального выбора и распределения неоднородных 
ресурсов:

 






c
d Ф

1
j
m
j

m

c

r j
j
r
r
r j

j 1

q d
min ,

d
d ,
,d ,
,d
,
d
1,2,
,
j 1,m,

Ф :
a
d
b ,
b
0,
r 1,R ,
a
0,

















(1)

где dj – количество единиц оборудования на j-й ТО; br

– имеющееся в наличии количество r-го ресурса; arj –
удельный расход r-го ресурса при использовании на j-й 
ТО единицы оборудования, Фс – область допустимых 
решений.

Допустим, что в процессе решения задачи ВКО 

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

Однако на данном этапе общего ресурсного процесса 

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

 

j
u

m

j
t Ф

j 1

n
n

i j

j
i j

i 1
i 1
i j
j

q t
t
min ,

p
Ф:t
t
,
j 1,m,
e d





















(2)

где tij – время обработки i-го вида изделий на j-й ТО; 

рij – производительность оборудования lj при обработке 
i-го вида изделий, еij – аналогично план для i-го вида 
изделий на j-й ТО.

Требование целочисленности элементов из множе
ства Ф с, нелинейность выбранной целевой функции q
значительно затрудняют решение задачи. И хотя, существуют специальные методы решения подобных задач 
математического программирования, например, метод 
ветвлений и метод отсечений [3] (которые могут быть 
использованы при сведении нелинейной целевой функции к линейному виду, учитывая ее сепарабельность), 
существенным ограничением к их применению является медленная сходимость этих методов и, в соответствии с этим, вычислительные трудности, связанные с 
решением задач большой размерности. С другой стороны, вид целевой функции и ограничений в представленной постановке делают удобным использование в данном случае одного из приближенных методов – метода 
нормирующих функций (МНФ) [4], который ориентирован на решение различных целочисленных задач.

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

jd
1, j 1,m


(в данном случае 
jd
0

не может быть, 

так как это будет означать невыполнение j-й ТО, а значит несоблюдение технологии получения готовой продукции); и заканчивает работу, когда оставшегося количества, хотя бы одного ресурса, уже недостаточно, чтобы сделать новый шаг.

Опишем работу данного алгоритма применительно к 

решению сформулированной задачи.

1.
Присвоить s = 0 (где s – текущий шаг работы ал
горитма).

2.
Рассчитать исходные параметры при условии

(
m
,1
j
,1
d j


):

s
j
j

m

s
s

r
r
r
r j

j 1

d
d , j 1,m,

b
b , c
a , r 1,R ,











где 
s
rc
- расход r-го ресурса на s-м шаге.

3.
Присвоить s = s + 1.

4.
Определить остатки по каждому виду ресурса 

R
,1
r,
c
b
b
1
s
r

1
s
r

s
r



5.
Выделить подмножество ТО 
J
J 

, удовлетво
ряющих условию: 
R
,1
r
,
b
a
J
j
s
r
j
r




.

6.
Если 
0
J 

, перейти к пункту 7. Если 
0
J 

, пе
рейти к пункту 12.

7.
Пронормировать удельные расходы ресурсов 

r j
s
r j
s
r

a
j J
a
, r 1,R
b


 


.

8.
Выделить из них максимальное значение

  


s
s

j
rj

r

j J
a
max a
.
ma x

 


9.
Определить номер ТО 
J


, обеспечивающей 

максимум уменьшения целевой функции к единице 
нормированного ресурса:




s
j
s

s
j J
jma x

o
o
o

j
j
j
s
j
s-1
s
s-1
s-1

j
j
j
j

q
j:
max
,

a

t
t
t
q
,

d
d
d
d
1








 














где 

o
jt
- суммарное время обработки изделий на j-й 

ТО при dj = 1. В случае равенства 

s

для некоторого 

подмножества ТО J
J



, из них, согласно [4], можно 

выбрать такую ТО, которая обеспечит 



s
j mx

j J
min a



, 

что будет соответствовать распределению ресурсов минимальными порциями.

10.
Присвоить: 
s
s-1
d
d
1



 , 
s
r
r
c
a
,
r 1,R



.

11.
Перейти к пункту 3.

12.
Закончить вычисления.

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

Сетевая структура. Рассмотрим теперь более общий 

случай – сетевую структуру ТС. Пусть обобщенный 
ориентированный ациклический граф маршрутов обработки изделий в системе представлен в виде сети. Известно [5], что при такой структуре ТС длительность 
производственного цикла будет определяться временами выполнения не всех ТО, а только тех из них, которые 
составляют критический путь. При игнорировании этого факта в процессе решения задачи ВКО на некоторые 
ТО может быть распределено избыточное количество 
единиц оборудования, которое не будет влиять на значение рассматриваемого критерия. Так как в данном 
случае мы имеем дело со статическими составляющими 
длительности производственного цикла, на первом эта

пе реализации задачи оптимизации критическим путем 
назовем такую последовательность ТО, сумма времен 
обработки изделий, у которых максимальна.

Учитывая, в предположении, линейность критическо
го пути, в алгоритме, реализующем МНФ, для случая 
сетевой структуры ТС будем использовать ту же целевую функцию q, что и при линейной структуре системы, 
но при этом добавлять оборудование, прежде всего, на 
те операции, которые принадлежат критическому пути. 
Внесем в алгоритм необходимые изменения.

6. Если 
0
J 

перейти к пункту 6а (далее аналогично 

рассмотренному ранее).

6а. По способу, описанному в [5], определить под
множество ТО 
*J
J

, составляющих критический 

путь. При этом время выполнения каждой ТО на s-м 
шаге работы алгоритма рассчитывать по формуле: 

s
o
s-1

j
j
j
t
t /d
, j 1,m


.

6б. Выделить множество ТО 
*
*
*
J
J
J



.

6в. перейти к пункту 7, причем, если 
0
J *
* 
, далее в 

пунктах 7 – 9 вместо J
использовать это множество 

ТО.

Отмеченные достоинства МНФ говорят об удоб
стве и эффективности его применения при решении 
подобных задач распределения ресурсов. В этой связи заметим, что основной недостаток МНФ – отсутствие гарантий получения с его помощью абсолютно 
точного решения, в данном случае не играет особую 
роль. Так как решение задачи оптимизации, полученное на первом этапе ресурсного процесса, является 
промежуточным, и его оптимальность еще не гарантирует оптимальность полного решения задачи ВКО. 
В то же время решение, полученное с помощью модифицированного МНФ, может служить «отправной 
точкой» для дальнейших исследований по ресурсному распределению в ТС.

Основное отличие модифицированного МНФ от 

его классического прототипа заключается в том, что 
первый из них предполагает на каждом шаге работы 
алгоритма дополнительно рассчитывать условный 
критический путь, характеризующий наиболее «узкое 
место» в структуре системы, и добавлять единицу 
оборудования на одну из ТО данного пути. В связи с 
тем, что такой критический путь дает лишь приблизительную оценку загруженности ТО (так как при его 
расчете нельзя учесть непроизводительные простои 
оборудования, которые, как правило, ЛПР может 
оценить только в процессе имитационного моделирования), трудно при этом говорить об оценке эффективности предложенного метода. Однако его применение позволяет ЛПР перейти к анализу функционирования системы, учесть некоторые структурные 
особенности объекта моделирования, что в конечном 
итоге может сказаться на результатах решения задачи.

ЛИТЕРАТУРА

[1] Робототехника и гибкие автоматизированные произ
водства [Текст] : в 9-ти кн. Кн.1. Системные принципы 
создания гибких автоматизированных производств :
учеб. пособие для вузов / И. П. Макаров. - М. :
Высш.шк.,1986. - 175 с.

[2] Подиновский, В. В. Оптимизация по последовательно 

применяемым критериям [Текст] / В. В. Подиновский, 
В. М. Гаврилов. - М. : Сов.радио,1975. - 192 с.

[3] Кофман, А. Методы и модели исследования операций. 

Целочисленное программирование [Текст] / А. Кофман, А. Анри-Лабордер. - М. : Мир, 1977.-432 с.

[4] Берзин, Е. А. Оптимальное распределение ресурсов и 

теория игр [Текст] / Е. А. Берзин. - М. : Радио и связь, 
1983. - 216 с.

[5] Конвей, Р. В. Теория расписаний [Текст] / Р. В. Кон
вей, В. Л. Максвелл, Л. В. Миллер. - М. : Наука,1975.360 с.

УДК 004

Алгоритм оптимального составления расписаний 

реализации операций технологических систем

Н.В. Акамсина1, А.В. Лемешкин2, Ю.С. Сербулов3

1Воронежский государственный архитектурно-строительный 

университет,nvs2003@yandex.ru

2Воронежский государственный университет инженерных технологий, sansan55@mail.ru

3Воронежская государственная лесотехническая академия, userbulov@vglta.vrn.ru

Аннотация — Разработаны модели решения задачи 

составления 
расписаний
технологических 
систем. 

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

Ключевые слова — Технологическая система, техно
логическая операция, модель, расписание, алгоритм.

Общепризнанна фундаментальная роль понятия 

«ресурсы» в процессе системного моделирования 
технологических объектов и многие авторы разработали различные математические подходы для формализации описания этого понятия в контексте системы. 

Технологическая система (ТС), имеющая сложную 

структуру, часто состоит из нескольких участков. Эти 
участки могут характеризоваться своей автономностью относительно номенклатуры обрабатываемых в 
них изделий, совокупности использования оборудования, транспортной системы и т.д. Например, это 
имеет место в гибких производственных системах 
(ГПС). Структура такой ТС часто имеет вид сети с 
узлами сборки и разузлования, что значительно 
усложняет решение задачи составления расписаний 
для всей системы в целом.

При разработке алгоритма составления расписаний 

для ТС, состоящих из отдельных линейных участков, 
была применена методология известного декомпозиционного подхода к решению подобных задач при 
планировании одного вида готовой продукции [1]. 
Вместе с тем в предлагаемом алгоритме учитываются 
специфические особенности подобных ТС: относительная автономность составляющих их участков и 
возможность получения не одного вида, а некоторой 
номенклатуры готовой продукции.

Постановка задачи. Пусть для обработки множе
ства видов изделий I = {1, . . ., i, . . ., n} на множестве 
имеющегося оборудования L = {1, . . ., l, . . ., m} 
необходимо выполнить множество работ N = {1, . . ., 
Ni , . . ., Nn}. Здесь и далее, используя понятие вида 

изделий, будем учитывать партионность обработки 
изделий. Такая система включает в себя совокупность 
линейных участков k = {1,  . . ., k, . . ., Ks}, каждый из 
которых характеризуется собственной номенклатурой обрабатываемых изделий I k I, совокупностью 
используемого оборудования Lk L и набором работ 
N
k N, представляющих собой непересекающиеся 

последовательности технологических операций (ТО) 
[1] для обработки каждого вида изделий из Ik. Такую 
систему представим в виде конечного ориентированного ациклического графа G = (K, V) с множеством 
вершин K и дуг V. Каждая вершина kK графа G
соответствует одному участку, каждая пара вершин 
(k, k’ )  K соединяется дугой 
kk
V



, направлен
ной от вершины k к вершине k’, если хотя бы один 
вид изделий из Ik необходим для обработки изделий 
из Ik’.

Построенный граф G представляет собой исходную 

модель структуры ТС. Подобно исходной модели в 
[1] он содержит некоторое множество вершин 
K
K

с нулевой полустепенью захода и одну вер
шину 
*
k
K

с нулевой полустепенью исхода. Эта 

вершина соответствует участку, обработка изделий в 
котором непосредственно предшествует получению 
готовой продукции.

На основе графа G построим графы GП   и GТ, кото
рые так же, как и в [1], будем использовать для составления расписаний.

Для получения графа Gп = (I, Vп, Wп) каждую вер
шину k K

графа G заменим множеством вершин 

kI
I

и каждую дугу 
kk
V



- множеством дуг 

kk
П
V
V

. При этом каждая пара вершин (ik, ik’) (где 

k
k
i
I , i
I
k
k



) соединяется дугой 
k
k
i
V

k


ki

, направ
ленной от вершины ik к вершине ik’, если вид изделий 
ik необходим для обработки вида ik’ . Каждой вершине поставим в соответствие число 
 
п
k
W
i
R


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

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

Воспользуемся теперь графом GП для того, чтобы 

построить граф GТ = (N, VП), характеризующий технологию получения в ТС готовой продукции. Для 
этого каждую вершину ik графа GП заменим новой 
вершиной 

ki
N
N

, соответствующей работе, посред
ством которой обрабатывается этот вид изделий. 
Каждая вершина 

ki
N
графа GТ в свою очередь явля
ется последовательным графом 


k
k
k
k
i
i
i
i
G
P ,V ,W

(с 

множеством 
вершин 

kiP , 
дуг 

kiV , 
функций 

k
k
i
i
W :P
R

), 
определяющим 
последовательность 

составляющих 
данную 
работу 
элементов 
ТО 



k
k
i
k 1
k j
k i
P
i l ,
,i l ,
,i l

, где каждый элемент, следуя 

[2], характеризуется индексом принадлежности к 
оборудованию lj и индексом принадлежности к работе 

ki
N
. Функция 

ki
W
R

каждой вершине ставит в 

соответствие число 


k
k
j
i
k
j
i l
W
i l
to

, определяющее 

время выполнения данной операции.

Заметим, что построенный граф Gт не является 

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

Если в качестве ТС рассматривается ГПС, для каж
дого типа оборудования 
k
k
l
L

из участка с номером 

k, 
зададим 
матрицу 
времен 
переналадок 

k

o

l
ii
k
M
t
, i I


, и, используя граф GТ, определим 

множество выполняемых этим типом оборудования 
работ 

kl
k
N
N

.

При такой постановке критериями оценки расписа
ний могут быть различные показатели, характеризующие динамику функционирования объекта, например: длительность производственного цикла, суммарное  время простоев или переналадок оборудования. Варьируемым же параметром при этом может 
являться очередность обработки изделий на всех первых (по ходу процесса) ТО. Пусть d = {d1, . . ., dl, . . ., 
dm} – вектор назначенного оборудования, т.е. полученное ранее оптимальное решение задачи на этапе 
синтеза системы (так как предполагается, что каждой 
ТО соответствует один тип оборудования, то индекс 
«j» в данном случае можно заменить на индекс «l»; 
по этой причине d можно рассматривать не как мат
рицу, а как  вектор); 


1
z
z ,
,z

- параметры, 

определяющие очередность обработки всех первых, в 

количестве  ТО процесса (причем, они могут при
надлежать разным участкам); q - вектор критериев 
качества; ФД – область допустимых решений, учитывающих особенности построения графов GП и GТ, а 
также следующие допущения, позволяющие применять стандартные алгоритмы составления расписаний: начавшаяся не прерывается, одновременное выполнение двух ТО при помощи одного и того же типа 
оборудования запрещено. В этом случае решение 
задачи оптимизации сводится к определению оптимального для каждого типа оборудования l
L

по
рядка выполнения на нем ТО и моментов их начала.

Алгоритм составления расписаний. Особенностью 

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

Декомпозиция сформированной задачи, согласно 

[1], основывается на: 1) разбиении графа G на подграфы; 2) решении для каждой вершины подграфа, 
соответствующей определенному участку, задачи 
составления расписаний; 3) агрегировании результатов решения подзадач в общее решение задачи.

При разбиении графа G по способу, описанному в 

[1], получим подграфы G1, . . ., Gr, представляющие 
собой ранговую структуру вершин графа G с r – рангами. При этом ранговая структура строится в 
направлении от вершин множества K’, имеющих нулевую полустепень захода к вершине k*, имеющей 
нулевую полустепень исхода. Затем, перейдя от графа G к графам GП и  GТ, мы сможем сформулировать 
для каждого участка отдельного подграфа задачу составления расписаний.

Проблему синхронизации поступления изделий из 

разных участков на ТО сборки можно уменьшить 
установлением определенного порядка получения 
номенклатуры готовой продукции и фиксацией этого 
порядка для всех видов изделий (работ) в соответствии с принадлежностью их к видам готовой продукции. Поэтому проблема синхронизации решается 
в направлении, обратном направлению декомпозиции 
задачи: от вершины k* графа G к вершинам множества K’.