УДК 658.512.012.011.56:665.6
Автоматизированное проектирование схем размещения объектов предприятий из условия минимизации коммуникационных затрат
И.М. Зуга, В.Г. Хомченко
ОАО «Омскнефтехимпроект»,
Омский государственный технический университет
Реферат
Предложены математическая модель оптимизационного синтеза и алгоритм автоматизированного проектирования схем размещения объектов предприятий при незакрепленных местах их возможного расположения из условия минимизации затрат на коммуникационные связи с учетом ограничений на минимально допустимые расстояния на просвет между этими объектами. Ил. 3. Библ. 7.
Ключевые слова: схемы размещения объектов, автоматизированное проектирование, уровни удельных затрат
При проектировании предприятий различных отраслей промышленности: машиностроительной, нефтехимической и других - важной задачей является рациональное размещение тех или иных объектов структурных подразделений на выделенной для них площади: станков и другого оборудования производственных участков, цехов и отдельных производств в рамках предприятий в целом.
Известно решение задачи о размещении объектов на предварительно выделенные места [1,2]. В данной работе рассматривается задача автоматизированного проектирования схем размещения объектов того или иного производственного подразделения при незакрепленных местах возможного расположения объектов.
На первом уровне абстракции будем представлять объекты в виде прямоугольников либо окружностей, охватывающих в плане контуры объектов.
В коммуникационные затраты включим все возможные затраты, связанные с созданием (проектированием, изготовлением, монтажом и т. п.) и эксплуатацией коммуникаций между объектами и необходимые для выполнения этими объектами их функционального назначения.
Так как задача о размещении объектов решается, как правило, на начальной стадии проектирования, когда известны лишь ориентировочные оценки затрат на реализацию коммуникаций между объектами, то целесообразно перейти на этом этапе от оценки затрат в тех или иных абсолютных единицах к некоторым условным уровням затрат, представляющим собой экспертную оценку удельных (приходящихся на единицу длины коммуникаций) затрат в принятой предварительно системе баллов. Принятая система баллов должна адекватно отражать ранжированную последовательность, например, по убыванию предполагаемых удельных затрат на коммуникационные связи. Тогда условные коммуникационные затраты между каждой парой объектов можно выразить следующей зависимостью:
, (i=1,…, n-1; j=i+1,…, n) (1)
где - уровни удельных затрат на реализацию коммуникационных связей между i-м и j-м объектами;
- длина коммуникаций между i-м и j-м объектами;
X
и Y
- векторы координат и центров i-го j-го объектов размерностью n1;
n
- число объектов рассматриваемой производственной структуры.
Условные коммуникационные затраты рассматриваемой производственной системы с учетом (1) будут равны:
(i=1,…, n-1; j=i+1,…, n) (2)
Поскольку, как отмечалось, решение о размещении объектов принимается на начальной стадии проектирования в условиях неопределенности [3], то целесообразно, не нарушая строгости постановки задачи, в качестве длины коммуникаций принять кратчайшее расстояние между центрами объектов, а именно:
, (i=1,…,n-1; j=i+1,…,n) (3)
где , и , - координаты центров прямоугольников либо окружностей, представляющих соответственно i-й и j-й объекты в принятой системе координат.
На последующих этапах проектирования можно использовать уточненные данные как по удельным затратам на коммуникационные связи, так и по способу расчета длины коммуникаций.
На взаиморасположение объектов производственных подразделений, как правило, накладывается целый ряд ограничений, характерных для конкретной отрасли промышленности. В данной работе без потери общности в качестве таких ограничений примем минимально допустимое расстояние между объектами на просвет, как наиболее характерное для большинства отраслей промышленности.
При решении задачи о размещении объектов удобно использовать в качестве дополнительных условий синтеза минимально допустимое расстояние между центрами i-го и j-го объектов, определяемое зависимостью
, (i=1,…,n; j=1,…,n) (4)
если объекты представлены в виде прямоугольников, и выражением
(i=1,…,n-1; j=i+1,…,n) (5)
если - в виде окружностей (здесь: - регламентированное минимально допустимое расстояние на просвет между i-м и j-м объектами; , , , и , - длина, ширина и радиус соответственно прямоугольников и окружностей, охватывающих в плане i-й и j-й объекты).
С учетом выражений (3), (4) и (5) допустимая область возможного расположения центров объектов будет ограничиваться системой неравенств:
, (i=1,…, n-1; j=i+1,…, n) (6)
Для выполнения условия (6) в ходе автоматизированного проектирования схем размещения объектов воспользуемся так называемой функцией штрафа, а именно:
, (7)
где - частная штрафная функция, равная
0, если ;
если .
На основе зависимостей (2) и (7) запишем целевую функцию вида
Z=minW(X,Y), (8)
X,YV
где ;
V
- область возможных (допустимых) значений векторов X и Y;
- параметр, позволяющий регулировать влияние функции штрафа (7) на свойства целевой функции (8).
Отметим, что векторы X и Y являются в данном случае множеством свободных параметров целевой функции Z.
Поиск минимума целевой функции (8) представляет собой типичную задачу нелинейного программирования, для решения которой можно воспользоваться теми или иными известными методами [4-7]. В данной работе для автоматизированного поиска оптимального решения задачи о размещении объектов использован градиентный метод [4], алгоритм которого представлен на рисунке 1.
В блоке 1 вводятся значения уровней удельных затрат; размеры прямоугольников либо окружностей, представляющих контуры объектов в плане; минимально допустимые расстояния между объектами на просвет и, при необходимости, другие данные. В блоке 2 свободным параметрам синтеза и (i=1,…,n) присваиваются значения, соответствующие начальному приближению оптимизационной задачи. Блок 3 предназначен для расчета целевой функции при начальном приближении свободных параметров. В блоке 4 численно определяются частные производные по параметрам и (i=1,…,n), а в блоке 5 – новые значения свободных параметров в направлении антиградиента. После расчета целевой функции (8) при новых значениях свободных параметров в блоке 6 ее значение сравнивается в блоке 7 со значением, полученным на предыдущем шаге l
итерации, и в зависимости от результата сравнения расчет либо продолжается с запоминанием нового значения целевой функции в блоке 8, либо завершается. В последнем случае в блоке 9 выводятся в той или иной форме результаты решения данной оптимизационной задачи.
Приведем пример автоматизированного решения задачи о размещении для пяти объектов. При решении данного примера будем считать, что уровни удельных коммуникационных затрат, длина коммуникаций между объектами и другие линейные размеры являются относительными (безразмерными) величинами.
Зададим регламентированные минимально допустимые расстояния между объектами на просвет и уровни затрат соответственно таблицами 1 и 2, а размеры прямоугольников, представляющих объекты, - таблицей 3. Уровни коммуникационных затрат назначены по некоторой 20-балльной шкале. В качестве начального приближения примем расположение объектов с координатами, указанными в таблице 4.
При принятом начальном приближении условия (6) не выполняются, а значение целевой функции равно 44 810.
В результате оптимизационного вычислительного процесса на основе предложенного алгоритма найдены координаты центров объектов, представленные в таблице 5. Значение целевой функции при этом удалось снизить до 14 430 и выполнить все условия (6). Полученное значение целевой функции лишь на 0,3% отличается от предельно возможного, равного 14 390.
В таблице 6 приведены отклонения фактических расстояний между объектами от регламентированных. Процесс решения задачи приведен на рисунках 2 и 3, при этом на рисунке 2 представлены в целях наглядности траектории центров объектов, а на рисунке 3 дополнительно нанесены геометрические образы объектов при начальных и конечных значениях координат центров объектов.
В заключение отметим, что поставленная в данной статье задача автоматизированного проектирования схем размещения объектов при незакрепленных предварительно местах их возможного расположения может быть решена с использованием предложенного подхода при достаточно хорошей сходимости вычислительного процесса и гарантированном выполнении минимально допустимых расстояний между объектами. Разработанный метод может быть применен при проектировании предприятий различных отраслей промышленности, в частности, машиностроительной, нефтехимической и других.
Библиографический список
1. Козловский В.А. Организационные и экономические вопросы построения производственных систем. Л.: ЛГУ,1981. - 216 с.
2. Gavett T.W., Plyter N.V. The optimal assignment of Facilities to locations by branch and bound. – Operations Research, 1966, vol.14, №2, p. 210-232.
3. Грундинг К.-Г. Проектирование промышленных предприятий: Принципы. Методы. Практика / Клаус-Герольд Грундинг; Пер. с нем. - М.: Альпина Бизнес Букс, 2007. – 340 с.
4. Бояринов А.И. Кафаров В.В. Методы оптимизации в химической технологии. М., Химия, 1975. – 576 с.
5. Химмельблау Д.М. Прикладное нелинейное программирование. М., Мир, 1975. – 534 с.
6. Уайлд Д. Оптимальное проектирование. М., Мир, 1981. – 272 с.
7. Васильев Ф.П. Численные методы решения экстремальных задач. М., Наука, 1988. – 552 с.
Табл. 1
Регламентированные минимально допустимые расстояния
между объектами на просвет
| j i |
1 |
2 |
3 |
4 |
5 |
| 1 |
0 |
70 |
100 |
110 |
:center;">60 |
| 2 |
0 |
0 |
45 |
150 |
130 |
| 3 |
0 |
0 |
0 |
80 |
95 |
| 4 |
0 |
0 |
0 |
0 |
20 |
Табл. 2
Уровни удельных затрат на коммуникационные связи
| j i |
1 |
2 |
3 |
4 |
5 |
| 1 |
0 |
2 |
20 |
15 |
1 |
| 2 |
0 |
0 |
1 |
18 |
16 |
| 3 |
0 |
0 |
0 |
5 |
10 |
| 4 |
0 |
0 |
0 |
0 |
3 |
Табл. 3
Размеры геометрических образов объектов
| № объектов |
1 |
2 |
3 |
4 |
5 |
| a |
40 |
20 |
60 |
40 |
30 |
| b |
20 |
20 |
40 |
40 |
10 |
Табл. 4
Начальные значения координат центров объектов
| № объектов |
1 |
2 |
3 |
4 |
5 |
| x |
80 |
60 |
110 |
140 |
120 |
| y |
100 |
130 |
150 |
125 |
90 |
Табл. 5
Значения координат центров объектов,
полученные в результате оптимизационного поиска
| № объектов |
1 |
2 |
3 |
4 |
5 |
| x |
45.635 |
11.824 |
93.266 |
197.787 |
143.306 |
| y |
53.622 |
154.615 |
204.708 |
105.163 |
63.525 |
Табл.
6
Отклонения фактических расстояний
между объектами на просвет от регламентированных
| j i |
1 |
2 |
3 |
4 |
5 |
| 1 |
0 |
0 |
0 |
0 |
0 |
| 2 |
0 |
0 |
0.417 |
0 |
0 |
| 3 |
0 |
0 |
0 |
0 |
2.922 |
| 4 |
0 |
0 |
0 |
0 |
4.475 |
Рис.1 Алгоритм оптимизационного синтеза схем размещения объектов
Рис. 2 Траектории движения центров объектов в ходе оптимизационного синтеза схем размещения объектов
Рис. 3 Положения геометрических образов объектов при начальных и конечных значениях координат их центров
Computer-aided design
(CAD)
of the facilities location
under condition of communications expenses minimization
Zuga I.M., Khomchenko V.G.
Omskneftekhimproekt JSC, Omsk state technical university
The abstract
The mathematical model of optimization synthesis and algorithm of the Computer-aided design (CAD) applied for the location of the facilities with variable assignment under condition of communications expenses minimization and feasible minimum distances constraints considered between the facilities are proposed. Fig. 3. Ref. 7.
Key words: Location of the Facilities, Computer Aided Design (CAD), marginal costs curve
Сведения об авторах
Зуга Игорь Михайлович, генеральный директор ОАО «Омскнефтехимпроект», тел. раб. (3812) 28-55-34, onhp@omsknet.ru
Хомченко Василий Герасимович, доктор технических наук, профессор, заведующий кафедрой «Автоматизация и робототехника» ОмГТУ, тел. раб. (3812) 65-21-76, v_khomchenko@mail.ru