[發明專利]柔性車間的多工藝路線與布局聯合優化方法

在審

• 申請號: 202010835115.8
• 申請日: 2020-08-19
• 公開（公告）號: CN112084704A
• 公開（公告）日: 2020-12-15
• 發明（設計）人: 湯洪濤;梁佳炯;陳青豐;王丹南;任森麗;魯建廈;詹燕
• 申請（專利權）人: 浙江工業大學
• 主分類號: G06F30/27
• 分類號: G06F30/27;G06F30/25;G06Q10/04;G06Q10/06;G06Q10/08;G06Q50/04;G06N3/00
• 代理公司: 杭州天正專利事務所有限公司 33201
• 代理人: 王兵

1.一種針對柔性車間的多工藝路線與布局聯合優化的方法，包含如下步驟：

S1：構建多工藝路線與車間布局聯合優化模型；具體包括：

記m為車間的產品種類，n為車間工藝路線中所涉及的設備數量(包含加工設備和倉庫)，記t為車間的加工設備數量(由于包含關系，所以tn)，p為總的工藝步驟數量，不同產品具有相同的工藝步驟的不重復統計；

步驟1)在引入各產品訂單數量的基礎上，將多工藝路線的規劃與車間布局同時作為決策變量考慮；同時，將倉庫看作設備考慮使得總體的生產物流計算更加準確，故生產物流成本函數為：

式中，Z₁表示生產物流成本；c表示物流成本系數；z_i表示第i類產品的訂單量；n階0-1矩陣P_n×n,i為車間第i類產品的工藝路線，矩陣P_n×n,i中每一元素的的行代表上一工序的設備編號，列代表下一工序的設備編號；

當出現一種產品多次出入同一臺設備時，可通過矩陣中包含配送段信息推出完整的該產品的工藝路線；當出現一種產品連續出入同一臺設備時，由于連續進入同一臺設備進行加工并不產生物流成本，所以可只用一臺設備來表達；當相同的配送段多次出現在一條工藝路線中時，通過改變矩陣中的元素來表達該配送段出現的次數；

矩陣D_n×n表示車間的設備間距；在實際車間中，設備區域面積不只包含了加工設備的占地面積，還有人員操作空間，維修空間等，故物流成本計算時不考慮加工設備區域的物流出入口設置問題，將設備區域中心作為物流起始與終點即可；倉庫在實際車間中有明確的物流出入口，因此在模型計算中將倉庫的物流出入口坐標代替為設備的坐標；同時，在實際車間中物流配送沿通道實行，因此設備間距采用曼哈頓距離公式計算；假定設備1的坐標為(x₁,y₁)，設備2的坐標為(x₂,y₂)，則兩設備間的物流距離為：

d₁₂＝|x₁-x₂|+|y₁-y₂| (2)

步驟2)考慮各設備在生產周期內的換模頻率和設備與模具庫的距離構建換模物流成本函數:

Z₂＝c(f_t×1×d_1×t) (3)

式中，Z₂表示換模物流成本；c表示物流成本系數；t維行向量f_t×1表示各設備換模頻率；t維列向量d_1×t表示模具庫與各設備的間距，設車間模具庫s出入口坐標為(x_s,y_s)，那么t維模具庫與各設備間距列向量d_1×t＝(d_1s,d_2s......d_ts)^T；其中設備與模具庫距離公式為：

d_is＝|x_i-x_s|+|y_i-y_s|，i＝1,2...t (4)

步驟3)綜合考慮車間的生產物流成本和換模成本，以車間總物流成本最低作為多工藝路線與車間布局聯合優化模型的目標函數：

MinZ＝Z₁+Z₂ (5)

式中，Z表示總體物流成本；

步驟4)構建工藝約束，具體為：

k_i,j＜k_i,r(i＝1,2...m；j,r＝1,2...p且j≠r) (6)

記k_i,j為工藝j在第i類產品工藝路線中的序號，i＝1,2,3,...,m,j＝1,2,3,...,p；公式(6)表示在第i類產品的工藝路線中，工藝j的序號小于工藝r的序號，即在第i類產品的生產過程中，工藝j必須先于工藝r進行；

步驟5)構建工藝設備選擇約束，具體為：

p_i,j∈Ω_j(i＝1,2...m；j＝1,2...p) (7)

記p_i,j為工藝j在第i類產品工藝路線中選擇的設備，Ω_j表示工藝j可選設備的集合，i＝1,2,3,...,m,j＝1,2,3,...,p；因此公式(7)表示在第i類產品的工藝路線中，工藝j選擇的設備必須屬于它的可選設備的集合Ω_j；

步驟6)構建設備區域間距約束，具體為：

式中，x_i表示第i個設備區域的橫坐標；y_i表示第i個設備區域的縱坐標；l_i表示第i個設備區域面積的長；w_i表示第i個設備區域面積的寬；因此公式(8)表示車間布局中各設備區域之間橫坐標之差和縱坐標之差的絕對值必須大于設備i與設備j的區域面積長度之和的二分之一和面積寬度之和的二分之一，即各設備區域不能有重合情況；

步驟7)構建設備區域邊界約束，具體為：

式中，L表示車間長度；W表示車間寬度；因此公式(9)表示設備i區域的橫坐標必須大于設備i區域面積長度的二分之一且小于車間長度與設備i區域面積長度的二分之一之差，同時設備i區域的縱坐標必須大于設備i區域面積寬度的二分之一且小于車間寬度與設備i區域面積寬度的二分之一之差，即各設備區域不能超出車間邊界；

步驟8)構建特殊固定約束，具體為：

x_i＝E,y_i＝E'(i∈B；E,E'∈R) (10)

式中，E,E’為已知實數,R表示實數集合；B表示需要固定位置的設備編號集合；R表示實數集合；因此公式(10)表示設備i由于特殊需要必須布置在坐標為(E,E’)的地方，如倉庫和一些需要通風的設備等；

S2：設計多決策變量智能優化算法對模型進行優化求解，得到最優布局方案和工藝路線，具體包括：

步驟1多決策變量智能優化算法中各維度算法思路的選擇；全局搜索和局部尋優是智能優化算法的兩大特點而不同的算法特點決定了解的搜索方向；如果在解的兩個維度都采用全局搜索，雖然保證了解的多樣性但是犧牲了尋優效率；如果兩個維度都采用局部尋優，那么會喪失大量解的可能性以及陷入局部最優；而如果兩個維度采用不同特點的算法思路則能理論上解決上述難題題，在初始種群的個體足夠分散的前提下能較好地兼顧全局搜索與局部尋優之間的協同問題；

多決策變量優化算法中各維度算法的選擇主要遵循以下準則：

各維度算法的主要特點體現在解的產生(搜索)規則方面；智能優化算法的設計著眼點主要在于解的產生方式和選擇規則，但在上述多決策變量優化算法的求解思路中每次優化迭代中任何維度的任何解都需要保留，若某次迭代的解缺失的話不僅會導致整體解空間減小也可能導致優化迭代無法進行，因此主要通過對解的選擇規則進行設計的算法并不適合運用在多決策變量優化算法中；

步驟2初始化種群；各變量根據所選的算法思路進行針對性的編碼，并進行所需參數的初始化設定；同時為了解決實際優化過程中種群個體搜索到的可行解過少的問題，提出了種群休整概率b；每次迭代時種群個體都有一次是否休整的判定；若判定為休整，則種群個體在這一次迭代中只進行可行解搜索，反之則同時進行尋優迭代；

其中b₀為初始種群個體的休整概率，b₁為休整概率的最小值，h₀為最大迭代數，h為當前代數，初始化種群時h＝0；初始化種群時個體分散度高，迭代中丟失可行解的可能性更大，因此休整概率的初始值最大，隨著迭代的進行種群個體越來越密集，個體的搜索范圍重疊度增加，因此可行解的丟失概率不斷下降，所以休整概率相應下降；

步驟3進行種群分散度的判定與優化；以二維解空間為例：點的集合即是解種群，點的分散程度即是解種群的分散度，當經過不斷的迭代之后，解種群將越來越密集于一點(解種群覆蓋范圍內最優解)即分散度越來越小，因此當初始解種群的分散度越大時，迭代后的最優解才越有可能最佳；以二維解空間為例，記解c由cx與cy組成，其中cx＝(x1,x2,...,xm)，cy＝(y1,y2,...,yn)，則解C在解空間中的坐標為(X,Y)，其中

X＝Ax₁+Bx₂+...+αx_m-(A*L₁+B*L₂+...+α*L_m) (12)

Y＝ay₁+by₂+...+βy_n-(a*l₁+b*l₂+...+β*l_n) (13)

L_i≤x_i≤U_i,i＝1,2,3,...,m (14)

l_j≤y_j≤u_j,j＝1,2,3,...,m (15)

其中A,B,...,α,a,b,...,β為常數系數，U_i,L_i,u_j,l_j分別為x_i,y_j的上下界；

設某次優化的初始解種群為C＝(c1,c2,...,cm),當其中任意兩個解之間的距離都不小于實數ε時即認為該初始種群是足夠分散的，記ci，cj在解空間中的坐標分別為(Xi,Yi),(Xj,Yj)，其中ci,cj∈C，i,jm，則

其中χ為種群大小，當種群中某兩個個體之間的距離過小時，通過隨機調整其中某一個體某一維度的解來使它們符合分散度要求；

步驟4進行工藝約束與布局約束的判定修正，即符合特定工藝順序需求和設備選擇要求，同時設備間距大于零且各設備不超出車間邊界；

步驟5進行初始化種群的適應度計算以及個體與全局最優種群(p和g)的初始化賦值；適應度函數為:

fitness＝minZ (18)

步驟6對是否執行種群休整進行判斷，若結果為是則在接下來的迭代更新步驟中跳過步驟8，若為否則按步驟進行操作；

步驟7進行工藝路線種群的可行解搜索，完成對工藝路線種群的迭代；

步驟8進行車間布局種群以及設備布置方向的可行解搜索；

步驟9再次對工藝路線種群與車間布局種群進行工藝約束與布局約束的判定修正，完全符合約束之后才能進入下一步驟；

步驟10進行種群的適應度計算以及個體與全局最優種群的更新；

步驟11進行最大迭代次數的判定，結果為否則重復步驟6～10，結果為是則結束該優化過程。