朱 毅 朱玉杰

（東北林業(yè)大學(xué)，黑龍江 哈爾濱 150000）

隨著消費(fèi)者對(duì)服裝產(chǎn)品個(gè)性化、多樣化需求的不斷增加，服裝企業(yè)必須快速響應(yīng)市場(chǎng)變化，提供個(gè)性化定制服務(wù)，以滿足消費(fèi)者的需求。與傳統(tǒng)的大批量生產(chǎn)相比，個(gè)性化定制趨向于小批量多品種（SBMV）生產(chǎn)模式，要求在服裝生產(chǎn)中充分發(fā)揮工藝柔性和設(shè)備柔性。由于采用SBMV 生產(chǎn)模式，因此懸掛式裝配線在換裝過(guò)程中面臨裝配線平衡（ALB）問(wèn)題和機(jī)器分配問(wèn)題。ALB 涉及的工藝路線優(yōu)化問(wèn)題是預(yù)生產(chǎn)排程的核心問(wèn)題，屬于柔性車間排程問(wèn)題[1]。通過(guò)優(yōu)化裝配線工藝分配和機(jī)器分配方案可以最大限度地提高整條裝配線的效率和柔性。

針對(duì)服裝裝配線的平衡優(yōu)化問(wèn)題，該文提出一種多目標(biāo)遺傳算法（MOGA），以實(shí)現(xiàn)裝配線排序效率最大化和機(jī)器調(diào)整路徑最小化的目標(biāo)[2]。通過(guò)服裝車間的生產(chǎn)實(shí)例驗(yàn)證MOGA 配制方案的有效性，MOGA 既可以實(shí)現(xiàn)流水線平衡的常規(guī)優(yōu)化目標(biāo)，又可以滿足小批量多品種生產(chǎn)模式下快速換裝對(duì)機(jī)器調(diào)整路徑最小化的優(yōu)化要求。MOGA 為企業(yè)設(shè)計(jì)實(shí)際生產(chǎn)線的人機(jī)調(diào)度方案提供參考。

1 數(shù)學(xué)模型

單件流服裝裝配線規(guī)劃問(wèn)題屬于多工藝路線柔性車間排程問(wèn)題，可以描述為每個(gè)工件有多條工藝路線。每個(gè)工件包括n道工序，這些工序必須依次經(jīng)過(guò)m個(gè)工位才能完成服裝縫制任務(wù)。

考慮工位數(shù)量和機(jī)器數(shù)量的限制，單件服裝車間裝配線問(wèn)題的約束條件如公式（1）～公式（6）所示。

式中：n為工件總數(shù)；m為加工站總數(shù)；p為總目標(biāo)；yj為工作站是否使用（j為0 表示未使用，j為1 表示已使用）；mji為機(jī)器類型i是否可用于工作站加工（j為0 表示不可用，j為1 表示可用）；xijk為在工作站第k次操作的處理時(shí)間。

公式（1）表示每個(gè)工作站最多包括2 種機(jī)器，公式（2）表示1 個(gè)工作站同時(shí)只能加工1 個(gè)工件，公式（3）表示一項(xiàng)操作最多只能部分加工1 次，公式（4）表示1 個(gè)工序只能在1 個(gè)工作站的1 臺(tái)機(jī)器上加工，公式（5）表示每個(gè)作業(yè)的所有操作都必須完成，公式（6）表示處理時(shí)間總是非負(fù)的。

在生產(chǎn)過(guò)程中，流水線指標(biāo)可以評(píng)價(jià)流水線的平衡狀態(tài)，判斷計(jì)劃能否保證準(zhǔn)時(shí)交貨。以多目標(biāo)算法求解FCALBP為目標(biāo)，采用裝配線平衡率最大化和換裝過(guò)程中機(jī)器調(diào)整路徑最小化的優(yōu)化目標(biāo)建立數(shù)學(xué)模型，如公式（7）～公式（9）所示。

式中：E為裝配線的整體效率；Eej為每個(gè)工位的生產(chǎn)效率；m為加工站總數(shù)；Tj為j站的工作時(shí)間；Tbs為計(jì)劃中總處理時(shí)間最長(zhǎng)的站的處理時(shí)間。

第二個(gè)優(yōu)化目標(biāo)是找到最小的機(jī)器調(diào)整路徑。在小批量多品種服裝生產(chǎn)模式下，為了實(shí)現(xiàn)快速換裝生產(chǎn)，流水線需要能夠快速、有效地切換生產(chǎn)工藝。采用目標(biāo)函數(shù)計(jì)算裝配線上所有機(jī)器的調(diào)整距離總和R，如公式（10）所示。

式中：Sk為裝配線上機(jī)器的調(diào)整路徑；S'k為同一機(jī)器在新裝配線機(jī)器布局方案中的位置；Sk'為在新的流水線機(jī)器布局方案中需要補(bǔ)充或移除的機(jī)器移動(dòng)路徑長(zhǎng)度。

2 多目標(biāo)遺傳算法

2.1 編碼和種群初始化

2.1.1 編碼方法

當(dāng)采用遺傳算法研究傳統(tǒng)生產(chǎn)線平衡問(wèn)題時(shí)，通常使用二進(jìn)制編碼進(jìn)行編碼和解碼。在FCALBP（局部二值模式）中，使用二進(jìn)制編碼可能會(huì)破壞服裝工序之間的優(yōu)先級(jí)關(guān)系，從而導(dǎo)致解的不可行。而面向?qū)ο蟮木幋a方法可以將該問(wèn)題的可行方案表示為染色體，并使子染色體繼承父染色體的特征。因此，MOGA 采用路徑表示法對(duì)布料工序進(jìn)行編碼，生成工序染色體。工藝染色體的長(zhǎng)度等于1 件服裝的工藝總數(shù)，每個(gè)工序基因攜帶相關(guān)的工序信息，例如后續(xù)工序、標(biāo)準(zhǔn)工時(shí)和機(jī)器型號(hào)等。MOGA 包括2 個(gè)染色體群，即工序染色體和計(jì)劃染色體。2 個(gè)種群中的染色體數(shù)量始終相同，并且它們之間建立了一對(duì)一的映射關(guān)系。工序染色體種群考慮工序之間的約束關(guān)系，并采用遺傳算法進(jìn)行操作，例如選擇、交叉和變異等[3]。時(shí)間表染色體種群由過(guò)程染色體種群通過(guò)過(guò)程分配機(jī)制產(chǎn)生，可以計(jì)算MOGA 的適應(yīng)度值并將其反饋到過(guò)程染色體選擇階段。

工序分配機(jī)制根據(jù)工序染色體考慮工位數(shù)量和每個(gè)工位單個(gè)工件的可分配作業(yè)時(shí)間進(jìn)行相應(yīng)的工序分配。如果瓶頸工時(shí)始終存在于同一個(gè)工位，就會(huì)導(dǎo)致掛線擁塞。在分配過(guò)程中，一些工序被批量分割，以便在2 個(gè)不同工位進(jìn)行周期性加工，從而優(yōu)化裝配線的瓶頸工位。在應(yīng)用工序分配機(jī)制后，將生成與工序染色體唯一對(duì)應(yīng)的計(jì)劃染色體，該染色體包括每個(gè)工位的工序和分割工序信息，可以進(jìn)一步解碼，以獲得包括工序和機(jī)器分配信息的調(diào)度計(jì)劃。

2.1.2 種群初始化

服裝流程圖的結(jié)構(gòu)與有向無(wú)環(huán)圖相同，所有服裝工序的調(diào)度與有向無(wú)環(huán)圖的遍歷具有共同特征：所有頂點(diǎn)都會(huì)出現(xiàn)且只出現(xiàn)1 次（加工的唯一性）。如果存在從頂點(diǎn)一到頂點(diǎn)二的路徑，那么在排序中，頂點(diǎn)一必須在頂點(diǎn)二的前面（工序約束）。1 個(gè)頂點(diǎn)可以指向多個(gè)頂點(diǎn)，也可以被多個(gè)頂點(diǎn)指向（處理的靈活性）。

MOGA 利用隨機(jī)拓?fù)渑判蜻M(jìn)行群體初始化。拓?fù)渑判虼_保在不違反服裝工藝約束的情況下對(duì)服裝工藝進(jìn)行排序并生成工藝染色體。該文在拓?fù)渑判蜻^(guò)程中引入隨機(jī)算子，保證初始種群在整個(gè)可行解空間內(nèi)生成，從而提高M(jìn)OGA 的全局搜索能力。具體步驟如下：1） 定義約束關(guān)系。根據(jù)工藝流程和工藝信息定義順序約束。2） 生成流程依賴圖。根據(jù)所有流程的順序約束進(jìn)行排列，構(gòu)建有向無(wú)環(huán)圖（DAG）。圖中的每個(gè)節(jié)點(diǎn)代表1 個(gè)流程，邊代表流程之間的依賴關(guān)系。3） 拓?fù)渑判?。采用隨機(jī)拓?fù)渑判蛩惴▽?duì)流程依賴圖中的節(jié)點(diǎn)進(jìn)行排序。選擇1 個(gè)入度indegree（指有向圖中某點(diǎn)作為圖中邊的終點(diǎn)的次數(shù)之和）為0 的節(jié)點(diǎn)作為起點(diǎn)，開(kāi)始遍歷相鄰節(jié)點(diǎn)。當(dāng)訪問(wèn)1 個(gè)節(jié)點(diǎn)時(shí)，如果其indegree為0，就根據(jù)隨機(jī)算子決定是否在結(jié)果列表中添加1 個(gè)元素。如果是，就刪除其指向的所有邊；否則，繼續(xù)遍歷其他節(jié)點(diǎn)。重復(fù)步驟三，直到訪問(wèn)完所有節(jié)點(diǎn)。4） 生成過(guò)程染色體群。節(jié)點(diǎn)列表即為過(guò)程染色體，根據(jù)種群大小初始化種群[4]。

表1 工藝信息

MOGA 中編程染色體的生成步驟如下：1） 工序定位。除第一個(gè)工序外，當(dāng)其他工序被視為待分配工序時(shí)，先確定所有工序分配的工位。工序被定位在最后一個(gè)工作站并進(jìn)行進(jìn)站判斷。2） 進(jìn)站判斷。在工序分配機(jī)制中，進(jìn)站判斷包括機(jī)器類型判斷和工站工作時(shí)間判斷。當(dāng)站內(nèi)機(jī)型數(shù)為0 或1時(shí)，直接測(cè)量工作時(shí)間[5]。如果工作時(shí)間滿足要求，那么工序可以進(jìn)入工位，同時(shí)更新工位機(jī)器類型和工作時(shí)間。如果工作時(shí)間不符合要求，那么進(jìn)入步驟三。當(dāng)站內(nèi)機(jī)器數(shù)量為2 臺(tái)時(shí)，判斷待處理工序?qū)?yīng)的機(jī)器與當(dāng)前站內(nèi)機(jī)器是否一致，以便進(jìn)行工作時(shí)間判斷。如果不一致，就進(jìn)入下一站執(zhí)行步驟二。3） 批量工序分配。當(dāng)工作時(shí)間不滿足要求時(shí)，根據(jù)公式（1）中描述的約束條件進(jìn)行分批。根據(jù)剩余工作時(shí)間與當(dāng)前工序時(shí)間的比例確定分割比例，取值接近1/n或（n-1）/n，如公式（11）所示。4） 重復(fù)步驟一～步驟三，直到過(guò)程染色體上的所有過(guò)程基因都進(jìn)入過(guò)程基因組。

式中：Tj為工位的實(shí)際生產(chǎn)速度；T'j為已進(jìn)站工序的總工作時(shí)間；Ti為可分割工序的加工時(shí)間（分批加工將整批工件中的第i道工序在2 個(gè)工位之間按一定比例周期性地分配加工）；Rp為單個(gè)工件工序不能分到2 個(gè)工位加工[6]。

2.2 選擇操作

在整個(gè)MOGA 迭代過(guò)程中，將規(guī)劃染色體的聯(lián)合適配值作為染色體的評(píng)估標(biāo)準(zhǔn)。裝配線的有效適配值和機(jī)器調(diào)整路徑的適配值被賦予不同的權(quán)重。對(duì)機(jī)器調(diào)整路徑最小化的結(jié)果進(jìn)行歸一化處理，以生成機(jī)器調(diào)整路徑的適配值。

最佳人員配置計(jì)劃包括在保持裝配線原有機(jī)器布局的情況下實(shí)現(xiàn)高效生產(chǎn)的目標(biāo)[7]。然而，在實(shí)際應(yīng)用中，為了提高裝配線的更換效率，可能需要調(diào)整某些機(jī)器。機(jī)器調(diào)整路徑采用最大/最小歸一化方法進(jìn)行處理，將路徑特征的范圍控制在0～1。

在多目標(biāo)遺傳算法的迭代過(guò)程中，采用精英保留策略保留性能優(yōu)越的個(gè)體，以加速算法收斂并提高解的質(zhì)量。具體來(lái)說(shuō)，在每代種群中，將適配度前40%的染色體作為當(dāng)前種群的精英群體，為下一代產(chǎn)生后代。

此外，從解集中選擇染色體也是提高搜索性能的重要方法，根據(jù)裝配線效率和機(jī)器調(diào)整路徑等其他標(biāo)準(zhǔn)，從解集中選擇2 個(gè)子集，每個(gè)子集占種群總數(shù)的10%，并與前一個(gè)精英組組合成新一代后代。這樣的操作可以綜合考慮多個(gè)標(biāo)準(zhǔn)，有助于找到更好的解決方案。

2.3 改進(jìn)交叉和變異操作

2.3.1 交叉操作

交叉操作在遺傳算法中起關(guān)鍵作用。服裝工藝之間的約束關(guān)系非常復(fù)雜，直接進(jìn)行交叉操作會(huì)破壞子染色體工藝基因之間的約束關(guān)系。該文采用約束調(diào)整方法對(duì)交叉操作進(jìn)行改進(jìn)，保證子染色體的有效性。前端點(diǎn)g1和后端點(diǎn)g2交叉基因段的前端點(diǎn)和后端點(diǎn)是隨機(jī)產(chǎn)生的。端點(diǎn)前的子串和端點(diǎn)后的子串g1和端點(diǎn)后的子串g2保留2 個(gè)親本過(guò)程染色體（P1，P2）。g1和g2之間的交叉基因段被交換，基因段中的相同基因保留原來(lái)的交換順序。在驗(yàn)證約束關(guān)系后，根據(jù)后續(xù)程序的基因位置將差異基因插入適當(dāng)?shù)奈恢谩?/p>

滿足約束關(guān)系的父染色體（P1，P2）如圖1 所示。在兩點(diǎn)交叉操作中，斷點(diǎn)g1和g2先被選中。交換中間子串中的相同過(guò)程3、4、6 和7 并保留各自父本中的基因順序進(jìn)行交叉。P1子串中的差分基因?yàn)?，其子代的插入點(diǎn)在過(guò)程基因7～基因9。子串中的差異基因?yàn)镻2子串中的差異基因?yàn)?，其子代的插入點(diǎn)在過(guò)程基因1～基因3。目前有2 個(gè)可選點(diǎn)，隨機(jī)選擇可選點(diǎn)進(jìn)行插入操作，交集最終產(chǎn)生子代S1和S2。

圖1 流程有向無(wú)環(huán)圖

2.3.2 變異操作

在遺傳算法中，通過(guò)變異操作對(duì)染色體基因進(jìn)行擾動(dòng)，以保證跳出局部最優(yōu)解的能力。該文通過(guò)改進(jìn)兩點(diǎn)交換法來(lái)實(shí)現(xiàn)變異操作。在父染色體上隨機(jī)選取2 個(gè)點(diǎn)，將這2 個(gè)位置上的基因與子代進(jìn)行交換。變異操作還利用約束調(diào)整方法對(duì)不可行解中變異基因的位置進(jìn)行調(diào)整，以保證子染色體的有效性。根據(jù)圖2 的過(guò)程路線生成父染色體，并進(jìn)行兩點(diǎn)交換變異操作，如圖3 所示。

圖2 兩點(diǎn)交叉示意圖

圖3 兩點(diǎn)交換示意圖

3 試驗(yàn)和計(jì)算結(jié)果

該文以成都某服裝公司的工裝襯衫生產(chǎn)訂單為例。該襯衫包括64 道基本工序，根據(jù)衣片的部位可劃分為5 個(gè)服裝模塊。工序約束條件如圖4 所示。每道工序的相關(guān)工序涉及平車、刀車、電腦平車以及四線疊加車等機(jī)型。人工操作不需要額外的車站空間，因此不包括在車站機(jī)器類型數(shù)量的計(jì)算中。工序相關(guān)信息見(jiàn)表1（工藝編號(hào)與圖4 的工藝路線圖對(duì)應(yīng)）。

圖4 襯衫工藝路線圖

該案例中的工裝襯衫流水線方案以服裝車間的人工方案為基礎(chǔ)。根據(jù)交貨要求，日產(chǎn)量為200 件襯衫。工人每天的操作時(shí)間為9 h，示例節(jié)拍為2.70 min，單件襯衫縫制標(biāo)準(zhǔn)工時(shí)為41.49 min，理論上最少工位數(shù)為16 個(gè)。在懸掛式流水線編排方案生成程序中，設(shè)定種群規(guī)模為50，那么拓?fù)渑判蜻x擇概率為0.5，交叉概率為0.6，變異概率為0.05，工位生產(chǎn)節(jié)拍為2.7，最大迭代次數(shù)為200 次。

根據(jù)不同的流水線工藝分配方法，各工位的加工時(shí)間和機(jī)型數(shù)量見(jiàn)表2。在人工分配方案中，瓶頸工位的加工時(shí)間為3.66 min。流水線裝配效率為70.93%，包括3 種類型機(jī)器的工位比例為43.75%。與人工分配方案相比，MOGA 算法和GA 算法對(duì)工位處理時(shí)間的控制更嚴(yán)格，并且會(huì)限制機(jī)器的使用數(shù)量。傳統(tǒng)GA 對(duì)裝配線配置的效率為85.05%，瓶頸工位加工時(shí)間為2.71 min，與人工分配方案相比，裝配線效率大約提高了15%，服裝生產(chǎn)線的工位數(shù)量通常為16 個(gè)、18個(gè)、20 個(gè)和22 個(gè)。由于工位機(jī)型數(shù)量的限制，因此MOGA和GA 的工位數(shù)量有所增加，最終方案的18 個(gè)工位仍為正常規(guī)模。

表2 工藝站編譯方案

MOGA 的聯(lián)合適配值迭代曲線如圖5 所示。在生產(chǎn)過(guò)程中，瓶頸工序時(shí)間始終存在于同一工位，會(huì)造成掛線擁堵。為了改善瓶頸工位，在編程中進(jìn)行工序入庫(kù)操作，將部分工序分批入庫(kù)。相應(yīng)的工序定期分配到2 個(gè)固定工位進(jìn)行縫制操作，瓶頸工位不會(huì)固定在同一位置。在整個(gè)縫制階段，流水線的效率將在一定范圍內(nèi)波動(dòng)。與傳統(tǒng)遺傳算法相比，MOGA 進(jìn)一步提高了流水線效率（與傳統(tǒng)遺傳算法相比，流水線效率從85.05%升至88.33%），MOGA 在方案編譯的染色體生成階段集成了工序批量拆分機(jī)制，進(jìn)一步提高了裝配線效率，MOGA 和GA 的裝配線效率迭代曲線如圖6 所示。

圖5 聯(lián)合適配性曲線

圖6 效率曲線

機(jī)器調(diào)整路徑的迭代曲線如圖7 所示。觀察迭代過(guò)程中的變化曲線可以發(fā)現(xiàn)，盡管存在一定的不穩(wěn)定性，但是機(jī)器調(diào)整路徑可以收斂。傳統(tǒng)遺傳算法的流水線效率收斂于最優(yōu)值，但是相應(yīng)的機(jī)器調(diào)整路徑波動(dòng)幅度大。在MOGA 中，機(jī)器調(diào)整路徑被賦予權(quán)重并進(jìn)行優(yōu)化。MOGA 將機(jī)器調(diào)整路徑最小化作為優(yōu)化目標(biāo)之一。雖然在迭代過(guò)程中因流水線效率的優(yōu)化會(huì)產(chǎn)生一定的波動(dòng)，但是可以實(shí)現(xiàn)總體收斂。在該案例中，MOGA 的最終機(jī)器調(diào)整路徑長(zhǎng)度為123 m。

圖7 機(jī)器調(diào)整路徑曲線

4 結(jié)語(yǔ)

該文針對(duì)服裝柔性車間小批量多品種生產(chǎn)模式下的排產(chǎn)問(wèn)題提出了一種解決方案。該方案基于實(shí)際生產(chǎn)的約束條件建立了流水線效率最大化和機(jī)器調(diào)整路徑最小化的數(shù)學(xué)模型。此外，該文通過(guò)改進(jìn)傳統(tǒng)遺傳算法的種群初始化、交叉和變異過(guò)程，開(kāi)發(fā)了多目標(biāo)遺傳算法（MOGA）?；贛OGA 的排產(chǎn)方法利用實(shí)際企業(yè)訂單進(jìn)行經(jīng)驗(yàn)驗(yàn)證。結(jié)果表明，MOGA 能夠優(yōu)化服裝懸掛線的加工順序，同時(shí)滿足服裝生產(chǎn)中靈活性和設(shè)備約束的要求。值得注意的是，與多種服裝場(chǎng)景下的人工排布方法相比，MOGA 具有更高的流水線編排效率（超過(guò)10%）。MOGA 將機(jī)器調(diào)整路徑作為優(yōu)化目標(biāo)之一，以確保迭代過(guò)程中的最小值收斂。因此，最終的生產(chǎn)方案能夠加快新訂單的流水線機(jī)器調(diào)整速度，減少停機(jī)時(shí)間，從而滿足小批量多品種生產(chǎn)模式的需求。相關(guān)結(jié)果證明了基于MOGA 的方法通過(guò)設(shè)計(jì)多目標(biāo)和多優(yōu)先級(jí)組合優(yōu)化算法來(lái)幫助企業(yè)實(shí)現(xiàn)精益生產(chǎn)目標(biāo)方面的潛力。

在MOGA 求解過(guò)程中，各種參數(shù)（包括適配值權(quán)重、交叉和變異概率）都會(huì)對(duì)最終解決方案產(chǎn)生影響。為了進(jìn)一步優(yōu)化基于人工智能的柔性制造預(yù)排程智能決策系統(tǒng)，將重點(diǎn)關(guān)注生產(chǎn)過(guò)程中的自主學(xué)習(xí)、適應(yīng)和參數(shù)調(diào)整。該文主要設(shè)計(jì)MOGA 來(lái)執(zhí)行服裝裝配線的預(yù)調(diào)度任務(wù)。然而，實(shí)際生產(chǎn)過(guò)程會(huì)受實(shí)時(shí)限制，例如工人缺勤或機(jī)器故障，這就需要對(duì)工作流分配進(jìn)行即時(shí)調(diào)整。因此，在未來(lái)的研究中，需要研究服裝作業(yè)車間的實(shí)時(shí)調(diào)度，以充分處理突發(fā)事件。