基于SA-QPSO算法的多層制造單元內(nèi)部布局方法

摘 要：針對(duì)多層制造單元內(nèi)部的設(shè)備布局優(yōu)化問(wèn)題，本文建立考慮單元尺寸、物料搬運(yùn)量、損失時(shí)間以及單元穩(wěn)定性的多目標(biāo)優(yōu)化數(shù)學(xué)模型。為更快速、高效地求解該問(wèn)題，使用模擬退火算法（Simulated Annealing，SA）確定單元內(nèi)設(shè)備所在平面以及層面，使用量子粒子群算法（Quantum Particle Swarm Optimization，QPSO）確定設(shè)備具體坐標(biāo)值和所在高度。以某汽車(chē)零件加工車(chē)間為實(shí)例，運(yùn)用SA-QPSO算法生成直線形、“U”形和環(huán)形3種最優(yōu)空間布局方案，驗(yàn)證了SA-QPSO算法在多層制造單元內(nèi)部布局方法設(shè)計(jì)方面的可行性。

關(guān)鍵詞：多層制造單元；布局優(yōu)化；模擬退火算法；量子粒子群算法

中圖分類(lèi)號(hào)：TU 318 文獻(xiàn)標(biāo)志碼：A

設(shè)施布局（Facility Layout Problem，F(xiàn)LP）是智能工廠建設(shè)的重要環(huán)節(jié)，科學(xué)合理的設(shè)備布局有重要的意義[1]。隨著使用智能化物流的智能工廠興起，多層制造單元的布局方式越來(lái)越多，許多學(xué)者對(duì)制造單元布局問(wèn)題進(jìn)行深入研究，例如王沙沙等[2]針對(duì)雙向環(huán)形過(guò)道布置問(wèn)題建模并使用混合鯨魚(yú)算法有效求解。丁祥海等[3]以“U”形生產(chǎn)單元為研究對(duì)象，建立了單元生產(chǎn)可重構(gòu)設(shè)施布局決策集成模型，并設(shè)計(jì)了決策問(wèn)題的遺傳算法。目前國(guó)內(nèi)外主要研究單層制造單元，多層制造單元相關(guān)研究較少，其中，單目標(biāo)優(yōu)化模型或雙目標(biāo)優(yōu)化模型的搬運(yùn)成本最低、單元利用率最高?；诖耍疚目紤]了眾多制造車(chē)間的實(shí)際需求，構(gòu)建多目標(biāo)優(yōu)化數(shù)學(xué)模型，研究多層制造單元內(nèi)部設(shè)備布局方法。

1 多層制造單元車(chē)間內(nèi)部布局問(wèn)題描述以及數(shù)學(xué)模型構(gòu)建

1.1 問(wèn)題描述及假設(shè)

多層制造單元內(nèi)部設(shè)備形狀以矩形為主，常見(jiàn)分類(lèi)有直線形制造單元、“U”形制造單元和環(huán)形制造單元。通過(guò)構(gòu)建X、Y、Z坐標(biāo)系，可立體表述制造單元，如圖1所示。其中，Z1為XOY平面，Z2為與XOY平面平行的平面，Z3為YOZ平面，Z4為與YOZ平面平行的平面，Z1、Z2、Z3和Z4均穿過(guò)設(shè)備中心，同層設(shè)備中心在同一條水平線上。

將單元布局平面抽象化。如圖2所示。其中，直線形制造單元內(nèi)設(shè)備布局僅在平面Z1和Z2內(nèi)；“U”形制造單元內(nèi)設(shè)備布局僅在平面Z1、Z2和Z3內(nèi)；環(huán)形制造單元內(nèi)設(shè)備布置在所有平面內(nèi)。

通過(guò)構(gòu)建相同的目標(biāo)函數(shù)，采用約束條件選擇不同的布局形式，求解不同的設(shè)備排列組合中最優(yōu)的順序布置，獲得最佳布局。

1.2 目標(biāo)函數(shù)

本文以單元體積最小、物流搬運(yùn)強(qiáng)度最低、制造損失時(shí)間最短和單元穩(wěn)定性最高為目標(biāo)構(gòu)建多目標(biāo)數(shù)學(xué)模型。

1.2.1 單元體積目標(biāo)

多層制造單元占用空間為單元體積，主要受長(zhǎng)、寬和高3個(gè)要素影響，當(dāng)3個(gè)要素最小時(shí)，單元體積就最小，目標(biāo)函數(shù)如公式（1）所示。

minV=LWH （1）

式中：V為單元體積；L為單元長(zhǎng)度，在單元內(nèi)設(shè)備的中心坐標(biāo)的x值與設(shè)備投影到X軸上的一半之和或之差組合的集合中，最大值和最小值之差即單元長(zhǎng)度目標(biāo)；W為單元寬度，在單元內(nèi)設(shè)備的中心坐標(biāo)的z值與設(shè)施投影到Z軸上的一半之和或之差組合的集合中，最大值和最小值之差即單元寬度；H為單元高度目標(biāo)，可將單元內(nèi)每個(gè)設(shè)備的中心在Y軸上的坐標(biāo)值y與該設(shè)備投影到Y(jié)軸上尺寸的一半相加，求得的結(jié)果組成的集合為單元高度集，集合中最大值就是制造單元所需的最低高度，即單元高度目標(biāo)。

1.2.2 物料搬運(yùn)目標(biāo)

本文搬運(yùn)距離采用與物流搬運(yùn)實(shí)際距離更接近的曼哈頓距離，如公式（2）所示。

dij=|xi-xj|+|yi-yj|+|zi-zj| （2）

式中：dij為設(shè)備i到設(shè)備j的曼哈頓距離，設(shè)備i中心坐標(biāo)為（xi，yi，zi），設(shè)備j中心坐標(biāo)為（xj，yj，zj）。

第p號(hào)產(chǎn)品從設(shè)備i到設(shè)備j的物料搬運(yùn)批量為ceil[]，搬運(yùn)目標(biāo)如公式（3）所示。

（3）

式中：D為物料搬運(yùn)強(qiáng)度；M為設(shè)備總數(shù)量；P為產(chǎn)品總數(shù)量；i、j為設(shè)備編號(hào)；p為加工產(chǎn)品種類(lèi)編號(hào)；ceil為取整；Vp為第p號(hào)產(chǎn)品待加工總數(shù)量；Bp為第p號(hào)產(chǎn)品一次搬運(yùn)數(shù)量。

1.2.3 損失時(shí)間目標(biāo)

在生產(chǎn)線平衡問(wèn)題中，損失時(shí)間為衡量制造單元平衡的重要指標(biāo)之一，因此設(shè)損失時(shí)間目標(biāo)，如公式（4）所示。

（4）

式中：T為損失時(shí)間目標(biāo)；np為設(shè)備總數(shù)；qi為第i個(gè)設(shè)備加工以及運(yùn)輸?shù)降趇+1個(gè)設(shè)備的時(shí)間。

1.2.4 穩(wěn)定性目標(biāo)

在多層制造單元設(shè)備布局中，需要考慮設(shè)備的穩(wěn)定性，穩(wěn)定性目標(biāo)B越小就越穩(wěn)定，目標(biāo)函數(shù)如公式（5）所示。

（5）

式中：yi為設(shè)備i的中心高度；wi為設(shè)備i的質(zhì)量。

1.3 約束條件

在設(shè)定具體約束前，須設(shè)定的基本約束如下。設(shè)備i的中心坐標(biāo)（xi，yi，zi）為優(yōu)化問(wèn)題的決策變量；（li，wi，hi）為設(shè)備對(duì)應(yīng)的長(zhǎng)、寬、高；設(shè)備單元集均在X、Y、Z軸正方向上，不考慮X、Y、Z軸負(fù)方向，任意設(shè)備不能超過(guò)單元的邊界。

1.3.1 邊界約束

邊界約束為設(shè)備對(duì)應(yīng)長(zhǎng)度li的一半與中心點(diǎn)xi坐標(biāo)之和≤單元Z軸方向的長(zhǎng)度邊界約束Lg，設(shè)備所對(duì)應(yīng)寬度wi的一半與中心點(diǎn)yi坐標(biāo)之和≤單元X軸方向的寬度邊界約束Wg，設(shè)備對(duì)應(yīng)高度hi與中心點(diǎn)zi坐標(biāo)之和≤單元Y軸方向的高度約束Hg。

1.3.2 設(shè)備位置約束

設(shè)備中心必須位于平面Z1、Z2、Z3和Z4上，zi為非負(fù)區(qū)域。假設(shè)PSi∈I為設(shè)備中心Zi面的歸屬，當(dāng)PSi=1時(shí)，zi=0；當(dāng)PSi=2時(shí)，zi=Z2_value；當(dāng)PSi=3時(shí)，xi=0；當(dāng)PSi=4時(shí)，xi=Z4_value。其中，Z2_value為Z2面的z坐標(biāo)，Z4_value為Z4面的x坐標(biāo)。

1.3.3 單元集形狀約束

假設(shè)Type_choose∈{1，2，3}為單元集形狀，當(dāng)Type_choose=1時(shí)，直線形僅選擇平面Z1、Z3；當(dāng)Type_choose=2時(shí)，“U”形僅選擇平面Z1、Z2以及Z3；當(dāng)Type_choose=3時(shí)，環(huán)形選擇平面Z1、Z2、Z3以及Z4。

1.3.4 高度層級(jí)約束

假設(shè)Yk為第k個(gè)高度層級(jí)，Yi=0只能從Yk（k=1，2，…，r）中取值，即yi∈{Yk：k=1，2，…，r}。

2 基于SA-QPSO算法的目標(biāo)函數(shù)求解

2.1 設(shè)備布局方案的編碼與生成

在優(yōu)化問(wèn)題中，粒子群優(yōu)化算法（Particle Swarm Optimization，PSO）和模擬退火算法（Simulated Annealing，SA）都是常見(jiàn)且有效的算法，量子粒子群算法（Quantum Particle Swarm Optimization，QPSO）是基于PSO算法提出的一種改進(jìn)算法[4]。本文采用了一種改進(jìn)的混合算法，稱為量子粒子群優(yōu)化算法（SA-QPSO），并將其應(yīng)用于求解單元內(nèi)部設(shè)備布局最優(yōu)化問(wèn)題。流程如圖3所示。

2.1.1 初步布局方案

設(shè)備j隨機(jī)生成數(shù)i和數(shù)k，i∈{1，2，3，4}，k∈{1，2，…，r}，表示將設(shè)備j分配至Zi面的第k層中，由此可得Aik，即Zi面第k層高度的設(shè)備編號(hào)升序向量。設(shè)Aik共有mik個(gè)元素，如果mik＞0，則生成一個(gè)mik維的各分量取值為（0，1）的隨機(jī)向量Vik，根據(jù)Vik各分量的大小關(guān)系對(duì)Aik進(jìn)行排序，結(jié)合Aik和Vik可得設(shè)備在zi面第k層上沿x正向或z正向的有序排布，得到初步布局方案。

2.1.2 Z4的x值生成

僅考慮x方向的干涉，從平面Z1、Z2找出x坐標(biāo)最大的設(shè)備，使其不與Z4內(nèi)最長(zhǎng)的設(shè)備發(fā)生干涉，又因?yàn)閾Q行約束，所以Z4≥Lz，Z4的下界lb4和上界ub4如公式（6）、公式（7）所示。

（6）

式中：Lz為換行約束；Zik，j為Zi的第k層中的第j個(gè)設(shè)備的前向中心間隔；lik，end為平面Zi第k層高度最后1個(gè)設(shè)備的長(zhǎng)度；l4k，j為平面Z4第k層高度設(shè)備j的長(zhǎng)度；G1為給定常數(shù)值。

（7）

式中：Lg為單元Z軸方向的長(zhǎng)度邊界約束。

由于此時(shí)最大余量為正，因此ub4gt;lb4，如公式（8）所示。

Z4=lb4+（ub4-lb4）·Z4_ratio " " "（8）

式中：Z4_value為隨機(jī)數(shù)且Z4_ratio∈（0，1）。

2.1.3 Z2的Z值生成

Z2的下界lb2和上界ub2如公式（9）、公式（10）所示。

（9）

式中：Wz為換行約束；zik，j為Zi的第k層中的第j個(gè)設(shè)備的前向中心間隔；wik，end為平面Zi第k層高度最后1個(gè)設(shè)備的寬度；w2k，j為平面Z2第k層高度設(shè)備j的寬度；G3為給定常數(shù)值。

（10）

式中：Wg為單元X軸方向的寬度邊界約束。

設(shè)隨機(jī)數(shù)Z2-ratio∈（0，1），如公式（11）所示。

Z2=lb2+（ub2-lb2）·Z2-ratio （11）

至此，分配至Z1、Z2、Z3和Z4的設(shè)備都已定x坐標(biāo)和z坐標(biāo)：平面Z1的z=0；平面Z2的z值已生成；平面Z3的x=0；平面Z4的x值已生成。

2.1.4 高度層級(jí)Yk的生成

假設(shè)ηk為第k層設(shè)備的最大高度，那么以層級(jí)r=3為例進(jìn)行分析，如圖4所示。

對(duì)各層的最高設(shè)備按層級(jí)順序編號(hào)，計(jì)算步驟如下。

步驟一：計(jì)算設(shè)備最大余量，如公式（12）所示。

（12）

式中：Marginymax為設(shè)備上側(cè)Y軸坐標(biāo)的最大邊緣值即最大余量；ηk為第k層高度設(shè)備的最大高度；r為高度層；Hg為設(shè)備對(duì)應(yīng)高度hi與中心點(diǎn)zi坐標(biāo)之和≤單元Y軸方向的高度約束；G2為給定常數(shù)值。如果最大余量≤0，則判定無(wú)解Marginymax為最大余量。

步驟二：生成r-1維（0，1）隨機(jī)向量，如公式（13）、公式（14）所示。

ra=[ra1，ra2，…，rar-1] （13）

（14）

式中：φk為第k個(gè)最高設(shè)備的前向中心間隔，φ1取0，k≥2；βy為占比向量；yratio為生成隨機(jī)數(shù)且yratio∈（0，1）。

步驟三：生成高度層級(jí)，如公式（15）所示。

（15）

至此，生成布局方案且各約束均得到了滿足，可得到可行布局方案或判定無(wú)解。該問(wèn)題外層為帶有簡(jiǎn)單約束的組合優(yōu)化問(wèn)題，使用帶有罰函數(shù)的SA算法進(jìn)行優(yōu)化，使各高度層級(jí)均有設(shè)備；內(nèi)層為無(wú)約束優(yōu)化問(wèn)題，使用QPSO算法進(jìn)行求解。

2.2 SA算法

2.2.1 解的編碼與初始化

假設(shè)共有n個(gè)設(shè)備，以2×n的整數(shù)矩陣來(lái)表示設(shè)備組的Zi面屬性和高度層級(jí)屬性，每列對(duì)應(yīng)1個(gè)設(shè)備，第一行為Zi面屬性，第二行為高度層級(jí)屬性。根據(jù)矩陣進(jìn)行。

編碼下界矩陣如公式（16）所示。

（16）

直線形上界矩陣如公式（17）所示。

（17）

“U”形上界矩陣如公式（18）所示。

（18）

環(huán)形上界矩陣如公式（19）所示。

（19）

2.2.2 適應(yīng)度函數(shù)

對(duì)該嵌套形式的優(yōu)化問(wèn)題來(lái)說(shuō)，SA算法的適應(yīng)度為內(nèi)層QPSO算法的最優(yōu)適應(yīng)度值。在最大化目標(biāo)中，令適應(yīng)度為-M；在最小化目標(biāo)中，令適應(yīng)度為M。其中，M為充分大的正數(shù)。

2.3 QPSO算法

在QPSO算法中，通過(guò)粒子可以搜索整個(gè)可行解空間，并將粒子群算法中的速度和位置更新公式進(jìn)行了替換[5]。同時(shí)該算法以概率分布機(jī)制替代原有機(jī)制，提高了全局搜索的能力，也提高了算法收斂的精度和速度[6]。QPSO 算法的具體步驟如下。

步驟一：初始化粒子位置，并設(shè)置初始個(gè)體最優(yōu)值。

步驟二：計(jì)算各粒子的適應(yīng)度值。

步驟三：比較粒子適應(yīng)度值的大小，更新個(gè)體最優(yōu)和全局最優(yōu)。

步驟四：更新粒子位置，如公式（20）所示。

（20）

式中：為最新粒子位置信息；pit，j為局部吸引子；Cjt為粒子當(dāng)前個(gè)體最優(yōu)的均值；α為控制參數(shù)；u為隨機(jī)變量，由此得到新位置。

步驟五：按照一定的變異概率對(duì)個(gè)體最優(yōu)進(jìn)行高斯擾動(dòng)，即加入服從高斯分布的隨機(jī)數(shù)來(lái)提升算法多樣性。

步驟六：重復(fù)步驟二～步驟四直到滿足停止條件。

3 應(yīng)用實(shí)例

3.1 實(shí)例描述

采用上述算法對(duì)某汽車(chē)零件單元生產(chǎn)車(chē)間進(jìn)行布局優(yōu)化，本文選擇該車(chē)間的15臺(tái)設(shè)備為研究對(duì)象，共生產(chǎn)12種產(chǎn)品，設(shè)備信息包括設(shè)備編號(hào)、設(shè)備尺寸（長(zhǎng)、寬和高）、設(shè)備質(zhì)量以及每臺(tái)設(shè)備加工1次的加工時(shí)間，具體信息見(jiàn)表1。

根據(jù)產(chǎn)品的工藝性對(duì)產(chǎn)品進(jìn)行編號(hào)，該車(chē)間的加工產(chǎn)品信息包括加工批量、搬運(yùn)批量以及加工產(chǎn)品所經(jīng)過(guò)設(shè)備的工藝路徑，具體信息見(jiàn)表2。

3.2 結(jié)果比較和分析

通過(guò)實(shí)例求解得到3種布局形式的最優(yōu)布局方案，解碼后得出了3種形狀的最優(yōu)單元布局方案。

在直線形單元布局中，平面Z1有7臺(tái)設(shè)備，平面Z2有8臺(tái)設(shè)備。具體布局方案如圖5所示。

在“U”形單元布局中，平面Z1有8臺(tái)設(shè)備，平面Z3有1臺(tái)設(shè)備，平面Z2有6臺(tái)設(shè)備。具體布局方案如圖6所示。

在環(huán)形單元布局中，平面Z1有5臺(tái)設(shè)備，平面Z3有2臺(tái)設(shè)備，平面Z2有6臺(tái)設(shè)備，平面Z4有2臺(tái)設(shè)備。具體布局方案如圖7所示。

SA-QPSO算法當(dāng)更新解時(shí)不會(huì)受目標(biāo)數(shù)值的數(shù)量級(jí)大小影響，而是比較2個(gè)解對(duì)應(yīng)目標(biāo)值的大小關(guān)系，這更有利于迭代尋優(yōu)。綜合實(shí)例求解結(jié)果，可以得出結(jié)論，將SA算法與QPSO算法相結(jié)合，在求解多層制造單元內(nèi)設(shè)備布局問(wèn)題中表現(xiàn)良好，尋優(yōu)能力更強(qiáng)。

4 結(jié)語(yǔ)

本文基于SA-QPSO算法提出了一種多層制造單元內(nèi)部布局優(yōu)化設(shè)計(jì)方法。該方法根據(jù)多層制造單元的多個(gè)目標(biāo)函數(shù)構(gòu)建嵌套優(yōu)化模型，進(jìn)行求解，并應(yīng)用于某汽車(chē)零件加工車(chē)間實(shí)際案例，得出直線形、“U”形以及環(huán)形3種最優(yōu)的空間布局方案，驗(yàn)證了當(dāng)較小規(guī)模的多層制造單元布局問(wèn)題求解時(shí)，SA算法與QPSO算法相結(jié)合具有有效性。該方法可為相關(guān)的多層制造單元智能工廠提供一定的單元內(nèi)部布局設(shè)計(jì)依據(jù)。SA-QPSO算法的求解思路擴(kuò)展了QPSO算法的應(yīng)用范圍，可應(yīng)用于類(lèi)似問(wèn)題的求解。

參考文獻(xiàn)

[1]董峰.建設(shè)智能工廠推進(jìn)智能方案落地[J].中國(guó)工業(yè)和信息化，2022（1）：44-47.

[2]王沙沙，張則強(qiáng)，劉俊琦，等.雙向環(huán)形過(guò)道布置問(wèn)題建模及混合鯨魚(yú)算法求解[J].計(jì)算機(jī)集成制造系統(tǒng)，2021（10）：27.

[3]丁祥海，查穩(wěn)，徐雙燕.“U”形生產(chǎn)單元可重構(gòu)設(shè)施布局方法研究[J].工業(yè)工程與管理，2015，20（1）：6.

[4]遲佳，梁秋艷，張曉玲，等.改進(jìn)量子粒子群自適應(yīng)優(yōu)化算法[J].中國(guó)科技信息，2023（11）：86-90.

[5]胡松琪.量子粒子群算法的研究及應(yīng)用[D].蘭州：蘭州理工大學(xué)，2019.

[6]張婧婧，施亭亭，汪強(qiáng).基于量子粒子群算法的公共空間主功能區(qū)布局優(yōu)化設(shè)計(jì)方法[J].齊齊哈爾大學(xué)學(xué)報(bào)（自然科學(xué)版），2023，39（6）：66-71.

作者簡(jiǎn)介：郭軼男（1998-），女，碩士研究生，主要研究方向?yàn)樯a(chǎn)車(chē)間布局優(yōu)化。

電子郵箱：2470528100@qq.com。

通信作者：姜雪松（1979-），男，博士，副教授，研究方向?yàn)楣I(yè)工程與管理、制造系統(tǒng)工程及信息化。

電子郵箱：xuesongjiang@nefu.edu.cn。