柔性生產(chǎn)中基于人員任務匹配度的人員調(diào)度

趙亞玲, 葛茂根, 扈 靜, 張銘鑫, 張 璽

(合肥工業(yè)大學 機械與汽車工程學院,安徽 合肥 230009)

?

柔性生產(chǎn)中基于人員任務匹配度的人員調(diào)度

趙亞玲, 葛茂根, 扈 靜, 張銘鑫, 張 璽

(合肥工業(yè)大學 機械與汽車工程學院,安徽 合肥 230009)

文章針對單件小批量生產(chǎn)的柔性生產(chǎn)方式,考慮操作人員技能的多樣性和對于不同任務技能水平的差異性等特點,根據(jù)操作人員對各任務的累計工作時間計算任務人員之間的匹配度,在此基礎上建立柔性生產(chǎn)中資源受限下人員調(diào)度數(shù)學模型;通過啟發(fā)式算法得到模型的初始解,并運用改進的遺傳算法對模型進行求解,得到最優(yōu)的人員調(diào)度方案以實現(xiàn)任務總完成時間最小的優(yōu)化目標;最后結合具體實例驗證了該求解模型的準確性與可行性。

柔性生產(chǎn);人員調(diào)度;遺傳算法;匹配度;資源受限

隨著全球化和競爭的加劇,企業(yè)之間的競爭開始轉(zhuǎn)向基于時間的競爭和基于顧客需求的競爭,為了適應日趨激烈的市場競爭,基于訂單生產(chǎn)的單件、小批量的柔性生產(chǎn)方式成為主流,訂單生產(chǎn)使得產(chǎn)品的種類、產(chǎn)量與生產(chǎn)時間的波動性特別大,操作人員要在顧客期望交貨期內(nèi)完成多種零件和產(chǎn)品的加工,不同任務有不同的能力需求,每個操作人員有不同的操作技能,且不同技能的能力水平不同。不同的人員配置方案直接影響任務的完成質(zhì)量和完成時間。因此,對于基于訂單生產(chǎn)的柔性生產(chǎn),需要全面考慮人員的技能種類和技能水平,構建合理的人員配置方案,以實現(xiàn)在最短交貨期內(nèi)滿足客戶需求。

目前國內(nèi)外圍繞人員優(yōu)化配置問題展開了大量的研究工作并取得了不少研究成果。例如，文獻[1] 以合理的人工分配方案和最佳作業(yè)排序為目標建立了數(shù)學模型,采用遺傳算法和動態(tài)規(guī)劃法獲取最佳的人工分配方案；文獻[2]針對人員多技能情況,采用崗位適應度表示人員執(zhí)行裝配作業(yè)的能力,建立了以人員崗位適應度最大和裝配線各工位之間作業(yè)人員崗位適應度差異最小為目標的裝配線人員優(yōu)化配置模型；文獻[3]針對單元制造系統(tǒng)的操作工分配問題,在傳統(tǒng)只考慮技術技能的基礎上,增加了操作工人技能的提高,以最大化企業(yè)績效為目標建立了混合整數(shù)規(guī)劃模型。

以上研究都考慮到操作工的作業(yè)能力,部分學者還考慮到員工學習性,但未涉及不同能力水平和學習性對任務執(zhí)行時間的影響。本文在總結前人研究的基礎上,根據(jù)任務特點和操作工能力計算操作工與任務之間的匹配度[4],以最小化任務總完成時間為優(yōu)化目標,構建柔性生產(chǎn)中人員優(yōu)化配置模型[5],通過啟發(fā)式算法得到模型的初始解[6],并運用改進的遺傳算法對模型進行求解,得到最優(yōu)的人員調(diào)度方案以實現(xiàn)任務總完成時間最小的優(yōu)化目標。

1 人員與任務匹配度的計算

20世紀30年代美國康乃爾大學的萊特博士首先在航空科學期刊上提出了學習曲線。波音公司發(fā)現(xiàn)每一架飛機的工時消耗在前一架制造完成后都會有所下降,而且還是以一個可預測的比例下降。學習曲線反映了操作人員對某一項重復性工作干的時間越長,對該項工作的熟練程度就越高,即其從事該工作的工作技能水平越高?；诖?本文將第i個操作人員Pi對編號為j的操作任務Tj的匹配度的計算公式表示如下:

其中,PTij表示編號為i的操作工與編號為j的操作任務之間的匹配度;i=1,2,…,m;j=1,2,…,n;ti表示給定時間段內(nèi)人員Pi的累計工作時間;tj表示達到任務Tj的標準需求值需要的累計工作時間。

2 人員調(diào)度的數(shù)學模型

2.1 問題描述

針對柔性生產(chǎn)制造企業(yè),有n個工件由m個操作人員完成;工件Tj由qj個具有次序約束關系的不重疊工序組成,即每道工序需在其緊前工序完成后才能開始,不同工件之間的工序之間沒有約束關系;每道工序的加工需要特定的技能,每道工序可由滿足匹配度的任一員工加工;每個員工在同一時間最多處理一道工序,每個員工具有1種或多種技能,每種技能的水平不同,因而處理不同的可處理工序的效率不同;優(yōu)化目標是要確定最優(yōu)的的人員調(diào)度方案以實現(xiàn)最小化工序最大完工時間的優(yōu)化目標[7]。

2.2 模型假設

(1) 假設操作工更換工序時,不考慮調(diào)整時間。

(2) 假設每一道工序時間足夠短,操作工在執(zhí)行該工序期間匹配度不變。

(3) 假設操作工一旦開始加工某道工序,該道工序完成之前不會中斷。

(4) 假設人員和工序之間是一一對應關系,可以通過調(diào)整工序的粒度,使得每道工序只由1個人員執(zhí)行,同時人員在同一個時刻只負責1道工序的加工。

2.3 定義模型變量

人員集為P={P1…Pi…Pm},m為人員數(shù)。

工作集為T={T1…Tj…Tn},n為工件數(shù),工件Tj是由qj個具有次序約束關系的不重疊工序組成,Tj={Tj1,…,Tjk,…,Tjqj},且Tj={Tj1≤Tjk≤Tjqj}。

Qjk為工序Tjk的任務量,在生產(chǎn)中以其所需工時數(shù)具體量化,j∈T,k∈Tj。

Tsjk為工序Tjk的開始時間,j∈T,k∈Tj。

技能集合為S={1,…,g},g為所有技能種類。

Sjk為工序Tjk需要的技能,j∈T,k∈Tj。

Pjk為有技能處理工序的員工集合,j∈T,k∈Tj。

Si為員工Pi具有的技能集合,i∈P。

TBjk為工序Tjk的緊前工序集合,j∈T,k∈Tj。

PTijk為將操作工Pi分配至工序Tjk的匹配度,i∈P,j∈T,k∈Tj。

tjk為工序Tjk的預期執(zhí)行時間,j∈T,k∈Tj。

2.4 人員調(diào)度的數(shù)學模型:

模型目標函數(shù)和約束條件如下:

(1)

(2)

(3)

(4)

目標函數(shù)(1)式是最小化工序最大完工時間;約束條件(2)式規(guī)定了參數(shù)tjk的計算方法;約束條件(3)式保證每個員工同一時刻只能處理1道工序,A(t)表示[t-1,t]內(nèi)正在執(zhí)行的任務集合;約束條件(4)式保證工序間的優(yōu)先約束關系,即每道工序必須在其緊前工序完成后才能開始。

3 優(yōu)化算法

柔性生產(chǎn)過程人員調(diào)度問題是一個復雜的離散型優(yōu)化問題,和Job-shop調(diào)度問題一樣是NP問題,本文采用改進的遺傳算法對其進行求解,采用啟發(fā)式算法產(chǎn)生遺傳算法的初始種群。

3.1 初始種群

首先根據(jù)工序間的時序約束,隨機選擇開始時間最早的工序Tjk,確定該工序需求的技能集合Sjk,然后根據(jù)已經(jīng)計算出的人員-工序匹配度確定有技能處理該工序的員工集合Pjk,優(yōu)先選擇與該工序匹配度大的操作人員;以此類推,建立人員-工序配置矩陣。

3.2 編碼設計

采用實數(shù)編碼法,對于一個有N道工序數(shù)的人員調(diào)度問題,其染色體由N個基因組成,每個基因由一個兩位數(shù)表示,包含了工件—工序—時間—操作工的約束[8]。第1位數(shù)代表要加工的工件序號,同一工件的所有工序采用同一工件序號表示,根據(jù)它們在染色體排序中的順序決定它們在不同機器上的加工順序,每個工件序號出現(xiàn)的次數(shù)為該工件的工序數(shù),第α次出現(xiàn)代表該工件的第α道工序;第2位代表加工該工序的操作工編號。以3個工件3個操作工,每個工件3道工序為例,其某一染色體為[12 23 13 31 12 23 32 21 33],其中第1個基因“12”表示第1個工件的第1道工序由第2個操作工加工,第3個基因“13”表示第1個工件的第2道工序由第3個操作工加工。

3.3 交叉算子設計

交叉策略采取二次交叉算子方式,交叉后既要得到操作工與工序之間的對應關系,還要得到工序的排序信息。染色體編碼是基于工序排序的,因此需精心設計遺傳算子以保證經(jīng)過交叉后產(chǎn)生的子代是可行解。交叉算子設計如下:任取父染色體Pa中2個交叉點與母染色體Pb進行交叉操作,設為p1和p2(p1

以3個工件(每個工件3道工序),3個操作工為例,第1次交叉如圖1所示:A(A1,A2,A3)表示這3個工件,工件A第α次出現(xiàn)表示工件A的第α道工序,基因的第2位數(shù)字M表示A工件的第α道工序由第M個操作工加工。在Pb中找到復制段中的第1位數(shù)字是A且第α次出現(xiàn)的數(shù)字的基因,將該數(shù)的第2位數(shù)字換為與A對應的M直到復制段的最后一個數(shù)。

圖1 第1次交叉示意圖

第2次交叉如圖2所示:先分解染色體,得到工序的排序信息,然后根據(jù)Pa交叉段的數(shù)字的排序信息在Pc中找到對應的工序,將這些工序按照交叉段的工序排列順序插入Pc中相應位置,形成最終交叉后的染色體Pd。因此,第2次交叉后變?yōu)镻d [22 11 13 31 12 23 33 33 21],并獲得了交叉段的工序排序。

圖2 第2次交叉示意圖

3.4 變異算子設計

以一定概率隨機交換染色體中基因的位置,重新排序,這個概率即為遺傳算法的變異率。經(jīng)過變異的粒子如果為可行解,則保留此交換,否則重新進行變異操作。

3.5 適應度函數(shù)與終止條件設計

本文的優(yōu)化目標是使任務總完成時間最小,所以根據(jù)人員配置模型的優(yōu)化目標函數(shù)確定優(yōu)化算法的適應度函數(shù)為:

其中,x為一個可行解(即被選方案);fmin為遺傳算法中每一代的f(x)的最小適應度值。

該算法如果達到給定的最大進化代數(shù)或者連續(xù)若干代群體的最優(yōu)解的目標函數(shù)值變化不大時,便停止迭代。

4 實例驗證

以某企業(yè)某一訂單的人員配置為例,該訂單包括3個工件,每個工件有3道工序,由3名操作工來完成,人員和任務之間的匹配度見表5所列,其中,工序后面括號里的數(shù)字為其所對應的任務量,單位是h。

表1 人員和任務之間的匹配度

采用上述遺傳算法,借助Matlab7.0編寫程序,設置如下優(yōu)化參數(shù)[9]:初始種群為20,迭代次數(shù)為100,交叉率取0.8,變異率取0.15,計算結果如圖3所示。

圖3 人員調(diào)度甘特圖

5 結束語

柔性生產(chǎn)過程中,由于人員技能的多樣性和工序之間的次序約束關系,不同的人員調(diào)度方案直接影響任務的總完成時間。為了實現(xiàn)任務總完成時間最小的優(yōu)化目標,本文根據(jù)操作人員對各任務的累計工作時間計算人員任務之間的匹配度,在此基礎上建立柔性生產(chǎn)中人員調(diào)度數(shù)學模型;通過啟發(fā)式算法得到模型的初始解,并運用改進的遺傳算法對模型進行求解;最后通過具體實例驗證了該求解模型的準確性與可行性。

[1] 高 麗,徐克林,朱 偉,等. 柔性生產(chǎn)中人員配置模型及其調(diào)度算法[J]. 哈爾濱工業(yè)大學學報, 2012, 44(5):144-148.

[2] 曹 樂,王 彪,劉 飛,等. 裝配線多技能作業(yè)人員優(yōu)化配置模型[J]. 重慶大學學報, 2010, 33(12):21-26.

[3] 孟志雷,葉春明,寧 凝. 單元制造系統(tǒng)的操作工分配方法[J]. 工業(yè)工程, 2009,12(1):84-87.

[4] 李英姿,張曉冬,張 碩,等.基于人員-任務-資源匹配度的產(chǎn)品設計項目靜態(tài)調(diào)度[J].工業(yè)工程與管理,2012, 17(3):74-80.

[5] 劉明周,高 納,葛茂根,等. 基于勝任指數(shù)的制造車間操作工優(yōu)化配置模型[J]. 合肥工業(yè)大學學報:自然科學版, 2011, 34(10):1466-1469.

[6] 沈維蕾,黃 莉.基于組合賦權的裝配線作業(yè)人員優(yōu)化配置[J].合肥工業(yè)大學學報:自然科學版,2013,36(9):1034-1037.

[7] Kuo Y, Yang T. Optimization of mixed-skill multi-line operator allocation problem[J]. Computers & Industrial Engineering, 2007,53(3):386-393.

[8] 劉明周,張明偉,蔣增強,等.基于混合粒子群算法的多目標柔性Job-Shop調(diào)度方法[J].農(nóng)業(yè)機械學報,2008, 39(5):122-127.

[9] 閆紀紅,王子墨. 基于學習遺忘作用的人員調(diào)度實驗設計及其軟件開發(fā)[J]. 實驗室研究與探索, 2011, 30(6):55-60.

(責任編輯 張淑艷)

Personnel scheduling of flexible job-shop problem based on person-task matching degree

ZHAO Ya-ling, GE Mao-gen, HU Jing, ZHANG Ming-xin, ZHANG Xi

(School of Machinery and Automobile Engineering, Hefei University of Technology, Hefei 230009, China)

For single piece and small batch production of flexible job-shop problem, considering the diversity of operator skills and different skill levels for different tasks, the person-task matching degree is calculated according to accumulated working time of each operator on each task,and the mathematical model of personnel scheduling under resource constraint is constructed for flexible job-shop problem. The initial solution of the model is obtained by the heuristic algorithm, and the optimal personnel scheduling plan is obtained with the minimum duration by using the revised genetic algorithm to solve the model. Finally, the feasibility and accuracy of the model are verified by real cases.

flexible job-shop; personnel scheduling; genetic algorithm; matching degree; resource constraint

2014-01-22；

2014-03-28

合肥工業(yè)大學產(chǎn)學研校企合作資助項目(10-067)

趙亞玲(1989-),女,安徽合肥人, 合肥工業(yè)大學碩士生; 葛茂根(1979-),男,安徽安慶人,博士,合肥工業(yè)大學副教授.

10.3969/j.issn.1003-5060.2015.02.027

F273.1

A

1003-5060(2015)02-0270-04