*于 華，王 雷

作業(yè)車間批量調(diào)度策略研究

*于 華，王 雷

（安徽工程大學(xué)機(jī)械與汽車工程學(xué)院，安徽，蕪湖 241000）

作業(yè)車間調(diào)度問題是最困難的組合優(yōu)化問題之一，在實際生產(chǎn)中具有廣泛應(yīng)用。調(diào)度的目的是使完工時間最小化。本文針對實際的具有批量調(diào)度問題，分析并比較了幾種調(diào)度策略。采用遺傳算法進(jìn)行求解，針對作業(yè)車間調(diào)度問題使用了一種單親移位算子進(jìn)行交叉和變異以避免不可行解的產(chǎn)生。最后給出了這些調(diào)度策略的仿真實例，結(jié)果表明，使用不同的調(diào)度策略將得到不同的優(yōu)化結(jié)果，為實際的生產(chǎn)提供一定的指導(dǎo)作用。

作業(yè)車間調(diào)度；遺傳算法；單親移位交叉算子；批量調(diào)度

作業(yè)車間調(diào)度問題(Job shop scheduling problem, JSP)是許多實際問題的簡化模型，是最典型、最困難的組合優(yōu)化問題。遺傳算法(Genetic algorithm, GA)作為全局搜索算法，廣泛應(yīng)用于各種優(yōu)化問題中，并已成為求解復(fù)雜JSP問題的主要方法[1-5]。

但是到目前為止，絕大多數(shù)的經(jīng)典車間作業(yè)調(diào)度問題只假設(shè)每種加工工件是單件的情況，而忽視了在實際生產(chǎn)過程中每種工件的加工數(shù)量卻是大于或等于1的任意自然數(shù)。因此，研究在此情況下的批量或者分批調(diào)度才顯得尤為重要。白俊杰等人[6]提出了一種基于粒子群算法的多目標(biāo)柔性分批調(diào)度算法，將工件分割為具有柔性批量的多個子批量，并使子批量的工藝路線選取和加工排序同時得到優(yōu)化。孫志峻等人[5]提出了一種等量分批調(diào)度遺傳算法，使子批數(shù)量的確定和子批加工順序的安排同時得到優(yōu)化。文獻(xiàn)[2]考慮機(jī)床資源的分配和生產(chǎn)調(diào)度的同時，更注重批量調(diào)度，并分析了幾種調(diào)度方案。鞠全勇等人[7]將粒子群算法與遺傳算法相結(jié)合，提出了一種混合優(yōu)化算法求解多目標(biāo)批量調(diào)度問題。曾強(qiáng)等人[8]對基于準(zhǔn)時交貨的批量生產(chǎn)FJSP多目標(biāo)優(yōu)化調(diào)度問題進(jìn)行了研究。以上這些基本上都是從多目標(biāo)的角度或者改進(jìn)智能優(yōu)化算法的角度對批量調(diào)度進(jìn)行了較為深入的研究。而本文研究了基于GA的不同調(diào)度方式對調(diào)度結(jié)果性能的影響，算法的性能不是本文研究的重點問題，主要目的是分析幾種調(diào)度策略多調(diào)度結(jié)果的影響，為研究實際生產(chǎn)調(diào)度問題提供一種可行的指導(dǎo)思想。最后通過實例進(jìn)行了比較分析，仿真結(jié)果表明：使用不同的調(diào)度策略將得到不同的優(yōu)化結(jié)果，在實際的生產(chǎn)中具有重要的指導(dǎo)意義。

1 作業(yè)車間調(diào)度問題描述

一般Job-Shop調(diào)度問題可描述為：有若干個工件，每個工件包含若干個工序，這些工序需要在若干臺設(shè)備上進(jìn)行加工，每道工序有確定的加工時間。調(diào)度的問題是要求給出任務(wù)在加工設(shè)備上的合理排序，以使得目標(biāo)函數(shù)值達(dá)到最優(yōu)。同時做出以下假設(shè)：

(1) 所有工件在零時刻同時到達(dá)；

(2) 每一工件在同一時間只能在一臺設(shè)備上加工；

(3) 工序加工的不可搶占，即若一道工序在一臺設(shè)備上加工，必須加工完成后，才能加工另一道工序；

(4) 一臺設(shè)備在同一時間只能加工一個工件；

(5) 工序的加工時間，是一個事先確定的固定值；

(6) 每一工件的加工路線是固定的，并且每一道工序只能被指定的唯一設(shè)備加工；

(7) 工件的加工允許等待；

(8) 整個加工過程中，設(shè)備連續(xù)可用，無故障；

本文以總完工時間最短為目標(biāo)的數(shù)學(xué)規(guī)劃模型可表示為：

min()=(C) (1)

式中各符號的含義如下：

c：工件在設(shè)備上的完工時間；

t：工件在設(shè)備上的加工時間；

a：如果工件在設(shè)備上先于在設(shè)備上加工，a=1，否則a=0；

x：如果工件先于工件到達(dá)設(shè)備，x=1，否則x=0；

：一個很大的正數(shù)；

式(1)為以完工時間makespan為優(yōu)化目標(biāo)的函數(shù)；式(2)和式(3)分別表示工藝約束和設(shè)備約束。

2 求解車間調(diào)度GA算法

2.1 編碼設(shè)計

求解Job-Shop調(diào)度問題的遺傳算法編碼主要有基于工序的編碼、基于工件的編碼、基于優(yōu)先表編碼、基于優(yōu)先規(guī)則編碼和基于機(jī)器的編碼等多種。由于基于工序的編碼具有編碼和解碼方案簡單、柔性高、容易實現(xiàn)等特點，本文選取基于工序的編碼與解碼。以下以一個簡單的實例來具體闡述基于該編碼與解碼方法的調(diào)度問題。該問題的加工時間和工藝約束如表1所示。

表1 加工時間和工藝約束

Table 1 Processing time and process constraints

設(shè)它的一個染色體為[211312332]，其中1、2和3分別表示工件J1、J2和J3。染色體中從左向右出現(xiàn)數(shù)字的次數(shù)分別表示工件的加工工序，如第一個數(shù)字2表示工件J2的第一道工序，第二個數(shù)字2表示工件J2的第二道工序，其它意義相同。對上述染色體進(jìn)行解碼后得到最優(yōu)調(diào)度Gantt圖如圖1所示，總最小完工時間Makespan = 13。

圖1 解碼獲得的調(diào)度結(jié)果

2.2 適應(yīng)度函數(shù)確定

適應(yīng)度函數(shù)通常取目標(biāo)函數(shù)直接作為適應(yīng)度函數(shù)，在這里取最大的流程時間() = max(C)的倒數(shù)作為適應(yīng)度函數(shù)，由此來計算每個染色體的適應(yīng)度值

() = 1/() (7)

2.3 遺傳操作設(shè)計

（1）復(fù)制

（2）交叉

在一般的遺傳算法中，交叉是一個重要的遺傳算子，是對發(fā)生交叉的雙親隨機(jī)選擇交叉位置后，使交叉點后的部分交換，產(chǎn)生新的個體。但對JSP問題，如果交叉算子使用不當(dāng)會產(chǎn)生不滿足約束條件的解，即非法解。因此，本文采用一個單親移位交叉算子，即通過一個染色體進(jìn)行交叉，這樣不但簡化了遺傳操作，而且可以避免非法解的產(chǎn)生。

算法描述如下：

step1.隨機(jī)產(chǎn)生一個正整數(shù)；

step2.取出染色體中位置后的-個基因；

step3.將取出的基因移動至染色體最前端。

例如1=(123)，=3，則

2=(123)。

在交叉過程中，交叉概率p用于控制交叉操作的頻率。概率太大時，種群中串的更新很快，進(jìn)而會使高適配值的個體很快被破壞掉；概率太小時，交叉操作很少進(jìn)行，從而會使停滯不前。因此，交叉概率介于0.5~0.8之間能很好地平衡這兩者的關(guān)系。

（3）變異

在二進(jìn)制編碼的遺傳算法中，變異是將染色體中某一位由1變?yōu)?，或反之。但在自然數(shù)編碼的情況下，對某一位單獨進(jìn)行變異容易產(chǎn)生非法解。因此，本文采用基因逆序的方法進(jìn)行變異。描述如下：

step1.隨機(jī)產(chǎn)生兩個正整數(shù)1，2，且1不等于2；

step2.將兩個位置之間的基因值逆序放置。

例如，1=(34643)，1=3，2=6，則2=(34643)。

為了加大種群多樣性，要對變異概率p選擇適當(dāng)?shù)臄?shù)值。概率太小則不會產(chǎn)生新個體，概率太大則使GA成為隨機(jī)搜索。因此，選取變異概率為0.05~0.15之間較為合適。

3 調(diào)度實例

現(xiàn)有4個Job類型的工件需要在4臺設(shè)備加工，各個Job類型的各個操作的加工時間和可用機(jī)床等信息，如表2所示。本問題的評價指標(biāo)是尋求最短生產(chǎn)周期（makespan），在此采用GA對于批量調(diào)度的方案進(jìn)行研究。

表2 加工時間和工藝約束

本文采取基于工序的編碼方式，其它遺傳算法參數(shù)選擇：種群規(guī)模= 40，進(jìn)化代數(shù)= 50，交叉概率p= 0.7，變異概率p= 0.1。

? 方案1 單件重復(fù)調(diào)度最小完工時間

對于單件調(diào)度，用遺傳算法尋求到的最小完工時間是24。由于每類加工工件的數(shù)量是3，那么最終加工完所有工件的時間是72(24×3)。圖2所示的是其調(diào)度Gantt圖。從圖中我們可以很容易發(fā)現(xiàn)這種方案存在的不足：以后各批次的開始加工時間都要滿足24的整數(shù)倍，方可開始加工，這樣將使得有些加工設(shè)備沒有得到充分利用，降低了資源的利用率。

圖2 方案1的調(diào)度Gantt圖

? 方案2 整體調(diào)度法

整體調(diào)度法的思想是把要加工每一種工件一次性加工完成，其調(diào)度Gantt圖如圖3所示。從圖中可以看出最終工件全部加工完畢的生產(chǎn)周期是63，比第一種方案節(jié)省9個時間單位。這種方法的優(yōu)點是不需要頻繁的調(diào)整安裝，提高了加工效率。

圖3 方案2的調(diào)度Gantt圖

? 方案3 把每一個加工工件當(dāng)作一個不同類的加工工件看待去調(diào)度加工

此方案完全與前兩種方案的思路與眾不同。此方案并不考慮同種工件之間的數(shù)量。將全部的12個工件當(dāng)作12個互不相同的工件來調(diào)度進(jìn)行加工。圖4所示時其調(diào)度Gantt圖（其中編號1、2和3代表任務(wù)1；4、5和6代表任務(wù)2；7、8和9代表任務(wù)3；10、11和12代表任務(wù)4）。從圖中可以看出加工完所有工件的最小完工時間為60，比第一種方案減少了12個時間單位，比第二種方案減少了3個時間單位，說明使用此種調(diào)度方案可以得到較優(yōu)的結(jié)果。值得注意的是，如果當(dāng)任務(wù)數(shù)量比較大時，使用該方法將得到比其他方案更加好的結(jié)果。

圖4 方案3的調(diào)度Gantt圖

4 結(jié)論

從上述對不同調(diào)度策略方案的調(diào)度結(jié)果分析很容易得到的結(jié)論是：由單批次（單件）所獲得的調(diào)度方案對后續(xù)批次的加工順序起不到指導(dǎo)性的作用，單件最優(yōu)加工順序不適用于批量調(diào)度。因此，在實際的生產(chǎn)過程中可考慮使用“不考慮工件之間的批次性”這種方案加工工件將得到更加優(yōu)化的結(jié)果。

[1] 王萬良,吳啟迪,宋毅.求解作業(yè)車間調(diào)度問題的改進(jìn)型自適應(yīng)遺傳算法[J].系統(tǒng)工程理論與實踐,2004(2): 58-62.

[2] 孫志峻,安進(jìn),黃衛(wèi)清.作業(yè)車間多工藝路線批量作業(yè)計劃優(yōu)化[J].機(jī)械科學(xué)與技術(shù),2002,21(3) :348-350,354.

[3] 張超勇,饒運清,李培根.基于POX交叉的遺傳算法求解Job shop調(diào)度問題[J].中國機(jī)械工程,2004,15(23): 2149-2153.

[4] Byung Joo Park, Hyung Rim Choi, Hyun Soo Kim. A hybrid genetic algorithm for the job shop scheduling problems [J], Computers & Industrial Engineering, 2003, 45(4):597-613.

[5] 孫志峻,安進(jìn),黃衛(wèi)清.作業(yè)車間多工藝路線批量作業(yè)計劃優(yōu)化[J].中國機(jī)械工程,2008,19( 2) :183-187.

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

[7] 鞠全勇,朱劍英.多目標(biāo)批量生產(chǎn)柔性作業(yè)車間優(yōu)化調(diào)度[J].機(jī)械工程學(xué)報, 2007, 43 ( 8 ):148-154.

[8] 曾強(qiáng),楊育,沈玲,等.基于準(zhǔn)時交貨的批量生產(chǎn)FJSP多目標(biāo)優(yōu)化[J].計算機(jī)集成制造系統(tǒng),2011,17(8):1780- 1789.

RESEARCH ON STRATEGY OF JOB-SHOP BATCH SCHEDULING

*YU Hua, WANG Lei

(School of Mechanical and Automotive Engineering, Anhui Polytechnic University, Wuhu, Anhui 241000, China)

Job-shop scheduling problem (JSP) is one of the most difficult combinatorial optimization problems which are widely applied to the practical production. The purpose of job-shop scheduling is to minimize the completion time. Aiming at batch process scheduling problem, several schemes are analyzed and compared. A partheno-genetic operation (PGO) for crossover operation in JSP is proposed in order to avoid unfeasible solutions. Finally, an example is given and the results of these schemes show that the different optimal scheduling results will be obtained by different schemes. Therefore, these schemes can provide certain instructional significance for practical production.

job-shop scheduling; genetic algorithm; partheno-genetic operation; batch process schedule

TP311

A

10.3969/j.issn.1674-8085.2013.01.017

1674-8085(2013)01-0079-04

2012-05-12；

2012-07-20

國家自然科學(xué)基金項目（51175262），安徽省自然科學(xué)基金項目(1208085QE94)，安徽高校省級自然科學(xué)研究項目(KJ2012B008)，安徽工程大學(xué)博士科研啟動基金項目（2011YQQ006）

*于 華(1966-)，女，山東煙臺人，講師，碩士，主要從事機(jī)械制造及其自動化方面的研究(E-mail: yh@ahpu.edu.cn);

王 雷(1982-)，男，安徽亳州人，講師，博士，主要從事制造系統(tǒng)調(diào)度與控制方面的研究(.E-mail:wangdalei2000@126.com)