книги / Управление большими системами. УБС-2017

Управление организационными и социально-экономическими системами

		a)			b)
	1			1
	0.5			0.5
	0			0
	0	5	10	0	5	10
			c)
		1			= 0
					= 0.1
		0.5			= 0.2
					= 0.3
		0
		0	5	10

Рис. 5. График зависимости от числа уровней при = 3,

= 0.01, 1 = 1, 2 = 1: a) = {1}; b) = [1, 5]; c)= [1, 10];

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

∙оптимальная структура производственной системы определяется нормативными и фактическими пропорциями факторов производства;

∙рост меры отклонения фактических пропорций факторов производства от нормативных величин ведет к росту сложности оптимальной структуры;

31826

251

Управление большими системами. Выпуск XX

∙рост неравномерности факторных пропорций элементарных производств ведет к росту сложности оптимальной структуры;

∙рост неопределенности в оценке фактических и плановых пропорций факторов производства ведет к снижению сложности оптимальной структуры;

Литература

1.БУРКОВ В.Н., ГУБКО М.В., КОРГИН Н.А., НОВИКОВ Д.А. Теория управления организационными системами и другие науки об управлении организациями // Проблемы управления. — 2012. — № 4. — C. 2–10.

2.ВЕДЕРНИКОВ Ю.В., КРАВЦОВ А.М., САФРОНОВ В.В., УМЕРЕНКОВ С.А. Методика оптимизации сложных технических систем в условиях риска // Информационноуправляющие системы . — 2007. — № 1. — C. 40–45.

3.ВОРОНИН А.А, МИШИН С.П. Оптимальные иерархические структуры // М.: ИПУ РАН, 2003. — 214 с.

4.ВОРОНИН А.А, МИШИН С.П. Алгоритмы поиска оптимальной структуры организационной системы // Автоматика и телемеханика, 2002, № 5.

5.ВОРОНИН А.А., ХАРИТОНОВ М.А. Модель численной оптимизации структуры операционного ядра организации // Управление большими системами. Выпуск 39. М.: ИПУ РАН, 2012. С.165–183

6.ГУБКО М. В. Структура оптимальной организации континуума исполнителей // Автоматика и телемеханика. — 2002. — № 12. — C. 116–130.

7.ГУБКО М. В. Поиск оптимальных организационных иерархий при однородных функциях затрат менеджеров

// Автоматика и телемеханика. — 2008. — № 1. — C. 97–113.

8.ГУБКО М. В. Алгоритмы построения субоптимальных организационных иерархий // Автоматика и телемеханика.

— 2009. — № 1. — C. 162–179.

252

31927

Управление организационными и социально-экономическими системами

9.КЛЕЙНЕР Г.Б. Производственные функции. Теория, методы, применение. // М.: Финансы и статистика, 1986. - 239 с.

10.НОВИКОВ Д.А. Теория управления организационными системами. // М.: Физматлит, 2007. - 584 с.

11.РОЖИХИН П.В. О поиске оптимальной траектории преобразований графа организации // Управление большими системами. — 2004. — Вып. 6. — C. 105–116.

12.РОЖИХИН П.В. О траекториях преобразования структуры организационных систем // Управление большими системами. — 2004. — Вып. 9. — C. 190–200.

13.РОЖИХИН П.В. Оценка мощности пространства состояний иерархической структуры // Управление большими системами. — 2005. — Вып. 11. — C. 75–80.

14.ЦИРЛИН А. М. Об оптимальной организации систем нагрева и охлаждения // Теоретические основы химической технологии. — 2012. — Т. 46, № 1. — C. 109.

15.ЮДИЦКИЙ С.А. Триадно-сетевые дорожные карты развития систем // Управление большими системами. — 2013. — 29 Вып. 42. — C. 55–74

16.BARNETT W. P., CARROLL G.R. Modeling Internal Organizational Change // Annual Review of Sociology. — 1995. — Vol. 21. — P. 217–236.

17.BLAND R.G. New finite pivoting rules for the simplex method // Mathematics of Operations Research. — 1977. — Vol. 2, №2 — P. 103-107.

18.DANILENKO A.I., GOUBKO M.V Semantic-aware optimization of user interface menus // Automation and Remote Control. — 2013. — Vol. 74, № 8. — P. 1399-1411.

19.GOUBKO M. Optimal organizational structures for change management in production // Intelligent Systems Reference Library. — 2016. — Vol. 98. P. 59-83

20.KHARITONOV M., SVETLOV A., VORONIN A. Operating core of an organizational system: optimal control of support structure // International Journal of Pure and Applied

3208

253

Управление большими системами. Выпуск XX

Mathematics, vol. 107, No. 4 (2016), p. 889 - 901

21.SHEU C. Y., PRAGER W. Recent developments in optimal structure design // Applied Mechanics Reviews. — 1968. — Vol. 21, № 10. — P. 985–992.

22.YANG W.H. On a class of optimization problems for framed structures // Computer Methods in Applied Mechanics and Engineering. — 1978. — Vol. 15, iss. 1. — P. 85–97.

OPTIMIZATION OF THE STRUCTURE OF THE PRODUCTION SUBSYSTEM OF THE ORGANIZATION UNDER CONDITIONS OF UNCERTAINTY

Mikhail Kharitonov, Volgograd State University, Volgograd, junior researcher ([e-mail]).

Abstract: We introduce an algorithm for numerical solution of the problem for structurally-parametric synthesis of optimal structures described by n-graded hierarchical graphs and generated by subgraphs with recursively defined structurally-dependent objective functions that can be represented as superpositions of elementary objective functions given at their vertices. The optimal structure corresponds to the optimal dimension of a family of convex programming problems that perform stream optimization on each fixed structure. We create an algorithm for automatic derivation of necessary equations and inequalities for this family of problems. On the basis of this algorithm, we construct an optimization models for the hierarchical structures of production subsystems of enterprises with structurally dependent production functions of the Leontief type under conditions of uncertainty

Keywords: production subsystem, hierarchical n-graded graph, structure optimization, parametric linear programming, flow control, Leontyev production function, hierarchical structure.

254

3219

Информационные технологии в управлении техническими системами и технологическими процессами

3.ИНФОРМАЦИОННЫЕ ТЕХНОЛОГИИ

ВУПРАВЛЕНИИ ТЕХНИЧЕСКИМИ СИСТЕМАМИ

ИТЕХНОЛОГИЧЕСКИМИ ПРОЦЕССАМИ. МЕХАТРОННЫЕ И РОБОТОТЕХНИЧЕСКИЕ СИСТЕМЫ, КОМПЛЕКСЫ И УСТРОЙСТВА

УДК 519.854.2 + 658.5 ББК 65.290-2

МНОГОРЕСУРСНАЯ ЗАДАЧА ЦЕХОВОГО ПЛАНИРОВАНИЯ: ОСОБЕННОСТИ

РЕАЛИЗАЦИИ И СРАВНЕНИЕ ПОДХОДОВ1

Лазарев А.А.2, Некрасов И.В.3

(Институт проблем управления им. В.А. Трапезникова РАН, Москва)

В статье обсуждаются две базовых постановки задачи планирования при ограниченных ресурсах (RCPSP): для непрерывного

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

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

Ключевые слова: RCPSP, задача цехового планирования, MESсистема, многоресурсное планирование, целочисленное линейное программирование (ЦЛП), вычислительная трудоемкость.

1Исследование выполнено за счет гранта Российского научного фонда

(проект №17-19-01665)

2Александр Алексеевич Лазарев, доктор физико-математических наук, заведующий лабораторией 68 ([e-mail]).

3Иван Васильевич Некрасов, кандидат технических наук, старший научный сотрудник лаборатории 68 ([e-mail]).

217

255

Управление большими системами. Выпуск XX

1. Введение

Решение задачи планирования в различных ее вариациях является центральной проблемой управления на современном предприятии [1, 5]. Плановые службы в обязательном порядке присутствуют в штатном расписании любого промышленного предприятия, осуществляя разработку и контроль исполнения планов различного уровня. Процесс планирования, как правило, разбивается по уровням: общий долгосрочный стратегический план, генерируемый на уровне ERP-систем [3], детализируется затем по подразделениям и отдельным ресурсам в MESсистемах [8, 9], после чего на местах осуществляется его исполнение и оперативная корректировка (в случае необходимости). Наиболее детальная и трудоемкая часть процесса планирования осуществляется на среднем, так называемом «цеховом», уровне в упомянутых выше MES-системах. Причина повышенной сложности задачи цехового планирования кроется в необходимости выполнять поставленные на более высоком уровне общие цели, с одной стороны, и учитывать локальные (цеховые) ограничения, с другой стороны. Таким образом, в отличие от ERP-уровня, где применимы упрощенные модели стратегического объемного планирования [6], в задаче планирования MES-уровня используются полные модели календарного планирования, дополнительно учитывающие последовательность технологических операций и их распределение по ресурсам (людям, станкам и т.п.) [1]. Ранее авторами были проанализированы математические модели цехового планирования для операций, задействующих ресурс одного типа (например, станки). Однако в ходе практической апробации моделей выяснилось, что на реальном производстве массово распространенным является случай, когда каждая операция одновременно задействует несколько ресурсов разных типов [4, 8, 9] (станки, персонал, оснастка, расходный материал и т.п.). Исследования, проведенные в рамках данной работы, показывают, как изменяются постановки и модели планирования при введении ресурсов нескольких типов.

218

256

Информационные технологии в управлении техническими системами и технологическими процессами

2. Модели одноресурсной задачи цехового планирования

С точки зрения математической формализации задача цехового планирования относится к классу RCPSP (Resourceconstrained Project Scheduling Problem), являясь его прикладным частным случаем [6]. Математические модели задачи RCPSP применительно к цеховому уровню планирования могут быть сгруппированы по типу временной шкалы – задачи с непрерывным и с дискретным временем [7]. Краткие постановки задач приведены ниже [7].

2.1. ИСХОДНЫЕ ДАННЫЕ И ОБОЗНАЧЕНИЯ

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

– работа цеха осуществляется с использованием однотипных ресурсов (например, станков), множество которых обозна-

чено R = {Rr } , r =1, , R;

– технологический маршрут выпуска конечного изделия цеха задан множеством технологических операций J , упорядо-

ченных в виде ориентированного графа, который описан матри-

цей G = gij ,	i =1, , J ,	j = 1, , J . Элемент матрицы gij = 1,
если операция	j в технологическом маршруте следует за опе-
рацией i . Во всех остальных случаях элемент gij = 0 ;
– каждая	операция i	характеризуется списком ресурсов

{rk }i ,k Z , которые привлекаются для ее выполнения, и дли-

тельностью τi ;

– использование ресурсов по всем операциям представлено матрицей Op = opir , i =1, , J , r =1, , R . Элемент матрицы opir = 1, еслиоперация i в технологическоммаршрутеиспользует ресурс r . Вовсехостальныхслучаяхэлемент opir = 0;

219

257

Управление большими системами. Выпуск XX

– задание F на производство партии конечного продукта носит название «заказ цеха» и характеризуется двумя величина-

ми: объемом заказа в штуках конечного продукта v f и директивным сроком заказа d f (здесь f = 1, , F ).

2.2.ЗАДАЧА В НЕПРЕРЫВНОМ ВРЕМЕНИ

Внепрерывном времени переменными задачи планирования

выбираются моменты начала каждой i -й операции каждого f-го

заказа xif ≥ 0 ( i = 1, J ;	f	= 1, F ) [3,7]. Переменные xif ≥ 0
объединим в F векторов	x f	≥ 0 . Ограничения задачи представ-

лены матричными неравенствами [7]:

– соблюдение последовательности операций технологиче-

ского процесса:	G xf	≥ (xf	+ τ) , f = 1,..., F;
(1)

–упорядочение одноименных операций различных заказов

сцелью исключения конфликтов на ресурсах:

≥ xf + τ , f = 1,...,(F − 1);( f +1)

– объединение одноименных операций разных заказов в группы и упорядочивание полученных групп на каждом ре-

сурсе с целью исключения конфликтов на ресурсах:
(3)	Op G x1 ≥ Op (xF + τ);
	– соблюдение директивных сроков всех заказов:
(4)	xJf + τJ ≤ d f , f = 1,..., F.

2.1.ЗАДАЧА В ДИСКРЕТНОМ ВРЕМЕНИ

Вдискретном варианте временная шкала от текущего момента (в который производится непосредственно планирование) до некоторой точки в будущем (называемой «горизонтом пла-

нирования» T ) разбивается на H временных отрезков равной длины [7]:

T = { 1, , H }

220

258

Информационные технологии в управлении техническими системами и технологическими процессами

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

– x fjt Z – накопленный объем работ операции j заказа

f к окончанию временного отрезка t (здесь j = 1, J , f = 1, F , t = 1, H );

– z fjt {0,1} – признак завершенности операции j заказа

fк окончанию временного отрезка t ;

–y jt Z – количество промежуточной продукции опера-

ции j от всех заказов f = 1, , F , произведенной к окончанию временного отрезка t .

Ограничения задачи представлены матричными неравенствами [7]:

– накопленный объем работ по каждой операции со временем не может уменьшаться:

(5)	xfjt	≥ x	(	)	;
			f , j,	t −1

– операция j заказа		f считается выполненной только при
полном выполнении его объема:
(6)	ν j	z fjt ≤ xfjt .
Здесь ν j	соответствует	требуемому объему промежуточной

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

процесса);

– Выполнение операции j каждого заказа f начинается

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

(7) xfjt gij ≤ν i z fit .

Ограничения (7) формируются для всех операций графа пред-

шествования j =1,..., J , i =1,..., J;

	– ограничение соблюдения директивных сроков всех зака-
зов	f = 1, , F :
(8)	z f J t = 1;
	221
	259

Управление большими системами. Выпуск XX

– в каждый момент времени прибавка промежуточной продукции каждой операции графа предшествования должна соответствовать суммарной разнице накопленного объема данной операции по всем заказам:

	F		t −1 )≤ y jt ;
(9)	(xfjt	− xf , j,
		(	)

f=1

–загрузка каждого ресурса в каждый момент времени не должна превышать максимально допустимую загрузку:

	F	J
(10)	opjr y jt ≤ crt .
	f =1	j=1

3. Расширение моделей цехового планирования на многоресурсный случай

На практике цеховое планирование в большинстве случаев осуществляется применительно к ресурсам разного типа [4, 8, 9]. Например, операции технологического маршрута должны быть распределены между станками, а для выполнения каждой операции требуется рабочий определенной квалификации. В этом случае при формализации задачи планирования исходное единствен-

ное множество ресурсов одного типа R = {Rr }, r = 1, , R

заменяется на совокупность нескольких множеств ресурсов различных типов:

M

R = Rm ,

m =1

где M – количество типов ресурсов цеха.

В данной постановке задачи для каждого типа ресурсов имеем отдельную матрицу использования ресурсов

Opm = opir m , i = 1, , J , r = 1, , Rm , m = 1, , M . Фор-

мально наличие отдельных матриц использования ресурсов означает кратное дублирование исходной оптимизационной задачи (ЛП или ЦЛП) с различными ограничениями. Таким образом, процесс многоресурсного планирования сводится к совместному решению M задач ЛП или ЦЛП. Однако обратим внимание, что переменные задачи привязаны к операциям

222

260