董 海, 徐曉鵬

(1沈陽(yáng)大學(xué) 應(yīng)用技術(shù)學(xué)院,遼寧 沈陽(yáng) 110044; 2.大連理工大學(xué) 機(jī)械工程學(xué)院,遼寧 沈陽(yáng) 110044)

0 引言

隨著柔性化生產(chǎn)的廣泛應(yīng)用，柔性車(chē)間調(diào)度問(wèn)題獲得大量研究，除傳統(tǒng)啟發(fā)式算法外，一些學(xué)者提出采用多種新型算法求解柔性車(chē)間調(diào)度問(wèn)題[1～8]。

文獻(xiàn)[9～12]對(duì)車(chē)間生產(chǎn)中的工序順序柔性開(kāi)展了全面的研究，總結(jié)和提出了描述方法。文獻(xiàn)[13～16]在實(shí)際車(chē)間調(diào)度問(wèn)題中除考慮機(jī)器因素外，還要考慮工人的因素，因此引入了人力資源約束。

本文考慮車(chē)間中掌握多種技能的工人和并行工序順序柔性，建立模型，并提出可快速得到處于非支配解集的多種調(diào)度方案的求解算法。

1 多柔性作業(yè)車(chē)間調(diào)度問(wèn)題模型

1.1 問(wèn)題描述

在實(shí)際柔性車(chē)間生產(chǎn)中，同一優(yōu)先級(jí)的工序無(wú)次序要求，而不同優(yōu)先級(jí)的工序需按順序加工，如圖1所示，其中J1、J2為兩個(gè)工件，J1的工序?yàn)镺111、O121、O122、O131、O132，分屬F11、F12、F13三個(gè)優(yōu)先級(jí)。

車(chē)間有數(shù)目有限的多能工，不同工人都有其所會(huì)操作的機(jī)器和所會(huì)加工的工序，如圖2所示。

綜上，本文提出多柔性作業(yè)車(chē)間調(diào)度問(wèn)題(Multi-Flexible Job-Shop Scheduling Problem，MFJSP):

有n個(gè)工件J={J1,J2,…,Jn}，m臺(tái)機(jī)器M={M1,M2,…,Mm}，w名工人W={W1,W2,…,Ww}；加工一個(gè)工件Ji的工序分為L(zhǎng)i層優(yōu)先級(jí)F={Fi1,Fi2,…,FiL(i)}，優(yōu)先級(jí)Fij中包含Kij道工序Oij={Oij1,Oij2,…,OijK(ij)}；優(yōu)先級(jí)Fij中的工序Oijk只能在優(yōu)先級(jí)Fij-1中所有工序完成之后被加工；每名工人Wv的技能都由一個(gè)二進(jìn)制矩陣Sv表示，矩陣Sv第p行中第a列的元素表示其是否會(huì)操作機(jī)器Mp完成第a列所對(duì)應(yīng)的工序，如表1所示。

表1 多能工與其所會(huì)的機(jī)器和工序

1.2 符號(hào)定義

除前文已有定義外：

i、e為工件下標(biāo)，J表示工件；L表示對(duì)應(yīng)工件所包含優(yōu)先級(jí)的數(shù)量；j、f為優(yōu)先級(jí)下標(biāo)；k、q、g為工序下標(biāo)；p、r為機(jī)器下標(biāo)；v為工人下標(biāo)；Sv為工人Wv的技能矩陣，元素為0或1表示工人會(huì)或不會(huì)操作機(jī)器完成列所對(duì)應(yīng)的工序；t為加工工序的用時(shí)，transTpr為工件從機(jī)器Mp轉(zhuǎn)移到到機(jī)器Mr的耗時(shí)；Pp為機(jī)器Mp加工工序時(shí)單位時(shí)間的耗能；Cijk、Cifg、Cefg為工序Oijk、Oifg、Oefg的完成時(shí)間，Ci為工件Ji的完成時(shí)間；

模型中決策變量定義如下：

xefgv同上定義。

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

MFJSP數(shù)學(xué)模型如下:

(1)

(2)

(3)

式(1～3)優(yōu)化目標(biāo)：最大完工時(shí)間、總耗能和工人工時(shí)方差。式(4～9)約束條件：式(4)確保在加工一道工序的過(guò)程中不換人和機(jī)器；式(5)確保優(yōu)先級(jí)順序，其中不等式右側(cè)前半部分為前一優(yōu)先級(jí)所有工序均完成且運(yùn)輸?shù)疆?dāng)前工序所在加工機(jī)器的時(shí)刻；式(6)和式(7)分別確保機(jī)器和工人不在同一時(shí)間被占用；式(8)確保工序加工的獨(dú)立性，其中求和的目的是找到加工工序的機(jī)器和工人；式(9)通過(guò)引入技能矩陣Sv(p,ijk)，確保工人只用他所會(huì)的機(jī)器加工他所會(huì)加工的工序，同時(shí)即確保了機(jī)器只能加工它所能加工的工序。

1.4 編碼與解碼

采用整數(shù)編碼，用四條染色體描述一種調(diào)度方案。其中，兩個(gè)染色體分別編碼機(jī)器和工人，其上上的基因值分別代表基因位置對(duì)應(yīng)工序所選擇的機(jī)器和工人，如圖3所示。

另兩條染色體將用于編碼工序排序：一條染色體的基因?yàn)楣ぜ聵?biāo)，其排列順序?yàn)榧庸ご涡颍涣硪粭l的基因?yàn)閺?到工序總數(shù)的不同整數(shù)，其基因位置對(duì)應(yīng)不同工序，如圖4所示。可將圖4中工序排序1染色體中的相同工件按順序和各優(yōu)先級(jí)的工序數(shù)分成各優(yōu)先級(jí)，如圖5所示。對(duì)圖5中的相同優(yōu)先級(jí)中的工序按圖4中工序排序2中染色體上的基因從小到大的順序進(jìn)行排序即可得到實(shí)際的加工順序，如圖6所示。

本文的編碼方式，可從編碼上去除不符合加工順序要求的情況，節(jié)省檢查編碼是否滿(mǎn)足加工順序的計(jì)算資源。

2 離散回溯搜索算法

為對(duì)算法做離散化處理并更好地從整體上反映對(duì)多目標(biāo)優(yōu)化問(wèn)題的優(yōu)化結(jié)果，本文將用于連續(xù)優(yōu)化問(wèn)題的回溯搜索算法(Backtracking Search Algorithm，BSA)做離散化處理，并基于Pareto優(yōu)化和快速非支配排序方法對(duì)其進(jìn)行改進(jìn)，提出了離散回溯搜索算法(Discrete Backtracking Search Algorithm，DBSA)以求解所提出的模型。

2.1 回溯搜索算法簡(jiǎn)述

BSA是一種新型算法[17]，過(guò)程如下:

(1)初始化P(當(dāng)前種群)和OldP(歷史種群)；

(2)通過(guò)公式(10)、公式(11)更新OldP；

(10)

OldP=permuting(OldP)

(11)

(3)根據(jù)公式(12)生成Mutant;

Mutant=P+F×(OldP-P)

(12)

(4)使用P和Mutant根據(jù)公式(13)生成V；

(13)

(5)根據(jù)公式(14)從V中選擇個(gè)體進(jìn)入P；

(14)

(6)重復(fù)步驟(2)～(5)，直到滿(mǎn)足條件。

以上步驟中，步驟(2)和步驟(5)分別被稱(chēng)為選擇I和選擇II，步驟(3)和(4)分別被稱(chēng)為變異和交叉。

2.2 精英化歷史種群

為三個(gè)目標(biāo)函數(shù)選取l,m,n個(gè)權(quán)重值，則可由三個(gè)單獨(dú)的目標(biāo)函數(shù)加權(quán)得到l×m×n種新函數(shù)，在OldP中用每種函數(shù)下的最優(yōu)個(gè)體替換其它個(gè)體。該過(guò)程同時(shí)確保OldP的質(zhì)量和多樣性?？梢允筄ldP在變異步驟中更好地引領(lǐng)P的進(jìn)化。

2.3 離散化變異交叉過(guò)程

本文引入遺傳算法中的交叉算子，使BSA中的變異交叉過(guò)程可以處理離散編碼。將oldp中機(jī)器選擇和工人指派染色體上的基因交換到p上；在工人能力約束下更改p中工人指派染色體上的基因；遴選工序順序1染色體上的基因位置，對(duì)比oldp和p在這些位置上的工件編號(hào)，選取oldp和p其它位置的基因進(jìn)行補(bǔ)充，使oldp的基因交換到p上后，p中染色體上各工件編號(hào)的總數(shù)不變；對(duì)工序順序2染色體，分別以等概率選擇采用基于位置的交叉算子和線性次序交叉算子[18]交換oldp的基因到p上。

2.4 對(duì)選擇Ⅱ的改進(jìn)

本文在步驟選擇Ⅱ中將P和V混合，用快速非支配排序方法[19]將個(gè)體分歸不同非支配等級(jí)，按非支配等級(jí)從低到高逐層將其中個(gè)體更新到P中。相較將P和V中的個(gè)體隨機(jī)配對(duì)進(jìn)行選擇，該方法從Pareto優(yōu)化角度看，可以在每次迭代中獲得更優(yōu)質(zhì)的解集。

3 算法驗(yàn)證/仿真實(shí)驗(yàn)

MFJSP問(wèn)題首次被提出，故本文實(shí)驗(yàn)基于自己創(chuàng)建的數(shù)值實(shí)例，分別使用遺傳算法(GA)[20]、粒子群算法(PSO)[21]、人工蜂群算法(ABC)[22]和DBSA，對(duì)其進(jìn)行求解，并選取相同時(shí)間下各算法的結(jié)果進(jìn)行對(duì)比，圖7中為四種算法對(duì)最大完成時(shí)間的收斂曲線；圖8為DBSA運(yùn)行30min后所得的Pareto非支配解集。

由圖可得，DBSA相對(duì)其它智能算法，收斂速度快，跳出局部最優(yōu)解能力強(qiáng)，且最終可獲得解均勻分布的Pareto非支配解集。圖9為解集中一解對(duì)應(yīng)車(chē)間調(diào)度方案的甘特圖，由圖可以看出其滿(mǎn)足約束條件。

4 結(jié)束語(yǔ)

本文針對(duì)同時(shí)具有機(jī)器、工人和工序柔性的作業(yè)車(chē)間調(diào)度問(wèn)題，建立了多目標(biāo)優(yōu)化模型，并給出四染色體整數(shù)編碼方案，可在編解碼過(guò)程直接滿(mǎn)足模型的約束條件；在BSA的基礎(chǔ)上，重新設(shè)計(jì)了交叉變異步驟，利用快速非支配排序方法更新當(dāng)前種群，并提出精英化種群方法。新算法在求解數(shù)值實(shí)例時(shí)，與多種智能算法相比，具有更快的收斂速度和更強(qiáng)的跳出局部最優(yōu)解的能力。