柔性生產中人員配置模型及其調度算法

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

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

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

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

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

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

1.1 問題描述

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

1.2 模型參數和決策變量

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

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

1.3 數學模型

式中，目標函數(1)為最優人工分配方案.目標函數(2)為最佳作業排序對應的最小完工時間.式(3)為將兩個優化目標組合的表示方式，Fs｜g1，

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

1.4 模型求解策略

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

2 算法設計

2.1 人工分配優化算法

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

2.1.1 遺傳算法求解人工分配方案及最優作業工時

將遺傳算法用于子層并聯作業的人工分配問題關鍵是采用有效的編碼和解碼方式以及適當的交叉、變異操作.遺傳算法對種群重復地進行選擇、交叉、變異等基本遺傳操作.不斷產生出比父代更適應環境的新一代種群，直到滿足要求條件為止.

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

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

獲得染色體編碼如表2(以兩位二進制碼構成基因座，根據實際作業工人數調整二進制碼位)

表2 染色體編碼

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

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

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

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

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

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

2.1.2 動態規劃法求取作業流程的最優工時

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

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

2.2 作業排序優化算法

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

2.2.1 算法特性分析及關鍵步驟處理

2.2.1.1 適應度函數值

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

2.2.1.2 初始溫度

令波爾茲曼常數為1，初始溫度

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

2.2.1.3 選擇、交叉、變異

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

(b)交叉.采用兩兩隨機分組交叉方式.各染色體產生交叉的概率pc設為一個固定值，比如pc=0.60，當產生0～1之間的隨機數值p＜pc時，發生交叉.交叉只發生在同一工序的染色體之間，確保基因變化的合法性.交叉點隨機選擇在1～n之間的任意一點，交叉點之后的全部基因進交叉.

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

2.2.1.4 局部搜索過程

(a)初始化馬爾可夫鏈長和局部最優解保持不變的次數q為0.令局部最優解s*=s＊＊當前狀態為s.

(b)從當前狀態s產生一個新解s'，計算二者目標函數值的差值Δc'=c(s')-c(s).

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

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

(e)用s＊＊代替s.

2.2.1.5 精英策略

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

2.2.2 算法實現步驟

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

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

Step3若進化代數超過設定的最大值w，則輸出s*和c*，算法結束;否則繼續執行以下步驟.

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

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

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

Step7保存最優解.

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

3 案例分析

3.1 求解最優人工分配方案

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

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

表3 %%組合作業額定人數與工時

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

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

3.2 作業排序優化

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

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

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

表5 作業排序結果比較

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

4 結束語

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

［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網仿真的柔性生產調度［J］.浙江大學學報，2004，38(3):286-291.

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