侯天天，張守京，杜昊天

(西安工程大學機電工程學院，西安 710600)

0 引言

車間調(diào)度問題是生產(chǎn)調(diào)度領域廣受學者關注的問題之一，優(yōu)化調(diào)度方案能一定程度提高生產(chǎn)效率，降低成本。在實際生產(chǎn)中，工人資源也是直接影響車間產(chǎn)能的重要因素之一[1]。由于人力成本逐年遞增，工人操作機器的技能受限或存在差異，合理工人分配資源十分必要。雙資源約束柔性車間調(diào)度問題(dual-resource constrained flexible job shop scheduling problem，DRCFJSP)就是在經(jīng)典柔性車間調(diào)度問題(FJSP)基礎上，增加了工人選擇的子問題，求解空間和難度大幅增加，是更復雜的NP-Hard問題，已有眾多學者針對該問題開展了廣泛研究。

OBIMUYIW等[2]考慮有限數(shù)量的熟練安裝工人，建立DRCFJSP的MILP模型，并采用遺傳算法進行求解；GONG等[3]提出考慮工人靈活性的柔性車間調(diào)度模型(FJSPW)，采用混合人工蜂群算法(HABCA)進行求解，并通過實驗證明該算法求解FJSPW問題的優(yōu)越性；肖倩喬等[4]考慮工人學習因素對產(chǎn)能的影響，構建基于學習曲線的人機資源配置模型，有效解決了多目標雙重資源配置；胡金昌等[5]為解決單人單工序多機的車間調(diào)度問題，根據(jù)學習效應計算實際安裝時間，構造迭代多目標遺傳算法(IMOGA)進行求解；PENG等[6]采用混合離散多目標帝國競爭算法(HDMICA)，求解受工件運輸時間和學習效果約束的多目標柔性車間調(diào)度問題模型；曹磊等[7]為解決異質(zhì)性全技能工人與機器的配置問題，構建基于車間層面的多目標模型，提出一種雙層編碼的變鄰域雜草優(yōu)化算法進行求解。

上述研究雖有考慮到工人的學習因素，但很少有學者將其量化，且沒有考慮工人技能柔性程度的影響。基于此，本文提出考慮工人技能柔性度的學習效應曲線，構建以最小化完工時間、加工成本和環(huán)境指標為優(yōu)化目標的DRCFJSP模型。為更好地求解該問題，融合MOPSO和NSGA-Ⅱ設計非支配排序混合遺傳算法(non-dominated sorting hybrid genetic algorithm，NSHGA-Ⅱ)，并通過實例仿真驗證了該算法的有效性和優(yōu)越性。

1 問題描述及數(shù)學模型

1.1 問題描述

考慮學習效應的DRCFJSP可描述為：某調(diào)度周期內(nèi)，w名操作工人(W={W1,W2,…,Ww})操作m臺加工機器(M={M1,M2,…,Mm})加工n個工件(J={J1,J2,…,Jn})；工件i有ni個待加工工序(Oi={Oi1,Oi2,…,Oini})，工序之間具有優(yōu)先級約束；不同機器和工人的技能柔性程度不同，工人的技能水平受學習能力影響。在求解該問題時需考慮工序排序、機器選擇和工人選擇3個約束，以及工人實際操作時間動態(tài)變化的情況。假設條件如下：

(1)工件、機器及工人在零時刻均空閑可用；

(2)加工過程穩(wěn)定運行，不允許中斷；

(3)同一時刻，任一機器至多加工一個工序，任一工序至多由一臺機器加工；

(4)同一時刻，任一機器至多由一個工人操作，任一工人至多操作一臺機器；

(5)工人須在一個工序加工完成后才可轉(zhuǎn)移；

(6)運輸、刀具更換等時間考慮在加工時間內(nèi)。

1.2 考慮工人技能柔性度的學習效應曲線

學習效應(learning effect)是指工人在連續(xù)的生產(chǎn)周期中，通過不斷重復地做同一個工作或類似工作，其自身知識經(jīng)驗得以積累，操作的熟練程度得到提升，從而減少操作時間或者成本的現(xiàn)象。由于人的異質(zhì)性，每個工人的培訓效果不同，技術水平存在差異，從而影響實際加工時間。因此，研究學習效應對生產(chǎn)調(diào)度的影響十分必要，本文采用基于對數(shù)模型的DeJong學習曲線模型[8]，如式(1)所示。

(1)

然而，對于一些機器操作難度大、人機協(xié)作要求高的行業(yè)，為保證工人良好的工作狀態(tài)，降低工人離崗的負面影響，人機比率可能大于1；此外，不同程度交叉培訓的工人具有技能柔性差異，這些情況下采用人機比率表示F不再適用。由于工人作業(yè)常為同種任務類型，其掌握技能數(shù)量也會影響操作熟練度，為此引入工人技能柔性度表示F。首先，為量化工人技能柔性度[10]，定義人機關系矩陣PM=(PMsk)w×m，其中PMsk∈{1,0}分別表示工人s能否操作機器k，工人技能柔性度FI如式(2)所示。

(2)

式中，F(xiàn)I∈[0,1]，F(xiàn)I越大，說明工人對機器的技能柔性越高，反之柔性越低。對于考慮工人技能部分柔性的情況，F(xiàn)I∈(0,1)。

(3)

αsk=lglsk/lg2

(4)

1.3 多目標DRCFJSP模型

目標函數(shù)為最小化完工時間(T)、加工成本(C)和環(huán)境指標(EI)(考慮能耗、廢屑和噪聲)，如式(5)～式(7)所示。

(5)

(6)

(7)

式中，在對計算環(huán)境評價的3個指標時，由于數(shù)據(jù)單位的不同，需對其去量綱處理，計算公式如式(8)所示，X′表示處理后的數(shù)據(jù)結(jié)果。

(8)

在求解DRCFJSP時，還需滿足以下約束：

(9)

(10)

(11)

[Sijks,Fijks]∩[Si′j′ks′,Fi′j′ks′]=?

(12)

式中，?i,i′∈{1,2,…,n}；?j,j′∈{1,2,…,ni}；?k∈{1,2,…,m}；?s∈{1,2,…,w}，i≠i′；j≠j′。式(9)表示同一時刻任一工件的任一工序只能選擇一臺機器和一個工人進行加工；式(10)表示同一工件的工序優(yōu)先級約束；式(11)表示加工過程不可中斷；式(12)表示兩道工序在一臺機器上的加工時間不可交叉。

2 改進NSHGA-Ⅱ求解多目標DRCFJSP模型

2.1 求解流程

多目標DRCFJSP約束復雜、求解難度大，為避免求解過程無效解的產(chǎn)生，采用工序編碼，并設計解碼策略獲得可行解；NSHGA-Ⅱ算法將NSGA-Ⅱ和MOPSO相結(jié)合，具有高效的全局搜索效率和精確率；為避免算法陷入局部最優(yōu)，在目標迭代停滯時執(zhí)行鄰域搜索。求解流程圖如圖1所示，步驟如下：

步驟1：設置算法參數(shù)，迭代次數(shù)maxGen，進化最大停滯代數(shù)N，種群規(guī)模popsize等；

步驟2：初始化種群F(t)：隨機生成工序編碼，通過解碼獲得對應機器、工人序列及可行解；

步驟3：計算種群F(t)個體適應度，進行快速非支配排序；算法迭代開始，令t=1；

步驟4：粒子更新：①更新權重；②找出最優(yōu)個體；③粒子更新；④計算新種群P(t)個體適應度；

步驟5：遺傳操作：①競標賽選擇；②交叉變異操作；③計算新種群G(t)個體適應度；

步驟6：合并子父代種群P(t)、G(t)和F(t)，刪除重復個體，若剩余個體數(shù)量小于popsize，則轉(zhuǎn)到步驟4，否則進行快速非支配排序，選擇種群規(guī)模大小的新種群；

步驟7：若種群進化停滯代數(shù)達到N，進行鄰域搜索，否則執(zhí)行步驟8；

步驟8：令t=t+1，得到新一代種群F(t)，若t

步驟9：熵值法選出最優(yōu)解，繪制Pareto解集圖，最優(yōu)調(diào)度方案甘特圖，算法迭代圖。

圖1 NSHGA-Ⅱ算法求解多目標DRCFJSP流程圖

2.2 編碼與解碼

為簡化算法流程，保證編碼的有效性，選擇基于工序的編碼方式，以分別有3、2、2道工序的3個工件為例，示意圖如圖2所示。

圖2 工序編碼示意圖

為選擇合適的機器和工人，以完工時間為導向，設計一種考慮工人學習效應的貪婪解碼策略：為各工序選擇完工時間最小的機器和工人，以確定工序的加工順序、起始加工時間等，生成可行調(diào)度方案。對于待加工工序Oij，可加工時刻為Sij(Sij=Ti(j-1))，解碼步驟如下：

步驟1：遍歷可加工工序Oij的機器集中各機器的加工任務，任一機器k的可用時刻記為Ak(即機器k上一任務完工時間)；若Sij≥Ak，則Ak=Sij，選擇完工時間(即Ak與tijk之和)最小的機器，記為集合kij；

步驟4：更新Ak=As=Tij，若j=ni，則Ti=Tij，否則Si(j+1)=Tij。

2.3 全局搜索

2.3.1 粒子更新

粒子群算法是模擬鳥類捕食行為的一種群體智能算法[12]，每個粒子表示一個潛在解，粒子根據(jù)個體最優(yōu)和全局最優(yōu)位置指導自己速度和位置的更新，如式(13)～式(14)所示。

(13)

(14)

式(13)中w是平衡算法搜索能力的重要參數(shù)，采用指數(shù)形式的時變權重如式(15)所示。

(15)

式中，wt為第t代的權重值；wmax和wmin分別為權重上下限；t為種群當前迭代次數(shù)；maxGen為最大迭代次數(shù)。

2.3.2 遺傳操作

選擇操作：采用三元錦標賽的方法，將非支配排序等級和擁擠度作為適應度的判斷值，擴大精英個體遺傳子代的概率；交叉操作：針對工序編碼，采用JBX[13]和PBX[14]兩種單一交叉算子相結(jié)合的方式，各按1/2的概率交替選擇；變異操作：針對工序編碼，采用任意三點基因互換的方式和兩段基因分別倒序的方式，示意圖如圖3所示。

圖3 變異操作示意圖

為避免固定的交叉變異概率造成算法收斂波動大，采用動態(tài)變化的交叉變異率，第t代交叉或變異率如式(16)所示。

pxt=pxmax-(pxmax-pxmin)×t/maxGen

(16)

式中，pxmax={pcmax,pumax}；pxmin={pcmin,pumin}。

2.4 鄰域搜索

由于遺傳算法和粒子群算法在局部搜索上均存在不足，為豐富種群多樣性提升解集質(zhì)量，針對任意兩點基因構造4種鄰域搜索算子：兩點互換、兩點間倒置、插入和鄰位互換，在搜索時只接受優(yōu)于原個體的新解。以圖2的工序編碼為例，隨機選擇兩個基因位2和5，其4種鄰域結(jié)構如圖4所示。

圖4 鄰域搜索算子示意圖

2.5 熵值法評價策略

3 實例仿真分析

以某車間調(diào)度實例數(shù)據(jù)為基準進行仿真實驗。車間內(nèi)共有6臺機器(M1～M6)和7個負責機器上下料的工人(W1～W7)，加工有若干工序的6個工件(J1～J6)。工序與機器、工人與機器的加工關系信息分別如表1和表2所示，工人和機器的單位成本如表3所示，污染指標中的能耗、噪音、廢屑數(shù)據(jù)參考文獻[13]的規(guī)律隨機生成。通過參考文獻[16]與正交試驗確定算法參數(shù)設置：popsize=200，maxGen=200，c1=c2=2，wmax=0.95，wmin=0.5，pcmax=0.8，pcmin=0.4，pumax=0.2，pumin=0.1。

表1 工序加工時間表

續(xù)表

表2 工人與機器加工關系表(上下料時間/初始能力/學習率)

表3 機器和工人單位時間成本

首先，采用NSHGA-Ⅱ算法求解不同人機比例下的最優(yōu)調(diào)度方案，如圖5～圖7所示，分別為工人數(shù)為5、6、7名時的最優(yōu)方案甘特圖(實線框為工序的機器加工時長，虛線框為工人作業(yè)時長)，驗證可知所提模型的有效性。

圖5 5名工人的最優(yōu)調(diào)度方案甘特圖

圖6 6名工人的最優(yōu)調(diào)度方案甘特圖

圖7 7名工人的最優(yōu)調(diào)度方案甘特圖

以6名工人為例分析算法性能，圖8為NSHGA-Ⅱ、NSGA-Ⅱ和MOPSO三種算法Pareto解集的分布情況。

圖8 Pareto解集分布圖

圖中NSHGA-Ⅱ的解集更靠近理想原點；此外，針對Pareto解集采用3種評價指標：①基數(shù)：解的數(shù)量(Q)；②收斂性：中值距離(MID)[6]；③多樣性：空間分布(spacing)。表4為3種算法的最優(yōu)解目標值、Pareto解集目標均值和評價指標的結(jié)果；通過對比可知，NSHGA-Ⅱ的最優(yōu)解和解集均值在3個目標上均占優(yōu)于其他兩種算法，而且解的數(shù)量最多，MID和Spacing的值最小，表明解集的收斂性和多樣性最佳。

表4 3種算法求得的最優(yōu)解的多目標值

圖9～圖11為3種算法Pareto解集的3個目標均值迭代情況。

圖9 Pareto解集平均完工時間迭代圖 圖10 Pareto解集平均環(huán)境指標迭代圖

圖11 Pareto解集平均加工成本迭代圖

從收斂情況看， NSHGA-Ⅱ算法的尋優(yōu)速度均明顯優(yōu)于其他兩種算法；在尋優(yōu)能力上，MOPSO算法和NSGA-Ⅱ算法容易早熟收斂，而NSHGA-Ⅱ算法能跳出局部最優(yōu)。

4 結(jié)束語

本文研究了考慮工人學習效應的多目標DRCFJSP，引入工人技能柔性度構建數(shù)學模型，并提出一種NSHGA-Ⅱ算法進行求解。為保證迭代過程中解的可行性，針對工序編碼設計基于完工時間的貪婪解碼策略；NSHGA-Ⅱ算法結(jié)合MOPSO和NSGA-Ⅱ的優(yōu)良性能，提高算法全局開發(fā)能力；構造的四種鄰域算子提高算法局部搜索能力；采用熵值法客觀選擇最優(yōu)調(diào)度方案。最后通過實例仿真，驗證了模型的有效性，將NSHGA-Ⅱ、NSGA-Ⅱ和MOPSO的結(jié)果對比可知，NSHGA-Ⅱ的解集質(zhì)量和尋優(yōu)收斂情況均明顯優(yōu)于其他兩種算法，證明了所提算法求解該類問題的可行性與優(yōu)越性。