柔性生產(chǎn)中人員配置模型及其調(diào)度算法

高 麗，徐克林，朱 偉，童科娜

(1.同濟大學(xué)機械工程學(xué)院，201804上海;2.上海理工大學(xué)圖書館，200093上海)

針對柔性企業(yè)的人員優(yōu)化配置問題，國內(nèi)外學(xué)者已進行了大量的研究并取得了一定的研究成果［1-3］.從優(yōu)化目標(biāo)來看，最小化最大完工時間［4-5］、合理的人工配置以及最佳作業(yè)排序［6-8］被作為優(yōu)化調(diào)度的目標(biāo);但迄今為止，將這些目標(biāo)結(jié)合起來進行多目標(biāo)優(yōu)化的研究較少.

由Bhaskar等［9］提出的MIP(mixed integer programming)和Suer［10］提出的兩階段啟發(fā)式算法，以及后來Kuo等［11］應(yīng)用這兩種方法對具有不同技能的人工分配問題的研究，均是以最小化最大完工時間為優(yōu)化目標(biāo)研究人工配置問題的，也就是只考慮了“多少人工作”(人員配置)的問題，而沒有考慮“這些人何時工作”(作業(yè)排序)的問題［12］.

本文綜合考慮了這兩個優(yōu)化目標(biāo)——合理的人員配置和最佳作業(yè)排序，提出了一種兩級遞階結(jié)構(gòu)的混合優(yōu)化算法［13］.第一級，基于遺傳算法和動態(tài)規(guī)劃法求解多種人工分配方案及對應(yīng)的最優(yōu)作業(yè)工時;第二級，基于遺傳算法和模擬退火算法求解作業(yè)排序問題.與單目標(biāo)算法結(jié)果對比表明，本文提出的算法有效，具有較好的魯棒性.

1 人員配置問題及模型建立

1.1 問題描述

針對柔性生產(chǎn)企業(yè)，有n個工件(j1，j2，…，jn)按方向一致的加工路線依次通過s個工位，該作業(yè)由隊伍B完成.假設(shè)任意兩道工序間存在有限的存儲能力(即被加工工件在兩道工序間等待時間受限)，每道工序的工人工作熟練度相當(dāng)且每個工件在每道工序的加工時間已知.優(yōu)化目標(biāo)是要確定一個調(diào)度:確定最合理的人工分配方案和作業(yè)調(diào)度方案，以使作業(yè)總完工時間最短.

1.2 模型參數(shù)和決策變量

設(shè)P={i=｜i=1，2，…，n}為工件集合;S={j=｜j=1，2，…，r}為工位集合;B={k=｜k=1，2，…，K}為人員集合;L為生產(chǎn)線集合;Bk為總?cè)斯?shù);gik表示分配到i工位的人工單位累計數(shù);tsijk為工件在工序k的開工時間，tijk為工件i在工序k的加工時間;teijk為完工時間，Tik為工件加工總時長.

決策變量為:0≤Xil≤1，表示產(chǎn)品i分配到生產(chǎn)線l上.

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

式中，目標(biāo)函數(shù)(1)為最優(yōu)人工分配方案.目標(biāo)函數(shù)(2)為最佳作業(yè)排序?qū)?yīng)的最小完工時間.式(3)為將兩個優(yōu)化目標(biāo)組合的表示方式，F(xiàn)s｜g1，

mg2，…，gr｜表示人工決策集合是工件總完工時間的不減函數(shù).式(4)～(10)為約束條件，式(4)為中各工位對應(yīng)的人工總數(shù).式(5)、(6)表示各工位人工約束.(7)～(10)表示作業(yè)排序時間約束.

1.4 模型求解策略

該數(shù)學(xué)模型主要求解兩個問題:確定最合理的人工分配方案和最佳作業(yè)排序.由于人工的固定費用遠(yuǎn)大于作業(yè)運行費用，所以將柔性生產(chǎn)線的優(yōu)化調(diào)度求解過程分為兩級:第一級，確定最佳人工分配問題方案.第二級，在給定各工序合理的人員分配前提下決定各工件的加工順序(排序問題).

2 算法設(shè)計

2.1 人工分配優(yōu)化算法

首先，將作業(yè)進行歸類分組.一般將加工流程分解為兩個層次——子作業(yè)層和父作業(yè)層.采用遺傳算法求解子作業(yè)層中多種人工分配方案及對應(yīng)的最優(yōu)作業(yè)工時，然后將子作業(yè)層視為父作業(yè)層的一個階段采用動態(tài)規(guī)劃法獲取整個作業(yè)流程的最優(yōu)工時.

2.1.1 遺傳算法求解人工分配方案及最優(yōu)作業(yè)工時

將遺傳算法用于子層并聯(lián)作業(yè)的人工分配問題關(guān)鍵是采用有效的編碼和解碼方式以及適當(dāng)?shù)慕徊?、變異操?遺傳算法對種群重復(fù)地進行選擇、交叉、變異等基本遺傳操作.不斷產(chǎn)生出比父代更適應(yīng)環(huán)境的新一代種群，直到滿足要求條件為止.

1)個體編碼.本文采用直接編碼的方式，以工序為對象.將分配工人數(shù)作為碼值這種編碼方法可避免同一工人在不同作業(yè)中的操作運算產(chǎn)生死鎖現(xiàn)象.以3個工人在3項作業(yè)中的2種分配方案為例，結(jié)果見表1.

表13 個工人在3項作業(yè)中的兩種分配方案

獲得染色體編碼如表2(以兩位二進制碼構(gòu)成基因座，根據(jù)實際作業(yè)工人數(shù)調(diào)整二進制碼位)

表2 染色體編碼

2)群體規(guī)模選擇.合適的群體規(guī)模對遺傳算法的收斂具有重要意義.群體太小難以求得滿意的結(jié)果，群體太大則計算復(fù)雜.根據(jù)經(jīng)驗，群體規(guī)模一般取10～150.

3)適值函數(shù).按照并行作業(yè)工人分配理論，如部分作業(yè)先不執(zhí)行，待部分作業(yè)完工后再進行等考慮最復(fù)雜的情況，假設(shè)n項并行作業(yè)經(jīng)過m個過程完成，其中k表示第k個作業(yè)組內(nèi)同時開工的作業(yè)項目，得到適值函數(shù)為

其中，1≤m≤n;1≤i≤m;k∈［a，m］.

本文模型選取m=1，即n項作業(yè)單獨作為一項工序優(yōu)化求其最短工時.

4)選擇.選擇是用來確定重組或交叉?zhèn)€體，以及備選個體將產(chǎn)生多少個子代個體.若有m個個體，其中某個個體i，其適值為fi，則其被選擇的概率表示為

5)交叉與變異.交叉在遺傳操作中起核心作用，交叉概率較大可增強遺傳算法開辟新搜索空間的能力.本文采用循環(huán)交叉操作(選擇3個碼串為一基點進行相互調(diào)換).變異主要是為保證算法的局部隨機搜索能力和維持種群的多樣性.當(dāng)遺傳算子在接近最優(yōu)解時，變異可以加速向最優(yōu)解的收斂.本問題的變異算子采用如下方法:在隨機選中染色體(個體串碼)中首先針對一個基點(即作業(yè)人員)增加一個單位，然后采用隨機原則，任選其他一個基點減少一個單位，既符合變異保證在全局范圍內(nèi)又保證了變異的前提條件即作業(yè)人員的總數(shù)不變，但對個體串碼而言實現(xiàn)了重排序操作.

2.1.2 動態(tài)規(guī)劃法求取作業(yè)流程的最優(yōu)工時

引入動態(tài)規(guī)劃法是將前面通過遺傳算法所獲得的決策作為一個階段決策，不管前面的決策如何，要將余下的諸決策必須構(gòu)成最優(yōu)策略;因此可將多階段決策問題的求解過程看成一個連續(xù)遞推過程，由后向前逐步計算［8］.

動態(tài)規(guī)劃模型中設(shè)置了幾個必要變量:決策變量bk，以及決策集合FFs｜g1，g2，…，gr｜，本文通過遺傳算法首先對子層并聯(lián)作業(yè)交叉變異優(yōu)化，獲得不同人工分配方案及對應(yīng)的最優(yōu)工時后，將其作為一個階段與該工序內(nèi)其他的獨立作業(yè)構(gòu)成一族同類型的子問題，最終得出人工分配的最優(yōu)指標(biāo)函數(shù).

2.2 作業(yè)排序優(yōu)化算法

確定了人工分配方案下的作業(yè)排序問題是典型的job-shop調(diào)度問題，近年來，運用遺傳算法解決這類問題的例子很多，本文采用遺傳模擬退火算法(GASA)［14］.以下簡要說明該混合算法的特性和關(guān)鍵步驟.

2.2.1 算法特性分析及關(guān)鍵步驟處理

2.2.1.1 適應(yīng)度函數(shù)值

以式(2)作為目標(biāo)函數(shù)，需要先計算工序i中各工位的總加工時間Tik，然后從中找出最大值，各工序的最大值求和;在式(2)中，目標(biāo)函數(shù)是使得f(t)最小化.取目標(biāo)函數(shù)適應(yīng)度值為該個體的目標(biāo)函數(shù)值的倒數(shù):

2.2.1.2 初始溫度

令波爾茲曼常數(shù)為1，初始溫度

式中，ΔF=Fmax-Fmin，F(xiàn)max和Fmin分別為初始種群p(0)中個體的最大和最小目標(biāo)函數(shù)值;pα為劣解接受概率.

2.2.1.3 選擇、交叉、變異

(a)選擇.為了確保適應(yīng)度大的個體能被保留到下一代種群中，采用確定式采樣來選擇復(fù)制染色體.先計算每個個體在下一代種群中期望生存的數(shù)目然后取各N的整數(shù)值作為該個體在下一代種群中出現(xiàn)的數(shù)量，由此可確定出下一代種群中符號?」表示取整;最后按照各Ni(i=1，2，…，p)的小數(shù)部分對個體降序排列，順序取前個個體補充到下一代種群，由此共得到p個新染色體組成一組新種群.

(b)交叉.采用兩兩隨機分組交叉方式.各染色體產(chǎn)生交叉的概率pc設(shè)為一個固定值，比如pc=0.60，當(dāng)產(chǎn)生0～1之間的隨機數(shù)值p＜pc時，發(fā)生交叉.交叉只發(fā)生在同一工序的染色體之間，確?；蜃兓暮戏ㄐ?交叉點隨機選擇在1～n之間的任意一點，交叉點之后的全部基因進交叉.

(c)變異.為了保證種群的穩(wěn)定性，選擇變異概率pm≤0.001，采用循環(huán)方式過濾種群的每個基因，當(dāng)產(chǎn)生的隨機數(shù)值p＜pm時，將當(dāng)前基因的整數(shù)部分隨機增或減1，只要始終確保每個基因整數(shù)部分的變化在合法的范圍內(nèi)即可.

2.2.1.4 局部搜索過程

(a)初始化馬爾可夫鏈長和局部最優(yōu)解保持不變的次數(shù)q為0.令局部最優(yōu)解s*=s＊＊當(dāng)前狀態(tài)為s.

(b)從當(dāng)前狀態(tài)s產(chǎn)生一個新解s'，計算二者目標(biāo)函數(shù)值的差值Δc'=c(s')-c(s).

(c)若Δc'≤0，則接受s'作為當(dāng)前狀態(tài)，令s＊＊=s'，q=0;若c(s*)＞c(s')，則令s'=s*;若Δc'＞0，則按照事先定義的pa接受s'作為當(dāng)前狀態(tài);若s被接受，則令s'(l+1)=s'，q=q+1，否則仍令s'(l+1)=s'(l).

(d)令l=l+1，若滿足算法終止條件(q＞qmax或l＞lmax)，則執(zhí)行步驟(e);否則轉(zhuǎn)步驟(b).

(e)用s＊＊代替s.

2.2.1.5 精英策略

為了防止丟失最優(yōu)解，若c(s*)＞c(s＊＊)，則令s*=s＊＊，否則用s*替換臨時種群中的最差個體.

2.2.2 算法實現(xiàn)步驟

Step1產(chǎn)生初始種群p(0).

Step2計算p(0)中各個體的適應(yīng)度值，分別記全局最優(yōu)解和最優(yōu)目標(biāo)函數(shù)值為s*和c*，確定初始溫度t0.令進化代數(shù)g=0.

Step3若進化代數(shù)超過設(shè)定的最大值w，則輸出s*和c*，算法結(jié)束;否則繼續(xù)執(zhí)行以下步驟.

Step4進行遺傳操作(選擇、交叉、變異).

Step5分別以經(jīng)過以上步驟得到的臨時種群中的每個個體S為起點，根據(jù)Metroplis抽樣準(zhǔn)則進行局部搜索.

Step6評價經(jīng)過以上步驟后所得臨時種群p'(g)中的所有個體，更新s*和c*.

Step7保存最優(yōu)解.

Step8令g=g+1，tg=αtg-1(α為冷卻速度)，轉(zhuǎn)步驟3.

3 案例分析

3.1 求解最優(yōu)人工分配方案

運用算法對某食品加工廠的檢驗和包裝流程進行求解.現(xiàn)有5類型號產(chǎn)品，分別為A、B、C、D、E.工位額定人數(shù)和工時如表3所示.

由表3可知該工序共有6項作業(yè).其中作業(yè)1～6可歸為父層并聯(lián)作業(yè);作業(yè)3由3項作業(yè)組成，屬于子層(由虛框標(biāo)出)，子并聯(lián)作業(yè)完成后.再執(zhí)行4，5，6作業(yè).故該工序的各項作業(yè)屬于組合并聯(lián)作業(yè).現(xiàn)已知該廠安排40名員工分組進行該工序作業(yè)，要求對各班組進行合理分配，使完成該工序的作業(yè)時間最短.

表3 %%組合作業(yè)額定人數(shù)與工時

優(yōu)化步驟一:針對第5層作業(yè)采用遺傳算法進行優(yōu)化，計算其不同人工分配方案及對應(yīng)的最短工時.由表3獲得已知數(shù)據(jù)，設(shè)置種群規(guī)模為20，交叉概率0.8，進化次數(shù)100，變異概率0.1，由VISUAL BASIC軟件編制程序得到優(yōu)化結(jié)果.將班組分為2組時，人員分配最合理同時完工時間也較小.

優(yōu)化步驟二:在獲得子層作業(yè)的不同分配小組方案及對應(yīng)最短作業(yè)工時的基礎(chǔ)上，采用動態(tài)規(guī)劃計算父層的最優(yōu)工時及人工分配方案，將第3子層作業(yè)視為第3階段，得到各階段的tk=tk(gk).由適應(yīng)度函數(shù)公式計算可知:當(dāng)k=4時，4≤bg≤7以此類推，當(dāng)k=2時，得到該組合作業(yè)的最短完工時間是450 s，同時得到最短完工的作業(yè)人工分配方案:g1=2，g2=2，g3=(1，1，1)，g4=2，g5=1，g6=2.

3.2 作業(yè)排序優(yōu)化

人工分配方案確定后，假定該加工線班次生產(chǎn)計劃為:4A、5B、5C、6D、7E.各工位對不同型號產(chǎn)品的作業(yè)時間見表4.

表4 %%加工線組成及加工時間

以最小化最大完工時間為優(yōu)化目標(biāo)，采用GASA混合算法求解該生產(chǎn)線調(diào)度問題，算法采用C++編程，經(jīng)過算法靈敏性計算試驗，選擇的算法參數(shù)值為:v=50，pc=0.85，pm=0.20，pa=0.50，ps=0.60，qmax=3，lmax=8，α=0.95，gmax=20.其他計算數(shù)據(jù)見具體的應(yīng)用問題.表5列出了該廠在各工位等額分配人員采用不完全混排的方法安排每班的加工任務(wù)，共有36種排列順序，為節(jié)約篇幅，表中只列出了5種排列的計算結(jié)果，同時與本文提出的混合算法運行25次的最優(yōu)排序結(jié)果進行了比較.

表5 作業(yè)排序結(jié)果比較

從表5可以看出，應(yīng)用本文提出的混合算法進行排序求解，可以縮短加工時間3.8%～8.6%，CPU時間為902 s.若采用最小生產(chǎn)集合的方式組織生產(chǎn)，所得的結(jié)果與不采用重復(fù)生產(chǎn)最小生產(chǎn)集合的方式的結(jié)果是相同的，但是CPU計算時間僅需要325 s，優(yōu)化效率有顯著提高.

4 結(jié)束語

本文所研究的柔性生產(chǎn)中人員配置問題屬于有約束混合離散優(yōu)化問題，因此難以針對整個過程建立統(tǒng)一的優(yōu)化模型.以作業(yè)人工分配和作業(yè)排序為優(yōu)化目標(biāo)，采用混合遺傳算法分階段求解該問題，仿真實驗說明了該方法的有效性.同時也為生產(chǎn)系統(tǒng)調(diào)度中的諸多組合優(yōu)化問題提供了一個具有前景的新方法.

［1］ERTAY T，RUAN D.Data envelopment analysis based decision model for optimal operator allocation in CMS［J］.European Journal of Operational Research，2005，164(3):800-810.

［2］ISLAM R，RASAD S M.Employee performance evaluation by the AHP:A case study［J］.Asia Pacific Management Review，2006，11(3):163-176.

［3］YANG T，CHEN M C，HUNG C C.Multiple attribute decision-making methods for the dynamic operator allocation problem［J］.Mathematics and Computers in Simulation，2007，73(5):285-299.

［4］BRUCKER P，HEITMANN S，HURINK J.Flow-shop problems with intermediate buffers［J］.OR Spectrum，2003，25(4):549-574.

［5］RONCONI D P.A note on constructive heuristics for the flow-shop problem with blocking［J］.International Journal of Production Economics，2004，87(1):39-48.

［6］WANG Ling，ZHEN D Z.An effective hybrid heuristic for flow-shop scheduling［J］.International Journal of Advanced Manufacturing Technology，2003，21(1):38-44.

［7］PONNAMBALAM S G，MOHAN R M.A GASA multiobjective hybrid search algorithm for integrating lot sizing and sequencing in flow-line scheduling［J］.International Journal of Advanced Manufacturing Technology，2003，21(6):126-137.

［8］SAWIK T.Mixed integer programming for scheduling flexible flow lines with limited intermediate buffers［J］.Mathematical and Computer Modeling，2000，31(13):39-52.

［9］BHASHKAR K，SRINIVASAN G.Static and dynamic operator allocation problems in cellular manufacturing systems［J］.International Journal of Production Research，1997，35(12):3467-3481.

［10］SUER G A，BERA I S.Optimal operator assignment and cell loading when lot-splitting is allowed［J］.Computers and Industrial Engineering，1998，35(3):431-434.

［11］KUO Y，YANG T.Optimization of mixed-skill multiline operator allocation problem［J］.Computers and Industrial Engineering，2007，53(3):386-393.

［12］SEN C G，CINAR G.Evaluation and pre-allocation of operators with multiple skills:A combined fuzzy AHP and max-min approach［J］.Expert Systems with Applications，2010，37(3):2043-2053.

［13］王笑蓉，吳鐵軍.基于Petri網(wǎng)仿真的柔性生產(chǎn)調(diào)度［J］.浙江大學(xué)學(xué)報，2004，38(3):286-291.

［14］王炳剛，混流加工/裝配系統(tǒng)集成優(yōu)化研究［J］.機械工程學(xué)報，2010，46(17):114-120.