多約束裝配線平衡問題的知識驅動系統(tǒng)控制啟發(fā)式算法

鄭巧仙，肖暉，李明

(1.湖北大學計算機與信息工程學院，湖北 武漢 430062;2.武漢科技大學理學院；湖北 武漢 430065)

0 引言

裝配線是一種生產(chǎn)系統(tǒng)，經(jīng)常用于大批量生產(chǎn)標準化產(chǎn)品.在裝配線上，未完成產(chǎn)品通過連續(xù)的工位，不同的工位執(zhí)行不同操作，最終獲得完整的產(chǎn)品.裝配線平衡問題[1](assembly line balancing problem, ALBP)可以描述為:給定一個存在優(yōu)先關系的操作集合與工位集合，將各項操作唯一分配至其中某個工位，最小化各個工位時間的差異，并且各個工位時間不能超過裝配線的生產(chǎn)節(jié)拍.ALBP在制造業(yè)和其他流水線生產(chǎn)行業(yè)有很高的實用價值，是調(diào)度優(yōu)化中的一類重要問題，也是離散約束優(yōu)化中的NP難問題[2].

研究初期，ALBP的約束條件主要為操作間的優(yōu)先關系約束，其后基于企業(yè)實際需求，其他約束如并行約束[3]、資源約束[4]以及時間和空間約束[5]等被相繼加入；隨著企業(yè)裝配環(huán)境的進一步復雜化，對裝配線的要求更高，更多更復雜的約束同時被引入，新增加的約束主要為位置約束、同步約束、消極區(qū)域約束等[6-7]，相應ALBP稱為多約束裝配線平衡問題(multiple constraints assembly line balancing problem, MCALBP).

作為離散約束優(yōu)化問題[8-9]，MCALBP具有約束條件多、可行解空間離散以及可行解少等特點，求解的難度較大，問題是否存在可行解也難以確定，所以在求解前如果能夠準確判定可行解的存在性，有重要的實用價值.目前對離散多約束優(yōu)化問題可行解的存在性方面的研究很少，鄭巧仙等對這一問題進行了分析和證明[10].而在求解算法方面，主要有爬山算法[11]、殖民競爭算法[12]和教與學算法[13-15].上述算法大都采用罰函數(shù)法處理問題中的主要等式約束，然而由于是近似算法，理論上無法保證所得的解是最優(yōu)解，從而難以保證所有的等式約束得到滿足，即難以保證所得的解為MCALBP的可行解.

本文中針對企業(yè)的實際需求，提出一種含有更多約束的MCALBP，然后基于各約束自身的特征以及相互耦合關系等知識，設計一種能主動控制所有約束得到滿足的系統(tǒng)控制啟發(fā)式算法，求解問題的近優(yōu)解.

1 多約束裝配線平衡問題模型

1.1 問題描述設MCALBP的操作集合為I={i|i=1,2,…,|I|}，工位集合為J={j|j=1,2,…,|J|}，裝配線的生產(chǎn)節(jié)拍為C.集合I中操作i的操作時間為ti.記P=(Pi2,i1)|I|×|I|為一個0-1矩陣，用以表示不同操作之間的直接優(yōu)先關系，如果操作i1是操作i2的直接前序，Pi2,i1=1；其余情況下，Pi2,i1=0，i1,i2∈I.通過直接優(yōu)先關系矩陣P可以得到優(yōu)先關系矩陣Q，記之為Q=(Qi2,i1)|I|×|I|.MCALBP所研究問題除優(yōu)先關系約束外，還要考慮下面三類約束：

1)加強邊約束：該約束要求一些存在直接優(yōu)先關系的成對操作分配至同一個工位，并且在完成其中一項操作后馬上開始另一項操作.稱滿足加強邊約束的成對操作統(tǒng)為加強邊操作.設問題有N對加強邊操作，其中第n對的第l(l=1,2)項操作記為JQl,n(n=1,2,…,N)；

2)位置約束：該約束要求一些操作必須分配至指定的工位，可以幫助企業(yè)減少運營成本.相應的工位稱為強位置工位，相應的操作稱為強位置操作.設問題有|K| 類位置約束，其中第k(k∈K，K={k|k=1,2,…,|K|})類強位置操作集合記為Qtk，強位置工位集合記為Qsk.

3)消極區(qū)域約束：該約束要求兩個集合中的操作不能分配至同一個工位，稱相應操作為互斥操作.記問題的互斥操作集合為Tam(m=1,2)，其中集合Ta1(第1類互斥操作，所分配的工位稱為第1類互斥工位)中的操作和集合Ta2(第2類互斥操作，所分配的工位稱為第2類互斥工位)中的操作間存在消極區(qū)域約束.

本文中所研究問題以最小化裝配線的生產(chǎn)節(jié)拍為目標，除此之外還要考慮到企業(yè)希望將一些操作盡可能分配至某些工位的實際生產(chǎn)需求，增加了相應的目標，稱之為弱位置目標.弱位置目標中相應工位稱為弱位置工位，相應操作稱為弱位置操作.設問題存在|K′|類弱位置目標要求，其中第k′(k′∈K′，K′={k′|k′=1,2,…,|K′|})類弱位置操作集合和工位集合分別記為Rtk′和Rsk′.于是得到問題的優(yōu)化目標為：最小化裝配線的生產(chǎn)節(jié)拍和不滿足弱位置目標要求的操作項數(shù)，稱該問題為第2類多約束裝配線平衡問題(MCALBP-2).

1.2 數(shù)學模型設xij(i∈I,j∈J)為0-1變量，若操作i分配至工位j，則xij=1；否則，xij=0.該問題的數(shù)學模型如下：

(1)

xi1j=xi2 ji1=JQ1,n;i2=JQ2,n;j∈J;n=1,2，…,N

(2)

(3)

xi3j+xi4j≤1i3∈Ta1,i4∈Ta2

(4)

(5)

(6)

(7)

其中，(1)式為去量綱化處理后所得的問題的目標，(2)式為加強邊約束，(3)式為位置約束，(4)式為消極區(qū)域約束；(5)～(7)式為裝配線平衡問題的一般約束，依次為優(yōu)先關系約束、節(jié)拍約束和操作的分配約束.

2 知識驅動的系統(tǒng)控制啟發(fā)式算法

MCALBP有多類約束，這些約束之間相互耦合、相互制約.若問題存在可行解，則可在先驗知識的基礎之上，系統(tǒng)地考慮問題的特性和各類約束的特征，提出一個面向所有約束的整體控制策略，以此為基礎，設計啟發(fā)式算法主動控制滿足各類要求，求解問題的可行解.

知識驅動的系統(tǒng)控制啟發(fā)式算法先對數(shù)據(jù)預處理，整合加強邊約束操作的信息，處理后的數(shù)據(jù)滿足加強邊約束，并創(chuàng)建一個信息矩陣用于對強、弱位置操作分配定位.再依次對各工位基于各類約束操作的分配要求根據(jù)其優(yōu)先級別生成相應的候選操作集合，并用所設計的操作選擇規(guī)則[16]選擇操作；根據(jù)當前工位的已被分配時間與所設定生產(chǎn)節(jié)拍之間的關系所設計的操作分配規(guī)則[16]，將操作分配至工位，得到各工位的操作分配方案，求得問題的可行解.最后更新信息矩陣，進行下一次的遍歷搜索.遍歷搜索過程依據(jù)定界規(guī)則[16]減小工位時間的變化區(qū)間[Lbbest,Ubbest].算法的主要流程如圖1所示.

圖1 知識驅動的系統(tǒng)控制啟發(fā)式算法流程圖

2.1 加強邊約束操作的信息整合在MCALBP中，加強邊約束要求一些存在直接優(yōu)先關系的成對操作分配至相同工位，并且在完成其中一項操作后馬上開始另一項操作.為滿足此要求，算法在數(shù)據(jù)預處理時將這些操作的原序號保留，將操作時間集中在一項操作上，同時重新定義相關的優(yōu)先關系和操作的特殊屬性.

記i1,i2,…,im之中含有多對加強邊操作(操作(i1,i2),(i2,i3),…,(im-1,im)間存在加強邊約束)，對這些操作進行信息整合：

Step1：找到這些操作中的最前序操作.根據(jù)加強邊約束的定義，操作(i1,i2),(i2,i3),…,(im-1,im)間存在直接優(yōu)先關系，則最前序操作為i1.

Step2：將所有操作的時間集中在最前序操作i1上，更新操作時間，令ti1=ti1+ti2+…+tim，ti2=ti3=…=tim=0.

Step3：更新操作間的優(yōu)先關系.找到im′(m′=1,2,…,m)的直接后繼操作集合DSim′和直接前序操作集合DPim′，令所有加強邊約束操作的直接前序和直接后繼為每項加強邊操作的直接前序和直接后繼，即令Pi,im′=1,Pim′,i′=1,?i∈DSc,?i′∈DPr，其中，DSc=DSi1∪…∪DSim，DPr=DPi1∪…∪DPim.然后更新優(yōu)先關系矩陣Q.

Step4：更新操作的各類特殊屬性.進行信息整合后，加強邊約束操作i1,i2,…,im被視為一項操作.若其中某些操作有特殊要求，對其他操作也增加相同要求，即對它們依據(jù)位置約束(消極區(qū)域約束)、弱位置要求的優(yōu)先級從高到低依次增加屬性，以此保證i1,i2,…,im被分配至相同工位.例如，當操作i1,i2,…,im中存在某類強位置操作時，其他所有操作都增加該類強位置操作；當操作i1,i2,…,im中存在某類強位置操作和弱位置操作時，其他所有操作都增加該類強位置操作.

2.2 位置操作的信息矩陣MCALBP的位置約束要求強位置操作必須分配至與之對應的某些強位置工位.為了保證此約束得到滿足，算法將強位置操作的所有前序操作時間平均分配至此強位置工位的前序工位，稱該分配原則為平均分配原則.平均分配原則，首先確定強位置操作(記為i)的可分配強位置工位的最小與最大的序號，初步定位操作i可分配的工位；再將強位置操作i的前序操作時間平均分配至其最小可分配工位的各前序工位中，保證強位置操作i盡可能分配至其最小可分配工位.

算法中的定界規(guī)則[16]設定了工位時間的上界，即裝配線的生產(chǎn)節(jié)拍.當生產(chǎn)節(jié)拍較大時，平均分配原則很容易控制操作分配滿足位置約束；但當生產(chǎn)節(jié)拍較小時，若強位置操作i的前序操作時間長度較大，平均分配原則可能無法保證在最大可分配工位到達之前將其分配完畢，于是此操作及其至少一項前序操作必須分配至最大可分配工位，在此情況下，如果這其中某項前序和操作i有互斥關系，算法就得不到可行解.

(10)

2.3 候選操作集合在MCALBP中，生成候選操作集合不僅只取決于優(yōu)先關系，還需要考慮目前工位的強、弱位置屬性和操作的強、弱位置屬性，以及操作間的互斥屬性.若工位j不是強位置工位，候選操作集合CA不能含有強位置操作；若工位j不是第k類強位置工位時，CA中不能含有第k類強位置操作，弱位置操作也有類似要求但不強制；若工位j中含有屬于Ta1中的操作時，CA中不能含有屬于Ta2中的操作；若工位j中含有屬于Ta2中的操作時，CA中不能含有屬于Ta1中的操作.候選操作集合的生成步驟如下：

Step1：基于優(yōu)先關系，生成工位j的候選操作集合CA[16].

Step2：基于工位的強位置屬性，更新CA.

Step3：基于工位上操作間的互斥屬性，更新CA.

1)若工位不存在Ta1或Ta2中操作時，保持CA不變.

2)若工位有只屬于Ta1中的操作，為防止分配Ta2中與之相互斥的操作，更新CA為CA-Ta2.

3)若工位有只屬于Ta2中的操作，為防止分配Ta1中與之相互斥的操作，更新CA為CA-Ta1.

Step4：基于工位的弱位置屬性，更新CA.

若經(jīng)過Step2和Step3，更新后CA為空集，那么表示有約束未得到滿足，算法結束.

(11)

即已分配的工位平均前序時間長度大于等于理論的可分配工位平均前序時間長度，稱操作i的已分配前序滿足平均分配原則，其中已分配操作的集合為V.同理可定義分配弱位置操作的前序需滿足的平均分配原則.

算法基于操作的屬性為當前工位選擇操作，設置各屬性操作的選擇優(yōu)先級從高至低如下：

ⅰ)以當前工位為最大可分配工位的強位置操作及其前序操作；

ⅱ)以當前工位為最大可分配工位的弱位置操作及其前序操作；

ⅲ)可被分配至當前工位的強位置操作和弱位置操作、沒有滿足平均分配原則的強位置操作的前序操作；

ⅳ)沒有滿足平均分配原則的弱位置操作的前序操作；

ⅴ)其余強、弱位置操作的前序操作；

ⅵ)其余候選操作.

若在候選操作集合中，屬于同一優(yōu)先級的候選操作有多項，算法將從以下操作選擇規(guī)則中選擇合適的規(guī)則選擇操作.

1)操作選擇規(guī)則1：根據(jù)候選操作i的操作時間及其所有未分配后繼的操作時間之和，即位階權重[16]，選擇其中權值最大的一項操作.

2)操作選擇規(guī)則2：根據(jù)候選操作i的操作時間及其對未分配強、弱位置操作的貢獻值大小Wi選擇其中權值最大的一項操作.Wi可由式(12)計算得到，其中UV為未分配操作的集合.

式(12)中，若操作i是更多未分配強和弱位置操作的前序，并且這些強、弱位置操作的最小可分配工位序號越小，則表示操作i對分配強、弱位置操作的貢獻值越大，所以應優(yōu)先選擇該操作.

3)操作選擇規(guī)則3：若當前工位確定含有某類互斥操作，為盡可能將同一類互斥操作分配至此工位，在已有選擇權值的基礎上成倍增加候選操作中該類互斥操作的選擇權值，然后再選擇權值最大的操作.

操作選擇規(guī)則僅為當前工位選擇操作，決定所選擇操作是否分配的是操作分配規(guī)則.操作選擇規(guī)則的具體步驟如下：

(13)

否則，搜索操作i1在CA中的所有前序操作(記為i3)，根據(jù)式(14)更新CA，優(yōu)先選擇這些操作.

(14)

然后基于位階權重計算各候選操作的選擇權值，并進入Step7；若CA中不存在上述前序操作，進入Step2.

(15)

(16)

然后基于位階權重計算各候選操作的選擇權值，并進入Step7；若CA中不存在上述前序操作，則進入Step3.

Step3：若候選操作集合CA中存在可分配至當前工位的強位置操作(記集合為CA1)、弱位置操作(記集合為CA2)和未滿足工位平均分配原則的強位置操作的前序操作(記集合為CA3)，更新CA為：CA1∪CA2∪CA3，其中：

集合CA中的所有操作(記為i).若i∈CA1或CA2，則根據(jù)位階權重分別計算其選擇權值；若i∈CA3，根據(jù)式(12)計算其選擇權值，并進入Step7；若集合CA中不存在上述操作，進入Step4.

Step4：若候選操作集合CA中存在未滿足工位平均分配要求的弱位置操作的前序操作，按式(20)更新CA，然后根據(jù)式(12)計算各候選操作的選擇權值，并進入Step7；若CA中不存在上述操作，進入Step5.

(20)

Step5：若候選操作集合CA中存在強、弱位置操作的前序操作，根據(jù)式(21)式更新CA，然后根據(jù)式(12)計算各候選操作的選擇權值，并進入Step7；若CA中不存在上述操作，進入Step6.

(21)

Step6：根據(jù)位階權重計算集合CA中各候選操作的選擇權值，并進入Step7.

Step7：根據(jù)操作選擇規(guī)則3更新各候選操作的選擇權值，并選擇操作，結束操作選擇.

2.5 信息更新若算法為工位j分配一項操作i后，除了更新工位時間、解、已分配操作集合等信息，還需更新以下所列舉情形相對應的信息：若操作i屬于Ta1(或Ta2)，更新工位相應的互斥屬性；若操作i屬于加強邊約束操作，搜索與操作i進行整合的其他加強邊約束操作，并將這些操作都分配至當前工位.

3 算例

表1～表3為某實際MCALBP的測試數(shù)據(jù)，其中表1為147項操作的操作時間，表2列出了操作間的192個直接優(yōu)先關系(表中有序數(shù)對(i1,i2)表示操作i1為操作i2的直接前序)，表3給出了有特殊要求的所有操作及其相應要求，共含有7類強位置操作，8類弱位置操作，兩類互斥操作和21對加強邊約束操作，并設定裝配線的工位個數(shù)為14.

表1 操作時間 s

表2 操作間的直接優(yōu)先關系

表3 特殊操作及其要求

利用所提的啟發(fā)式算法對上述多約束問題進行求解，求解的結果見表4，所得的操作分配方案見圖2.實驗(包括后續(xù)實驗)在配置為CPU：Intel(R) Core(TM) i5-3337U@1.80 GHz，內(nèi)存：4.00 G的計算機上基于Python軟件完成，算法中參數(shù)的取值為5，最大迭代次數(shù)NC=100.

表4 對實際算例的求解結果

圖2 實驗算例的操作方案分配圖縱坐標表示工位，橫坐標為工位時間；標識表示強位置操作，表示弱位置操作(含第一類互斥操作)，表示第二類互斥操作(當此操作同時為強位置操作時，標識為)，表示其他操作，標識上方的數(shù)字為分配至該工位的操作序號，各工位最后的數(shù)值為此工位的工位時間.

比較圖2的操作分配方案和表3的操作要求易知問題的所有約束，即位置約束、加強邊約束和消極區(qū)域約束都得到滿足，而8類弱位置要求也全部滿足.算法所得的最小節(jié)拍為111，較算例的理論節(jié)拍僅大2，平衡率為97.55%，而計算時間不到5 s，都滿足實際需求.

為進一步驗證算法的有效性，將所提算法對目前已有的6個大規(guī)模標桿算例[17](相關信息見表5第1～4列)進行求解.表5中第4列為利用精確算法求解對應ALBP-2所得的最優(yōu)節(jié)拍，第5～9列依次為所提算法求得MCALBP-2的節(jié)拍、所得解中未滿足約束的個數(shù)和未滿足弱位置要求的個數(shù)、所得解對應的裝配線的平衡率以及算法的求解時間(秒).

表5 對標桿算例的求解結果

由表5的求解結果可知，對6個標桿算例，所提算法求得了所有算例的較優(yōu)可行解，而對所有160個弱位置要求僅1個(算例Mukherjee中的弱位置操作83)沒有滿足，滿足率為99.38%.所得解的平衡率均在90%以上，計算時間都不足10秒，滿足實際需求.這說明所提啟發(fā)式算法可快速、有效地求解MCALBP-2的近優(yōu)解.

4 結論

本研究針對含有多類約束，在裝配線運作過程中普遍存在的第2類多約束裝配線平衡問題，提出了一種知識驅動的系統(tǒng)控制啟發(fā)式算法，解決了多約束離散優(yōu)化問題中一直存在的難以求得可行解的難題.與已有此類問題的求解算法相比，所提算法基于各類約束的特征以及它們之間相互耦合的關系等知識，系統(tǒng)設計，整體主動控制各類約束得到滿足.由于目前多約束單邊裝配線平衡問題的研究還處于初步階段，相關數(shù)據(jù)缺少，所以只用了6個含有多約束的標桿算例.接下來將對單邊裝配線平衡問題的標桿算例進行改造，增加文章所說的多種約束，得到更多的單邊多約束問題的算例數(shù)據(jù).