侯天天，張守京，杜昊天

(西安工程大學(xué)機(jī)電工程學(xué)院，西安 710600)

0 引言

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

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

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

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

1.1 問題描述

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

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

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

(3)同一時(shí)刻，任一機(jī)器至多加工一個(gè)工序，任一工序至多由一臺(tái)機(jī)器加工；

(4)同一時(shí)刻，任一機(jī)器至多由一個(gè)工人操作，任一工人至多操作一臺(tái)機(jī)器；

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

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

1.2 考慮工人技能柔性度的學(xué)習(xí)效應(yīng)曲線

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

(1)

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

(2)

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

(3)

αsk=lglsk/lg2

(4)

1.3 多目標(biāo)DRCFJSP模型

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

(5)

(6)

(7)

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

(8)

在求解DRCFJSP時(shí)，還需滿足以下約束：

(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)表示同一時(shí)刻任一工件的任一工序只能選擇一臺(tái)機(jī)器和一個(gè)工人進(jìn)行加工；式(10)表示同一工件的工序優(yōu)先級(jí)約束；式(11)表示加工過程不可中斷；式(12)表示兩道工序在一臺(tái)機(jī)器上的加工時(shí)間不可交叉。

2 改進(jìn)NSHGA-Ⅱ求解多目標(biāo)DRCFJSP模型

2.1 求解流程

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

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

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

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

步驟4：粒子更新：①更新權(quán)重；②找出最優(yōu)個(gè)體；③粒子更新；④計(jì)算新種群P(t)個(gè)體適應(yīng)度；

步驟5：遺傳操作：①競標(biāo)賽選擇；②交叉變異操作；③計(jì)算新種群G(t)個(gè)體適應(yīng)度；

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

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

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

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

圖1 NSHGA-Ⅱ算法求解多目標(biāo)DRCFJSP流程圖

2.2 編碼與解碼

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

圖2 工序編碼示意圖

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

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

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

2.3 全局搜索

2.3.1 粒子更新

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

(13)

(14)

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

(15)

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

2.3.2 遺傳操作

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

圖3 變異操作示意圖

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

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

(16)

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

2.4 鄰域搜索

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

圖4 鄰域搜索算子示意圖

2.5 熵值法評(píng)價(jià)策略

3 實(shí)例仿真分析

以某車間調(diào)度實(shí)例數(shù)據(jù)為基準(zhǔn)進(jìn)行仿真實(shí)驗(yàn)。車間內(nèi)共有6臺(tái)機(jī)器(M1～M6)和7個(gè)負(fù)責(zé)機(jī)器上下料的工人(W1～W7)，加工有若干工序的6個(gè)工件(J1～J6)。工序與機(jī)器、工人與機(jī)器的加工關(guān)系信息分別如表1和表2所示，工人和機(jī)器的單位成本如表3所示，污染指標(biāo)中的能耗、噪音、廢屑數(shù)據(jù)參考文獻(xiàn)[13]的規(guī)律隨機(jī)生成。通過參考文獻(xiàn)[16]與正交試驗(yàn)確定算法參數(shù)設(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 工序加工時(shí)間表

續(xù)表

表2 工人與機(jī)器加工關(guān)系表(上下料時(shí)間/初始能力/學(xué)習(xí)率)

表3 機(jī)器和工人單位時(shí)間成本

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

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

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

圖9～圖11為3種算法Pareto解集的3個(gè)目標(biāo)均值迭代情況。

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

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

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

4 結(jié)束語

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