張 哲,王麗麗,殷 勇

(1.南京理工大學(xué) 經(jīng)濟(jì)與管理學(xué)院,江蘇 南京 210094;2.同志社大學(xué)商學(xué)院,日本 京都 602-8580)

賽汝(Seru)生產(chǎn)系統(tǒng)是一種靈活且反應(yīng)靈敏的柔性制造系統(tǒng)[1]。它結(jié)合了Jobshop生產(chǎn)模式的高柔性、大規(guī)模生產(chǎn)模式的高效率以及高度可持續(xù)發(fā)展的環(huán)境友好性[2]。與傳統(tǒng)裝配線相比,在應(yīng)對(duì)不確定的需求及動(dòng)蕩的市場(chǎng)變化方面更具競(jìng)爭(zhēng)力[3]。Seru生產(chǎn)主要用于電子工業(yè),大量用于組裝生產(chǎn)[4]。因此,Seru屬于小型的裝配組織,通常只包括3個(gè)工序:裝配、測(cè)試和包裝[5]。一個(gè)Seru生產(chǎn)系統(tǒng)由一個(gè)或者多個(gè)Seru組成。每個(gè)Seru是一個(gè)小型緊湊的組裝單元,由一些小型、簡(jiǎn)單和便宜的設(shè)備以及一個(gè)或多個(gè)致力于生產(chǎn)一種或多種產(chǎn)品的工人組成[3]。Seru生產(chǎn)單元具有完結(jié)性(Kanketsu)、工程間締合性(Majime)和自律性(Jiritsu)的特點(diǎn)[6]。Seru有3種基本的類型:流程分割式Seru、巡回式Seru和單人貨攤式Seru(屋臺(tái)式Seru或Yatai)[7-10]。流程分割式Seru是傳統(tǒng)流水線向Seru生產(chǎn)轉(zhuǎn)變的第一種形式,整個(gè)生產(chǎn)過程是由幾個(gè)經(jīng)過交叉培訓(xùn)的工人合作完成的[4,10]。巡回式Seru是流程分割式Seru向單人貨攤式過度的中間狀態(tài),這種形式的Seru生產(chǎn)單元工作臺(tái)固定,每位工人都掌握著所有生產(chǎn)工序的操作,并且多能工一個(gè)緊跟一個(gè)繞著工作臺(tái)循環(huán)作業(yè),所以整個(gè)Seru的效率主要是由最慢的工作工人決定[4,8,10]。單人貨攤式Seru是Seru進(jìn)化的方向或者說高級(jí)形式,在一個(gè)Seru生產(chǎn)單元中只需要一個(gè)全能工,工人要掌握全部生產(chǎn)工序,以生產(chǎn)出所需產(chǎn)品[10]。實(shí)際上,這3種類型的Seru之間沒有嚴(yán)格的優(yōu)劣之分[1,11]。因此,對(duì)于企業(yè)而言,有必要根據(jù)其實(shí)際生產(chǎn)條件選擇合適的Seru類型。本文研究的問題基于巡回式Seru,未來將考慮分割式Seru和單人貨攤式Seru。

訂單調(diào)度是制定訂單生產(chǎn)計(jì)劃的決策過程。它包括兩個(gè)方面:一是將訂單分配給可行的Seru,二是確定分配到各個(gè)Seru中的訂單的生產(chǎn)順序。其中,批量分割和換裝時(shí)間是影響Seru調(diào)度的兩個(gè)主要因素[4]。一方面,批量分割后的并行生產(chǎn)可以減少最大完工時(shí)間(Makespan)并增加整個(gè)系統(tǒng)的靈活性。另一方面,太小的批量則會(huì)導(dǎo)致頻繁的換裝,這可能會(huì)導(dǎo)致Makespan的增加。此外,在Seru生產(chǎn)方式下,經(jīng)過交叉培訓(xùn)的多能工是實(shí)施Seru生產(chǎn)的基礎(chǔ)和前提條件[12]。由于工人的技能組合及技能熟練水平的差異,工人和操作任務(wù)之間存在著多重匹配關(guān)系,不同的工人執(zhí)行同一操作所需時(shí)間也有所不同[13]。因此,如何設(shè)計(jì)合理的多能工配置方案以充分發(fā)揮多能工的生產(chǎn)效率對(duì)優(yōu)化整個(gè)Seru生產(chǎn)系統(tǒng)性能有著重要的影響作用。也就是說,工人分配的結(jié)果將會(huì)對(duì)訂單的調(diào)度決策產(chǎn)生重要的影響。因此,該問題的研究對(duì)于解決Seru實(shí)際生產(chǎn)中的問題具有重大參考意義。目前,同時(shí)將這些問題進(jìn)行研究的文章較少,且大多以最大化工人間的工作量平衡及最小化工人培訓(xùn)成本為目標(biāo)[13,14],忽略了訂單調(diào)度計(jì)劃目標(biāo)。Luo等[4]創(chuàng)新性地研究了帶有工人分配的巡回式Seru調(diào)度問題,構(gòu)建了一個(gè)雙層規(guī)劃模型,并設(shè)計(jì)了一種雙層嵌套模擬退火遺傳算法(SA-GA)進(jìn)行求解。然而,該方法運(yùn)算復(fù)雜而且運(yùn)行時(shí)間較長?；诖?本文將多能工配置與Seru訂單調(diào)度協(xié)同決策,設(shè)計(jì)了一種基于雙層編碼的改進(jìn)型多目標(biāo)混合遺傳算法。

1 問題描述

假設(shè)現(xiàn)有一個(gè)巡回式Seru生產(chǎn)系統(tǒng),在該生產(chǎn)系統(tǒng)存在W位擁有不同操作熟練度的多技能工人,且這些工人將會(huì)被分配給J個(gè)Seru生產(chǎn)單元用于I個(gè)訂單的生產(chǎn),這些訂單包括P種產(chǎn)品類型。此外,各個(gè)工人對(duì)于各種類型產(chǎn)品的操作熟練度、每個(gè)訂單的交貨日期、需求量及產(chǎn)品類型、每種產(chǎn)品類型所需的換裝時(shí)間及標(biāo)準(zhǔn)生產(chǎn)時(shí)間等參數(shù)是已知的。通常在接收到一系列的訂單后,首先將由一線經(jīng)理制定出工人-Seru分配計(jì)劃?；谠摴と朔峙溆?jì)劃,生產(chǎn)計(jì)劃部門將會(huì)做出訂單調(diào)度決策。實(shí)際上,工人分配結(jié)果與訂單調(diào)度計(jì)劃是相互作用、相互影響的。因此,制造商需要做出包括訂單調(diào)度和工人分配聯(lián)合決策。

在本文中,工人分配的目標(biāo)是平衡每個(gè)Seru中工人的能力,即最大程度地減少工作人員的總閑置時(shí)間。在巡回式Seru中,工人負(fù)責(zé)單個(gè)產(chǎn)品的整個(gè)加工過程,但設(shè)備彼此共享。多能工一個(gè)緊跟一個(gè)從一個(gè)工作臺(tái)移動(dòng)到另一個(gè)工作臺(tái)循環(huán)作業(yè),以滿足訂單需求。因此,每個(gè)Seru的效率主要由該Seru中生產(chǎn)速度最慢的工人決定,并且該Seru中的其他工人將會(huì)停下來等待最慢的工人。因此,等待時(shí)間就是他們的空閑時(shí)間。Seru調(diào)度的目標(biāo)是在計(jì)劃期內(nèi)保證所有的訂單都能在交貨期之前完工的基礎(chǔ)上最大地減少整個(gè)生產(chǎn)系統(tǒng)的完工時(shí)間。且考慮批量分割以使生產(chǎn)計(jì)劃更加地平衡和靈活。

2 模型建立

2.1 模型假設(shè)

(1)Seru的數(shù)目是給定的常數(shù)。

(2)每個(gè)訂單只包含有一種產(chǎn)品類型;

(3)考慮批量分割,即一個(gè)訂單可拆分成多個(gè)子訂單并分配給不同的Seru;

(4)分配給某個(gè)Seru的訂單或子訂單所包含的全部的生產(chǎn)操作必須全部在該Seru內(nèi)完成;

(5)Seru生產(chǎn)系統(tǒng)中的工人數(shù)量是恒定的,并且多技能工人的技能水平不會(huì)受到情感,身體和環(huán)境因素以及學(xué)習(xí)和遺忘的影響;

(6)考慮到布局緊湊,忽略了多技能工人在執(zhí)行不同操作時(shí)在工作臺(tái)之間移動(dòng)的距離和時(shí)間;

(7)假設(shè)每個(gè)Seru中的第一個(gè)加工的訂單的換裝時(shí)間為零,且不考慮兩個(gè)訂單產(chǎn)品類型相同且連續(xù)生產(chǎn)的第二個(gè)訂單的換裝時(shí)間。

2.2 符號(hào)說明

(1)編號(hào)。i:訂單編號(hào),i=1,2,…,I;j:Seru編號(hào),j=1,2,…,J;w:工人編號(hào),w=1,2,…,W;p:產(chǎn)品類型編號(hào),p=1,2,…,P;k:訂單在Seru中的加工順序,k=1,2,…,K。

Twp:工人w生產(chǎn)單件產(chǎn)品p所需時(shí)間。

(3)變量。

Qij:訂單i分配給Seruj的量;tij:Seruj生產(chǎn)單件訂單i所需產(chǎn)品的時(shí)間,其中,tij=max{w=1,2,…,W}{TwpZipfwjewp};STij:生產(chǎn)Qij所需的換裝時(shí)間;

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

minmakespan=

max{i∈{1,2,…,I}}{max{j=1,2,…,J}(CTij)}

(1)

minidle_time=

(2)

(3)

(4)

(5)

(6)

(7)

max{j=1,2,…,J}(CTij)≤Di

(8)

fwj,gij,Hijk∈{0,1}

Qij≥0,?i,j

(9)

式(1)和式(2)是目標(biāo)函數(shù),分別表示Makespan和總的工人空閑時(shí)間;式(3)確保工人只能被分配給一個(gè)Seru;式(4)限制了一個(gè)Seru內(nèi)的人數(shù);式(5)確保訂單只能分配到可行的Seru;式(6)表示訂單需求量等于其子訂單分配量的和;式(7)和式(8)保證了所有的訂單均在交貨期及Seru計(jì)劃期前完成;式(9)表示變量Qij的非負(fù)邏輯約束。

3 改進(jìn)型多目標(biāo)混合遺傳算法

第二代非支配排序遺傳算法(Non-dominated sorting genetic algorithm II,NSGA-II)是有效求解多目標(biāo)函數(shù)的算法之一,它降低了非劣排序遺傳算法的復(fù)雜性,具有運(yùn)行速度快和解集收斂性好的優(yōu)點(diǎn)[15]。然而在處理高維問題時(shí),NSGA-II容易陷入局部極值,出現(xiàn)早熟收斂現(xiàn)象[16]。模擬退火(Simulated annealing,SA)算法是一種基于蒙特卡羅迭代求解策略的自適應(yīng)啟發(fā)式概率搜索算法,具有簡(jiǎn)單性和強(qiáng)大的搜索功能的優(yōu)點(diǎn),但是缺乏對(duì)整體搜索方向的掌握。為了吸收這兩種算法的優(yōu)點(diǎn),本文設(shè)計(jì)了一種有效的混合多目標(biāo)優(yōu)化策略—改進(jìn)型多目標(biāo)混合遺傳算法來解決所提出的問題。

3.1 染色體編碼

染色體的第一層包含W位基因,基因的值對(duì)應(yīng)于Seru編號(hào)用來表示工人-Seru分配方案。染色體的第二層則表示訂單調(diào)度結(jié)果。在進(jìn)行訂單調(diào)度前,將接收到的訂單根據(jù)交貨期從小到大排列并進(jìn)行自然數(shù)編碼,并通過實(shí)數(shù)編碼以分配比率來表示訂單調(diào)度方案。詳細(xì)示例如圖1所示。

圖1 編碼示例

3.2 解的檢驗(yàn)與修正

染色體需保證個(gè)體能滿足約束(3)～(9)。但是,在初始種群及由遺傳操作產(chǎn)生的新個(gè)體中仍存在有很多不滿足約束條件的非可行解。對(duì)于不滿足約束(4)的個(gè)體,通過調(diào)整基因值來進(jìn)行解的修正。對(duì)于不滿足約束(6)的個(gè)體通過調(diào)節(jié)子訂單的量來進(jìn)行解的修正。修正方案如圖2所示。對(duì)于不滿足約束(5)、(7)及(8)的個(gè)體,則通過構(gòu)造懲罰函數(shù)來抑制該類解的產(chǎn)生。

圖2 可行性修正方案

3.3 遺傳操作與模擬退火

首先通過非支配排序?qū)ΨN群中的個(gè)體進(jìn)行分層,快速非支配排序的基本步驟如下。

首先令種群中的不被其他個(gè)體所支配的個(gè)體的rank=0;將這些個(gè)體儲(chǔ)存到非支配前端F1中;然后將F1從種群中剔除,找出剩下的個(gè)體中不被其他任何個(gè)體所支配的解集,令其rank值為1,并將這些個(gè)體儲(chǔ)存到非支配前端F2中,然后從現(xiàn)有種群中剔除F2,重復(fù)上述操作直到種群中的所有的個(gè)體都被分配到對(duì)應(yīng)的非劣前端。

非支配排序完成后則需計(jì)算各層個(gè)體的擁擠距離。擁擠度是判斷同一個(gè)rank層中個(gè)體的優(yōu)劣的標(biāo)準(zhǔn),擁擠度排序的目的是保持個(gè)體的多樣性。個(gè)體的擁擠度是通過計(jì)算與其相鄰兩個(gè)個(gè)體在每個(gè)子目標(biāo)值上距離差之和,其中邊界解被指定為無窮大距離的值。本文希望同一rank層中的個(gè)體差異越大越好,所以對(duì)于同一rank中的個(gè)體擁擠度大的將被優(yōu)先選擇。

然后根據(jù)個(gè)體的rank值及擁擠度通過錦標(biāo)賽選擇選出父代個(gè)體。由于本文采用了擴(kuò)展的雙層染色體編碼方法,因此染色體的上層需要分別進(jìn)行交叉操作和變異操作。染色體上級(jí)采用單點(diǎn)交叉和單點(diǎn)突變。染色體下層采用矩陣單列交叉及矩陣單列變異操作。

種群經(jīng)過交叉變異后,需執(zhí)行SA操作,以兩倍的Makespan與工人空閑時(shí)間之和作為適應(yīng)度值,如果通過遺傳操作生成的新種群中的個(gè)體具有較大的適應(yīng)性值,則接受概率為1,否則根據(jù)等式(10)計(jì)算該個(gè)體的接受概率。

(10)

Tg+1=aTg

(11)

式中:p(Tg+1)為當(dāng)溫度為Tg+1時(shí)新個(gè)體的接受概率;fg+1為新個(gè)體的適應(yīng)度值;fg為舊個(gè)體的適應(yīng)度值;a為降火系數(shù)。

整個(gè)算法的流程如圖3所示。

本文改進(jìn)型多目標(biāo)混合遺傳算法參數(shù)值如表1所示。

表1 改進(jìn)型多目標(biāo)混合遺傳算法參數(shù)設(shè)置

4 算例分析

引用Luo等[4]論文表2中的數(shù)據(jù)對(duì)所提出的基于雙層編碼的改進(jìn)型多目標(biāo)混合遺傳算法進(jìn)行驗(yàn)證。表2列出了該算例的非支配解集。表3和表4以解1為例給出了相應(yīng)的工人分配方案以及訂單調(diào)度計(jì)劃。Luo等[4]以Makespan為主目標(biāo),工人空閑時(shí)間為次目標(biāo),采用SA-GA算法進(jìn)行求解。由于Makespan占有主導(dǎo)地位,所以算法運(yùn)行一次僅求得一個(gè)結(jié)果,不存在非支配解。這樣并不是非常合理,企業(yè)面臨不同的環(huán)境會(huì)有不同的側(cè)重點(diǎn)。如企業(yè)較注重公平與員工滿意度,可能會(huì)更加關(guān)注工人的生產(chǎn)任務(wù)均衡,而追求效率的企業(yè)則會(huì)更加關(guān)注Makespan。根據(jù)其文章中10次運(yùn)行的結(jié)果得到了3個(gè)非支配解集如表6所示。

圖3 算法流程圖

圖4直觀地顯示了兩種算法的運(yùn)行結(jié)果,可以發(fā)現(xiàn)本文所提出的算法在單獨(dú)實(shí)現(xiàn)最小化Makespan及工人空閑時(shí)間方面更優(yōu),無明顯的優(yōu)劣之分。SA-GA算法單次平均運(yùn)行時(shí)間約為8 156 s,而本文所提出算法運(yùn)行時(shí)間約為160 s,運(yùn)行時(shí)間縮短了約98%。為了驗(yàn)證所提出算法的可擴(kuò)展性,本文引用了Luo等[4]論文中的大算例進(jìn)行求解,表5列出了該大算例的非支配解集,表7是根據(jù)Luo等[4]論文中的5次運(yùn)算得到的大算例的非支配解。通過比較發(fā)現(xiàn)本文所提出的算法在實(shí)現(xiàn)最小化Makespan方面較弱但差距極小,且在最小化工人空閑時(shí)間方面較優(yōu)。另Luo等[4]論文中的算法在驗(yàn)證大算例時(shí),其單次平均運(yùn)行時(shí)間約為16 066 s,而本文算法僅需約490 s,詳細(xì)比較如表8所示。

表2 非支配解集

表3 解1對(duì)應(yīng)的工人分配方案

表4 解1對(duì)應(yīng)的訂單調(diào)度計(jì)劃

表5 大算例非支配解集

表6 Luo等[4]文章小算例的非支配解集

表7 Luo等[4]文章大算例的非支配解集

圖4 兩種算法的非支配解集

表8 算法運(yùn)行時(shí)間比較

綜上,本文所提出的多目標(biāo)混合遺傳算法相較與之前的研究,在求解小算例時(shí),不僅能夠獲得較優(yōu)的解,且算法運(yùn)行時(shí)間大大減少(單次運(yùn)行時(shí)間減少約98%);在求解大規(guī)模算例時(shí),本文所求的解相較于之前的研究仍為非劣解,不僅如此,運(yùn)行時(shí)間也縮短了約97%。實(shí)際上本文算法所優(yōu)化的時(shí)間遠(yuǎn)不僅如此,先前的研究中所獲得的非支配解集是經(jīng)多次運(yùn)算獲得的。因此,其運(yùn)行時(shí)間還需疊加。此外,大算例的數(shù)據(jù)相較于小規(guī)模算例增加了3倍多,而本文算法大算例的運(yùn)行時(shí)間也約是小算例的3倍。因此,該算法的時(shí)間復(fù)雜度為線性時(shí)間。由此可證,文中所提出的基于雙層編碼的改進(jìn)型多目標(biāo)混合遺傳算法是可行且有效的,并具有良好的可擴(kuò)展性。

5 結(jié)論

本文研究了多能工配置與Seru訂單調(diào)度協(xié)同優(yōu)化決策,綜合考慮工人分配、換裝時(shí)間及批量分割等因素,建立了以最小化Makespan及最小化工人空閑時(shí)間為目標(biāo)函數(shù)的多目標(biāo)整數(shù)非線性規(guī)劃模型。設(shè)計(jì)了一種基于雙層編碼的改進(jìn)型多目標(biāo)混合遺傳算法對(duì)模型進(jìn)行求解。數(shù)值算例結(jié)果表明,相較于SA-GA算法,本文所設(shè)計(jì)算法在執(zhí)行大小算例所需的運(yùn)行時(shí)間均縮短了98%,且目標(biāo)函數(shù)值無優(yōu)劣之分。本文算法在解決所提出的問題方面相較于之前的研究更加有效且具有良好的可擴(kuò)展性。這對(duì)于解決Seru實(shí)際生產(chǎn)中的問題具有重大參考意義。

未來的研究還應(yīng)考慮工人學(xué)習(xí)效應(yīng)、遺忘效應(yīng)、工人培訓(xùn)、員工離職以及其他影響工人技能水平的因素。此外,訂單往往是在不同時(shí)間連續(xù)或隨機(jī)到達(dá)的,并且可能還會(huì)取消訂單,更改交貨日期等,這直接影響到企業(yè)可以選擇接受的訂單集,也影響到訂單調(diào)度決策。