基于SA-QPSO算法的多層制造單元內部布局方法

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

關鍵詞：多層制造單元；布局優化；模擬退火算法；量子粒子群算法

中圖分類號：TU 318 文獻標志碼：A

設施布局（Facility Layout Problem，FLP）是智能工廠建設的重要環節，科學合理的設備布局有重要的意義[1]。隨著使用智能化物流的智能工廠興起，多層制造單元的布局方式越來越多，許多學者對制造單元布局問題進行深入研究，例如王沙沙等[2]針對雙向環形過道布置問題建模并使用混合鯨魚算法有效求解。丁祥海等[3]以“U”形生產單元為研究對象，建立了單元生產可重構設施布局決策集成模型，并設計了決策問題的遺傳算法。目前國內外主要研究單層制造單元，多層制造單元相關研究較少，其中，單目標優化模型或雙目標優化模型的搬運成本最低、單元利用率最高。基于此，本文考慮了眾多制造車間的實際需求，構建多目標優化數學模型，研究多層制造單元內部設備布局方法。

1 多層制造單元車間內部布局問題描述以及數學模型構建

1.1 問題描述及假設

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

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

通過構建相同的目標函數，采用約束條件選擇不同的布局形式，求解不同的設備排列組合中最優的順序布置，獲得最佳布局。

1.2 目標函數

本文以單元體積最小、物流搬運強度最低、制造損失時間最短和單元穩定性最高為目標構建多目標數學模型。

1.2.1 單元體積目標

多層制造單元占用空間為單元體積，主要受長、寬和高3個要素影響，當3個要素最小時，單元體積就最小，目標函數如公式（1）所示。

minV=LWH （1）

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

1.2.2 物料搬運目標

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

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

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

第p號產品從設備i到設備j的物料搬運批量為ceil[]，搬運目標如公式（3）所示。

（3）

式中：D為物料搬運強度；M為設備總數量；P為產品總數量；i、j為設備編號；p為加工產品種類編號；ceil為取整；Vp為第p號產品待加工總數量；Bp為第p號產品一次搬運數量。

1.2.3 損失時間目標

在生產線平衡問題中，損失時間為衡量制造單元平衡的重要指標之一，因此設損失時間目標，如公式（4）所示。

（4）

式中：T為損失時間目標；np為設備總數；qi為第i個設備加工以及運輸到第i+1個設備的時間。

1.2.4 穩定性目標

在多層制造單元設備布局中，需要考慮設備的穩定性，穩定性目標B越小就越穩定，目標函數如公式（5）所示。

（5）

式中：yi為設備i的中心高度；wi為設備i的質量。

1.3 約束條件

在設定具體約束前，須設定的基本約束如下。設備i的中心坐標（xi，yi，zi）為優化問題的決策變量；（li，wi，hi）為設備對應的長、寬、高；設備單元集均在X、Y、Z軸正方向上，不考慮X、Y、Z軸負方向，任意設備不能超過單元的邊界。

1.3.1 邊界約束

邊界約束為設備對應長度li的一半與中心點xi坐標之和≤單元Z軸方向的長度邊界約束Lg，設備所對應寬度wi的一半與中心點yi坐標之和≤單元X軸方向的寬度邊界約束Wg，設備對應高度hi與中心點zi坐標之和≤單元Y軸方向的高度約束Hg。

1.3.2 設備位置約束

設備中心必須位于平面Z1、Z2、Z3和Z4上，zi為非負區域。假設PSi∈I為設備中心Zi面的歸屬，當PSi=1時，zi=0；當PSi=2時，zi=Z2_value；當PSi=3時，xi=0；當PSi=4時，xi=Z4_value。其中，Z2_value為Z2面的z坐標，Z4_value為Z4面的x坐標。

1.3.3 單元集形狀約束

假設Type_choose∈{1，2，3}為單元集形狀，當Type_choose=1時，直線形僅選擇平面Z1、Z3；當Type_choose=2時，“U”形僅選擇平面Z1、Z2以及Z3；當Type_choose=3時，環形選擇平面Z1、Z2、Z3以及Z4。

1.3.4 高度層級約束

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

2 基于SA-QPSO算法的目標函數求解

2.1 設備布局方案的編碼與生成

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

2.1.1 初步布局方案

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

2.1.2 Z4的x值生成

僅考慮x方向的干涉，從平面Z1、Z2找出x坐標最大的設備，使其不與Z4內最長的設備發生干涉，又因為換行約束，所以Z4≥Lz，Z4的下界lb4和上界ub4如公式（6）、公式（7）所示。

（6）

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

（7）

式中：Lg為單元Z軸方向的長度邊界約束。

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

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

式中：Z4_value為隨機數且Z4_ratio∈（0，1）。

2.1.3 Z2的Z值生成

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

（9）

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

（10）

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

設隨機數Z2-ratio∈（0，1），如公式（11）所示。

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

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

2.1.4 高度層級Yk的生成

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

對各層的最高設備按層級順序編號，計算步驟如下。

步驟一：計算設備最大余量，如公式（12）所示。

（12）

式中：Marginymax為設備上側Y軸坐標的最大邊緣值即最大余量；ηk為第k層高度設備的最大高度；r為高度層；Hg為設備對應高度hi與中心點zi坐標之和≤單元Y軸方向的高度約束；G2為給定常數值。如果最大余量≤0，則判定無解Marginymax為最大余量。

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

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

（14）

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

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

（15）

至此，生成布局方案且各約束均得到了滿足，可得到可行布局方案或判定無解。該問題外層為帶有簡單約束的組合優化問題，使用帶有罰函數的SA算法進行優化，使各高度層級均有設備；內層為無約束優化問題，使用QPSO算法進行求解。

2.2 SA算法

2.2.1 解的編碼與初始化

假設共有n個設備，以2×n的整數矩陣來表示設備組的Zi面屬性和高度層級屬性，每列對應1個設備，第一行為Zi面屬性，第二行為高度層級屬性。根據矩陣進行。

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

（16）

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

（17）

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

（18）

環形上界矩陣如公式（19）所示。

（19）

2.2.2 適應度函數

對該嵌套形式的優化問題來說，SA算法的適應度為內層QPSO算法的最優適應度值。在最大化目標中，令適應度為-M；在最小化目標中，令適應度為M。其中，M為充分大的正數。

2.3 QPSO算法

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

步驟一：初始化粒子位置，并設置初始個體最優值。

步驟二：計算各粒子的適應度值。

步驟三：比較粒子適應度值的大小，更新個體最優和全局最優。

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

（20）

式中：為最新粒子位置信息；pit，j為局部吸引子；Cjt為粒子當前個體最優的均值；α為控制參數；u為隨機變量，由此得到新位置。

步驟五：按照一定的變異概率對個體最優進行高斯擾動，即加入服從高斯分布的隨機數來提升算法多樣性。

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

3 應用實例

3.1 實例描述

采用上述算法對某汽車零件單元生產車間進行布局優化，本文選擇該車間的15臺設備為研究對象，共生產12種產品，設備信息包括設備編號、設備尺寸（長、寬和高）、設備質量以及每臺設備加工1次的加工時間，具體信息見表1。

根據產品的工藝性對產品進行編號，該車間的加工產品信息包括加工批量、搬運批量以及加工產品所經過設備的工藝路徑，具體信息見表2。

3.2 結果比較和分析

通過實例求解得到3種布局形式的最優布局方案，解碼后得出了3種形狀的最優單元布局方案。

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

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

在環形單元布局中，平面Z1有5臺設備，平面Z3有2臺設備，平面Z2有6臺設備，平面Z4有2臺設備。具體布局方案如圖7所示。

SA-QPSO算法當更新解時不會受目標數值的數量級大小影響，而是比較2個解對應目標值的大小關系，這更有利于迭代尋優。綜合實例求解結果，可以得出結論，將SA算法與QPSO算法相結合，在求解多層制造單元內設備布局問題中表現良好，尋優能力更強。

4 結語

本文基于SA-QPSO算法提出了一種多層制造單元內部布局優化設計方法。該方法根據多層制造單元的多個目標函數構建嵌套優化模型，進行求解，并應用于某汽車零件加工車間實際案例，得出直線形、“U”形以及環形3種最優的空間布局方案，驗證了當較小規模的多層制造單元布局問題求解時，SA算法與QPSO算法相結合具有有效性。該方法可為相關的多層制造單元智能工廠提供一定的單元內部布局設計依據。SA-QPSO算法的求解思路擴展了QPSO算法的應用范圍，可應用于類似問題的求解。

參考文獻

[1]董峰.建設智能工廠推進智能方案落地[J].中國工業和信息化，2022（1）：44-47.

[2]王沙沙，張則強，劉俊琦，等.雙向環形過道布置問題建模及混合鯨魚算法求解[J].計算機集成制造系統，2021（10）：27.

[3]丁祥海，查穩，徐雙燕.“U”形生產單元可重構設施布局方法研究[J].工業工程與管理，2015，20（1）：6.

[4]遲佳，梁秋艷，張曉玲，等.改進量子粒子群自適應優化算法[J].中國科技信息，2023（11）：86-90.

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

[6]張婧婧，施亭亭，汪強.基于量子粒子群算法的公共空間主功能區布局優化設計方法[J].齊齊哈爾大學學報（自然科學版），2023，39（6）：66-71.

作者簡介：郭軼男（1998-），女，碩士研究生，主要研究方向為生產車間布局優化。

電子郵箱：2470528100@qq.com。

通信作者：姜雪松（1979-），男，博士，副教授，研究方向為工業工程與管理、制造系統工程及信息化。

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