鄭巧仙，肖暉，李明

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

0 引言

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

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

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

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

1 多約束裝配線平衡問(wèn)題模型

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

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

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

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

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

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

(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)式為去量綱化處理后所得的問(wèn)題的目標(biāo)，(2)式為加強(qiáng)邊約束，(3)式為位置約束，(4)式為消極區(qū)域約束；(5)～(7)式為裝配線平衡問(wèn)題的一般約束，依次為優(yōu)先關(guān)系約束、節(jié)拍約束和操作的分配約束.

2 知識(shí)驅(qū)動(dòng)的系統(tǒng)控制啟發(fā)式算法

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

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

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

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

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

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

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

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

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

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

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

(10)

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

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

Step2：基于工位的強(qiáng)位置屬性，更新CA.

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

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

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

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

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

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

(11)

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

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

ⅰ)以當(dāng)前工位為最大可分配工位的強(qiáng)位置操作及其前序操作；

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

ⅲ)可被分配至當(dāng)前工位的強(qiáng)位置操作和弱位置操作、沒(méi)有滿足平均分配原則的強(qiáng)位置操作的前序操作；

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

ⅴ)其余強(qiáng)、弱位置操作的前序操作；

ⅵ)其余候選操作.

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

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

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

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

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

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

(13)

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

(14)

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

(15)

(16)

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

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

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

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

(20)

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

(21)

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

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

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

3 算例

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

表1 操作時(shí)間 s

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

表3 特殊操作及其要求

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

表4 對(duì)實(shí)際算例的求解結(jié)果

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

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

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

表5 對(duì)標(biāo)桿算例的求解結(jié)果

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

4 結(jié)論

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