基于多能工配置的巡回式賽汝訂單調(diào)度優(yōu)化決策

張 哲,王麗麗,殷 勇

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

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

1 問題描述

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

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

2 模型建立

2.1 模型假設(shè)

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

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

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

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

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

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

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

2.2 符號說明

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

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

(3)變量。

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

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和總的工人空閑時間;式(3)確保工人只能被分配給一個Seru;式(4)限制了一個Seru內(nèi)的人數(shù);式(5)確保訂單只能分配到可行的Seru;式(6)表示訂單需求量等于其子訂單分配量的和;式(7)和式(8)保證了所有的訂單均在交貨期及Seru計劃期前完成;式(9)表示變量Qij的非負(fù)邏輯約束。

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

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

3.1 染色體編碼

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

圖1 編碼示例

3.2 解的檢驗與修正

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

圖2 可行性修正方案

3.3 遺傳操作與模擬退火

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

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

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

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

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

(10)

Tg+1=aTg

(11)

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

整個算法的流程如圖3所示。

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

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

4 算例分析

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

圖3 算法流程圖

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

表2 非支配解集

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

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

表5 大算例非支配解集

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

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

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

表8 算法運行時間比較

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

5 結(jié)論

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

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