劉 煬，熊俊西，程 晨，彭 駿

Liu Yang, Xiong Junxi, Cheng Chen, Peng Jun

（合肥工業(yè)大學(xué) 機械與汽車工程學(xué)院，安徽 合肥 230009）

0 引 言

作業(yè)車間生產(chǎn)調(diào)度是企業(yè)從大批量“推動式”生產(chǎn)邁向小批量“拉動式”生產(chǎn)的重要環(huán)節(jié)[1]，對該問題的研究需結(jié)合實際的生產(chǎn)環(huán)境，才能真正實現(xiàn)理論研究的實用化。柔性作業(yè)車間調(diào)度問題[2]（FJSP）釋放了工序的資源約束，是傳統(tǒng)車間調(diào)度問題[3]（JSP）的重要擴展，近年來成為作業(yè)車間調(diào)度的研究熱點[4]。然而，實際環(huán)境下不僅要解決機床分配問題和工序調(diào)度問題，而且要對各工件劃分理想的生產(chǎn)批次和批量。另外，由于增加了批量分配子問題，使算法的設(shè)計過程和問題的值域空間都更加復(fù)雜，求解難度也會進一步增大。因此，對柔性作業(yè)車間分批調(diào)度問題（Flexible Job-shop Scheduling with Lot-splitting Problem，F(xiàn)JSLP）的研究具有重要的實踐價值和學(xué)術(shù)意義。

目前，分批調(diào)度問題因其復(fù)雜性較高，通常采用啟發(fā)式方法求解[5-6]。該方法按照對子問題的處理方式分為分步法[7]和集成法[8]。分步法將復(fù)雜問題劃分為幾個子問題分別求解，雖然可以降低計算難度，但獲得的解只能保證各獨立部分達到最優(yōu)，不能體現(xiàn)整體最優(yōu)，缺乏一定的說服力。集成法求解是將復(fù)雜問題統(tǒng)一考慮，其難點主要有兩點：一是面對大規(guī)模值域如何尋優(yōu)；二是編碼和解碼過程中如何表達模型中復(fù)雜的子批量工序排列。鑒于此，文中基于集成法思想將初始群體采用平衡設(shè)備負荷原則優(yōu)化，設(shè)計工件交貨期越早越優(yōu)先加工的子批工序排序方法，對編碼和解碼過程同時改進，并采用遺傳算法求解，取得了較好效果。

1 問題描述

FJSLP可描述為：生產(chǎn)多個不同種類的產(chǎn)品，各產(chǎn)品具有獨立的工藝順序和生產(chǎn)批量，且產(chǎn)品的工序存在多種加工設(shè)備。調(diào)度目標(biāo)是：為每種工件確定合適的批量；為工件的各道工序確定合適的加工機器；為每臺機器分配合適的工件加工順序，使得系統(tǒng)總目標(biāo)達到最優(yōu)。問題通?；谌缦录僭O(shè)：1）產(chǎn)品的工序事先確定；2）每道工序的加工時間及批次啟動時間確定；3）加工過程中機器不因為人為和非人為的因素而停滯；4）各工件任何時刻都有可能被選擇加工。

同時，具有如下約束條件：1）工藝順序約束，同一批次工件的工序只有在上一道工序完成之后才能繼續(xù)加工；2）加工資源約束，同一臺機器在完成一個批次工件后才能加工另一批次工件；3）子批數(shù)量約束，工件的任一子批量都不能大于工件的總加工數(shù)，且各子批量之和為工件總加工數(shù)；4）子批啟動約束，同一臺機器相鄰加工工件，同批次內(nèi)加工無批次啟動時間，不同批次則必須有批次啟動時間。綜上所述，F(xiàn)JSLP具有以下兩個特征：1）繼承FJSP存在的并行機和多功能機；2）強調(diào)對同種工件的子批工序的排列?；谝陨厦枋?，給出以下最短加工時間的數(shù)學(xué)模型和相關(guān)參數(shù)解釋。

式中，Ei，j，k，m為工件i的子批j的工序k在機器m加工的完工時間；Si，j，k，m為工件i的子批j的第k道工序在機器m上的開始加工時間；ti，j，k，m為工件i的子批j的第k道工序在機器m上的加工時間；ti，j，k k′，m為機器m上相鄰工序k與k′的批次啟動時間；li為工件i的子批數(shù)；ni，l為工件i的第l子批的子批量；Ni為工件i的總加工數(shù)量；T為批次啟動時間，為一常數(shù)。

模型中，式（1）表示調(diào)度目標(biāo)為最小化工件的最大工序完工時間；式（2）～式（5）分別表示問題的工藝順序約束、加工資源約束、子批啟動約束和子批數(shù)量約束。

2 分批調(diào)度算法

2.1 編碼設(shè)計

采用矩陣編碼方式，將問題分解為工件編碼區(qū)、批量編碼區(qū)和工序編碼區(qū)。工件編碼區(qū)行數(shù)為工件的子批數(shù)和，列數(shù)為1，數(shù)值表示工件種類；批量編碼區(qū)數(shù)值為各子批的工件加工數(shù)量；工序編碼區(qū)表示工件各子批的加工工序，列數(shù)為最大子批工序數(shù)，列號為工件工序號，矩陣數(shù)值表示工序?qū)?yīng)的加工設(shè)備，若工件工序數(shù)小于子批最大工序數(shù)，則用“0”補充“虛工序”，即該工序不安排加工設(shè)備。矩陣A即為對應(yīng)表1工件信息的一個編碼。

此編碼方式相比染色體向量編碼[9]問題信息表達更加直接，易于實現(xiàn)算法過程。

表1 工件信息表

2.2 算法詳細描述

2.2.1 初始染色體優(yōu)化

采用平衡設(shè)備負荷規(guī)則為工序安排加工設(shè)備，即工序選擇當(dāng)前累計負荷與工序負荷之和最小的設(shè)備，并將各子批排列成可執(zhí)行的調(diào)度方案，進而獲得質(zhì)量較優(yōu)的染色體。以染色體A為例，算法具體實現(xiàn)過程及中間解如下。

算法——工件分批排序算法。

步驟1：根據(jù)交貨期設(shè)定工件i優(yōu)先級，交貨期越早，優(yōu)先級越高；

步驟2：隨機生成初始種群，基于工件加工優(yōu)先級，以子批量小的優(yōu)先加工原則設(shè)定工件子批排序優(yōu)先級；

步驟3：依據(jù)子批優(yōu)先級為工件i的工藝規(guī)程Pi選擇當(dāng)前累計負荷與加工負荷之和最小的設(shè)備，直到所有工序都被安排；

步驟 4：在模型約束式（2）、式（3）下，排列各批次工序并獲得優(yōu)化染色體。

表2為工件子批加工信息及設(shè)定的工件、子批排序優(yōu)先級等；表3為設(shè)備安排子批工序過程的累計負荷及對應(yīng)的子批工序，表中“1.1.3”表示工件1第1個子批的第3道工序在第1臺設(shè)備上加工；子批順序指為工序安排加工設(shè)備的順序，由子批按照其工藝規(guī)程排列，主要為了避免工件太過集中導(dǎo)致makespan[10]增加。A′為平衡機器負荷后的優(yōu)化染色體。經(jīng)算法 1，初始隨機染色體優(yōu)化為目標(biāo)較優(yōu)染色體。圖1為A′對應(yīng)的時間甘特圖。

表2 工件子批加工信息及排序優(yōu)先級

表3 設(shè)備負荷及加工工序

2.2.2 染色體解碼

解碼是將一個確定的編碼按照設(shè)定的排列規(guī)則轉(zhuǎn)換成一個調(diào)度方案并計算調(diào)度目標(biāo)的過程。設(shè)備前工件采用最短完工時間原則排序，即在模型約束式（2）、式（3）下同一臺設(shè)備前的工件，工序號小的工件進行前移，工序號大的工件后置。

算法2——染色體解碼算法。

步驟1：提取染色體表示的工件子批量ni，l和工件工序集pi對應(yīng)的加工設(shè)備集mi；

步驟2：計算各子批工序加工時間ti，j，k，m×ni,l；

步驟3：結(jié)合工序批次啟動時間，以算法1的排序結(jié)果排列各設(shè)備前的工序；

步驟4：設(shè)工件i的第j道工序為pi，j，并設(shè)i=1，j=1；

步驟5：j′=j+1，若同臺設(shè)備上的工序pi，j開始加工時間≥pi，j′的完工時間，轉(zhuǎn)步驟 6，否則，轉(zhuǎn)步驟7；

步驟6：在pi，j的緊前工序pi，j-1和pi，j′的緊后工序pi，j′+1滿足模型約束式（2）、式（3）下，將工序pi，j和pi，j′分別前移、后置一次，否則，立即停止并返回步驟5；

步驟7：重復(fù)步驟5、步驟6直到設(shè)備工序全部被比較；

步驟8：i=i+1，j=1，返回步驟 5，直到不同工件全部被比較；

步驟9：算法結(jié)束，獲得新的調(diào)度方案。

以A′為實例，經(jīng)解碼算法，獲得新的調(diào)度方案，時間甘特圖如圖2所示。

2.2.3 染色體交叉與變異

遺傳算法的染色體交叉與變異的實際應(yīng)用一直是個難題，交叉后要確定工序在哪臺設(shè)備上加工、工件的批次和工序的排列順序?？紤]到文中染色體在問題中表現(xiàn)的實際意義，交叉后可能會產(chǎn)生過多的不可行解，而重置或剔除這些不可行解會直接導(dǎo)致算法效率降低。因此，染色體交叉后既要保證解的更新，又要保證新的染色體在問題可行域內(nèi)。模型受設(shè)備平衡負荷制約，算法1和算法2已經(jīng)對工序進行工時和負荷的較優(yōu)排列，文中設(shè)計局部交叉策略僅對批次、批量與設(shè)備進行更新。

設(shè)染色體A和A′為不同的問題編碼，染色體總行數(shù)為n，交叉后生成染色體C。交叉時，首先隨機確定染色體A交叉區(qū)的行號k和行數(shù)x并保證k+x-1

變異策略采取以一定概率替換交叉區(qū)的方式，為保證變異的合法性，隨機選擇一個非變異染色體作為替換染色體。

2.3 其他過程設(shè)定

FJSLP模型可行域范圍明顯較FJSP大得多，因此，問題求解最大困難在于如何搜索到較優(yōu)解。鑒于此，在初始化染色體后，首先對染色體進行目標(biāo)優(yōu)化，獲得相對較優(yōu)初始群體。同時，為維持群體多樣性，防止過早收斂，算法以一定概率優(yōu)化初始群體和染色體的交叉、變異，終止條件為設(shè)定最大迭代次數(shù)。算法結(jié)構(gòu)采用遺傳算法的基本流程[11]。

3 實例測試與對比

基于最短完工時間的柔性作業(yè)車間分批調(diào)度模型及遺傳算法已實用于某精密加工車間。文中采用該車間某生產(chǎn)周期內(nèi)的生產(chǎn)任務(wù)作為測試實例。具體描述為：加工4種不同類型的工件，工件產(chǎn)量為8，表4為工序可供選擇的設(shè)備及加工信息。

表4 工序?qū)?yīng)設(shè)備及加工信息

算法仿真環(huán)境為：Intel（R）Core（TM）2、CPU主頻2GHz、內(nèi)存2GB、Windows XP操作系統(tǒng)，采用C#語言實現(xiàn)。設(shè)置遺傳算法經(jīng)驗參數(shù)：初始種群規(guī)模為100，初始染色體優(yōu)化概率為0.5，交叉概率為 0.5，變異概率為 0.1，算法最大迭代次數(shù)為100次。

SPEA作為一類進化算法已被應(yīng)用于求解FJSLP且取得一定效果[11]。因此，選取 SPEA與文中基于集成思想的IGA分別對上述實例求解并對比。同時，為體現(xiàn)集成化IGA的特點，采用文獻[7]提出的一種借助 Witness仿真技術(shù)將批量分配與工序調(diào)度分開處理的優(yōu)化方法。建立前文第1節(jié)中最短完工時間的數(shù)學(xué)模型，評價次數(shù)設(shè)為10000，這里分別給出10次獨立運行結(jié)果。

分步法首先采用Witness的Optimize功能對工件批量進行優(yōu)化，獲得的工件加工批次及批量如表 5所示；然后，將分割的各批次工件看作獨立工件，即將FJSLP轉(zhuǎn)化為FJSP；最后，采用SPEA求解。圖4為SPEA求解的最優(yōu)結(jié)果的時間甘特圖，圖中1.1指工件1的第1道工序，括號內(nèi)數(shù)字為批量。集成化IGA求解時將工件批量與工序調(diào)度融合。首先，編碼過程包含工件批量與工序調(diào)度全部信息；然后，對染色體進行目標(biāo)優(yōu)化時設(shè)計依據(jù)子批優(yōu)先級平衡設(shè)備負荷規(guī)則；最后，在解碼、交叉變異過程中分別對子批進行工藝排序和工序更新。因此，直接獲得各子問題最優(yōu)解，運行后，獲得最優(yōu)時間甘特圖如圖5所示。

表5 工件分批結(jié)果

表6 算法結(jié)果對比

分析表5、表6結(jié)果，分步求解方式可分別獲得批量優(yōu)化子問題與工序調(diào)度子問題優(yōu)化解，但難以保證FJSLP整體最優(yōu)。集成化IGA可對FJSLP整體尋優(yōu)，算法過程解決了FJSLP的子批與工序同時優(yōu)的難點。另外，二者運算速度分別為7.23 s和6.58 s，表明IGA過程簡單，收斂速度快。

4 結(jié)束語

針對柔性分批作業(yè)調(diào)度問題難以集成求解，文中設(shè)計IGA取得較好效果。但該問題在國內(nèi)外研究仍相對較少，可著重對以下幾個方面繼續(xù)研究：1）考慮劃分瓶頸工序與非瓶頸工序，找出影響調(diào)度效率的原因并分析；2）同時考慮多資源約束條件下的調(diào)度模型；3）研究不確定環(huán)境下重調(diào)度問題，考慮生產(chǎn)過程中的突發(fā)因素影響。

[1] 趙爾恭，饒輝樟. 多品種小批量流水作業(yè)生產(chǎn)組織與管理[M].北京：中國鐵道出版社，1981.

[2] 吳秀麗，李蘇劍，杜彥華. 柔性作業(yè)車間多品種小批量調(diào)度算法研究[J]. 中國機械工程，2010，21（4）：424-429.

[3] 陶澤，李小軍，劉曉霞. 基于Petri網(wǎng)和GA的多目標(biāo)動態(tài)優(yōu)化調(diào)度問題研究[J]. 組合機床與自動化加工技術(shù)，2011，（10）：5-9.

[4] 姚嫣菲. 基于改進遺傳算法的車間作業(yè)調(diào)度問題研究[D].浙江：浙江大學(xué). 2010.

[5] Huang R H. Multi-objective job-shop scheduling with lotsplitting production[J]. International Journal of Production Economics，2010，124（1）：206-213.

[6] 白俊杰，龔毅光，王寧生，等. 批量生產(chǎn)柔性作業(yè)車間優(yōu)化調(diào)度研究[J]. 機械科學(xué)與技術(shù)，2010，29（3）：293-298.

[7] 曾強，楊育，王小磊，等. 并行機作業(yè)車間等量分批多目標(biāo)優(yōu)化調(diào)度[J]. 計算機集成制造系統(tǒng)，2011，17（4）：816-825.

[8] 白俊杰，龔毅光，王寧生，等. 多目標(biāo)柔性作業(yè)車間分批優(yōu)化調(diào)度[J]. 計算機集成制造系統(tǒng)，2010，16（2）：396-403.

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

[10] Low C，H Su C M，Huang K I. Benefits of lot splitting in Job Shop scheduling[J]. International Journal of Advanced Manufacturing Technology，2004，24（9-10）：773-780.

[11] 王凌. 車間調(diào)度及其遺傳算法[M]. 北京：清華大學(xué)出版社，2003.

[12] 王云，馮毅雄，譚建榮，等. 柔性作業(yè)車間分批調(diào)度多目標(biāo)優(yōu)化方法[J]. 浙江大學(xué)學(xué)報（工學(xué)版），2011，45（4）： 719-726，764.