牛 群 周臺金 王小海 張紅運(yùn)

(上海大學(xué)上海市電站自動化技術(shù)重點實驗室，上海200072)

(上海大學(xué)機(jī)電工程與自動化學(xué)院，上海200072)

并行機(jī)調(diào)度是生產(chǎn)調(diào)度中一類典型的調(diào)度問題，近年來受到研究者的廣泛關(guān)注.已經(jīng)證明目標(biāo)函數(shù)為最小化最大完工時間即Makespan 最小時，僅有兩臺機(jī)器的并行機(jī)調(diào)度問題便是NP-hard 問題［1］.在相同并行機(jī)的研究中，大多數(shù)研究假設(shè)工件之間的調(diào)整時間(setup time)是可忽略不計的.這種假設(shè)能夠簡化問題模型，便于求解，但在實際的生產(chǎn)條件下，尤其是調(diào)整時間依賴于工件加工順序中的前一個加工工件及工件的分組技術(shù)時，調(diào)整時間是不可忽略的.研究表明，在生產(chǎn)調(diào)度中，若充分考慮調(diào)整時間的影響，會使調(diào)度模型能更好地解決實際問題，從而為企業(yè)降低成本.帶調(diào)整時間的相同并行機(jī)調(diào)度問題的研究方法主要包括精確方法和啟發(fā)式方法.

Lee 等［2］針對該問題，提出了一種三階段啟發(fā)式方法.Armentano 等［3］研究了帶調(diào)整時間的相同并行機(jī)調(diào)度問題，提出了一種貪婪式隨機(jī)搜索自適應(yīng)程序，并且結(jié)合基于記憶準(zhǔn)則的方法來構(gòu)造初始種群.何軍輝等［4］對含有非常數(shù)調(diào)整時間的并行機(jī)作業(yè)排序問題，設(shè)計了一種遺傳算法的實現(xiàn)形式.

由于精確算法僅適于小規(guī)模調(diào)度問題，因此智能優(yōu)化方法被廣泛應(yīng)用于調(diào)度問題，如遺傳算法、模擬退火等，并取得了良好的效果，由于智能方法簡潔、方便、易于實現(xiàn)，因此已成為解決調(diào)度問題的一個研究熱點.克隆選擇是生物免疫系統(tǒng)的重要學(xué)說，通過這一概念發(fā)展起來的克隆選擇算法已經(jīng)廣泛應(yīng)用于許多優(yōu)化問題，如旅行商問題、背包問題、電磁優(yōu)化設(shè)計等.克隆選擇算法在調(diào)度問題中也有應(yīng)用，Yang 等［5］采用克隆選擇算法求解Job Shop調(diào)度問題，并結(jié)合了局部搜索方法來增強(qiáng)算法的尋優(yōu)能力.Kumar 等［6］提出了一種新的克隆選擇算法來解決連續(xù)的flow shop 調(diào)度問題.劉曉冰等［7］將免疫克隆選擇算法應(yīng)用于柔性生產(chǎn)調(diào)度問題，然后著重設(shè)計了克隆免疫算子，最后運(yùn)用該模型對一個實際生產(chǎn)系統(tǒng)進(jìn)行仿真調(diào)度.

克隆選擇算法雖然已經(jīng)應(yīng)用于多種優(yōu)化領(lǐng)域，并取得了顯著的效果，但在生產(chǎn)調(diào)度方面尤其是對并行機(jī)調(diào)度問題的研究較少，因此本文采用克隆選擇算法來優(yōu)化帶調(diào)整時間的并行機(jī)調(diào)度問題，并針對該調(diào)度模型，提出了一種改進(jìn)的克隆選擇算法.該算法采用單機(jī)排序的編碼方式來代替?zhèn)鹘y(tǒng)編碼方式，從而簡化了問題求解;為了能夠加快算法搜索性能，提出了一種新的啟發(fā)式方法來產(chǎn)生初始種群;并且，針對克隆選擇算法中重要的變異算子，本文比較了4 種變異方式并給出了分析;最后通過仿真實例進(jìn)一步驗證了改進(jìn)方法的有效性.

1 含調(diào)整時間的并行機(jī)調(diào)度問題描述

并行機(jī)調(diào)度問題可以描述為:設(shè)有m(m ＞1)臺并行機(jī)器，需要加工n 個工件，這些并行機(jī)的加工性能是完全相同的，每個工件可在任一臺機(jī)器上完成加工，同時也需要滿足以下約束:每臺機(jī)器在每一時刻只能加工一個工件，一個工件一旦在機(jī)器上加工就不能中斷，必須要等該工件被加工完成之后，才能加工其他的工件.本文所研究的問題是帶調(diào)整時間的并行機(jī)調(diào)度，所謂的調(diào)整時間就是指機(jī)器i 在加工工件j 完成之后，要進(jìn)入加工工件k時，中間有一個機(jī)器調(diào)整時間，只有在機(jī)器調(diào)整好之后才能加工工件k，所以在計算Makespan 時必須要考慮工件的加工時間和機(jī)器的調(diào)整時間.設(shè)在機(jī)器i 上加工的工件排序為π={σ1，σ2，…，σj，…，σk}，則在機(jī)器i 上加工的工件σj的開工時間tS(i，σj)和完工時間tC(i，σj)由下面公式計算:

式中，i=1，2，…，m，i 表示機(jī)器指針，m 為并行機(jī)的機(jī)器數(shù);j =1，2，…，k，j 表示工件指針，k 表示在機(jī)器i 上待加工工件的數(shù)目;pij為第j 個工件在機(jī)器i上的加工處理時間;sj1，j2為假設(shè)j1，j2在同一臺機(jī)器上加工時從工件j1轉(zhuǎn)到工件j2的調(diào)整時間.

本文的目標(biāo)函數(shù)是最大完成時間的最小化(Makespan)，可由下式表示:

式中，σk表示機(jī)器i 上的最后一個被加工的工件.

2 改進(jìn)的克隆選擇算法求解并行機(jī)調(diào)度

克隆選擇算法(clonal selection algorithm，CSA)是基于生物獲得性免疫的克隆選擇原理［8］而發(fā)展起來的一種優(yōu)化方法，當(dāng)生物免疫系統(tǒng)遇到抗原入侵時，系統(tǒng)能夠快速找到與之相匹配的抗體進(jìn)行免疫應(yīng)答，最終消除抗原.由于外界的抗原具有多樣性，所以生物免疫系統(tǒng)能夠保持抗體的多樣性.克隆選擇算法根據(jù)抗體群體按一定比例數(shù)目進(jìn)行克隆，然后再進(jìn)行高頻變異操作，從而保持了整個群體的多樣性.由于該算法操作比較簡單，且參數(shù)設(shè)置較少，因此已經(jīng)成功應(yīng)用于許多優(yōu)化問題.克隆選擇算法主要包括3 個操作步驟:克隆復(fù)制操作、克隆變異操作和克隆選擇操作.

基本的克隆選擇算法通過復(fù)制多個優(yōu)秀抗體，然后對這些抗體進(jìn)行變異產(chǎn)生新的抗體，經(jīng)過迭代優(yōu)化找到問題的最優(yōu)解.因此，該算法尋優(yōu)性能跟初始種群有關(guān)，若初始種群較好，則該算法的求解效率較高.為了提高克隆選擇算法的求解性能，本文提出了一種基于單機(jī)排序的均勻插入分割點的編碼方法以及新的啟發(fā)式方法的改進(jìn)克隆選擇算法.

2.1 基于單機(jī)排序的編碼方法

擴(kuò)展順序表達(dá)方式和分段編碼方式能夠保證產(chǎn)生的調(diào)度方案都是可行解，能夠清晰表示每臺機(jī)器要加工的工件以及工件被加工的順序，因此這兩種編碼方式是并行機(jī)調(diào)度問題常用的2 種編碼方式.①擴(kuò)展順序表達(dá)方式.Cheng 等［9］針對含帶調(diào)整時間的并行機(jī)調(diào)度問題提出了一種新的編碼方式，即擴(kuò)展順序表達(dá)方式，首先將n 個工件的編號進(jìn)行隨機(jī)全排列，然后隨機(jī)插入m－1 個分隔符“* ”，這個分隔符是用來區(qū)分不同機(jī)器上的工件.②分段編碼方式.在文獻(xiàn)［10］中，將染色體分為兩段基因串，每臺機(jī)器加工的任務(wù)代號依次排列作為第一段基因串，每臺機(jī)器上的任務(wù)加工總數(shù)作為第一段基因串，則染色體可以表示如下:

其中，Lij表示機(jī)器i 上第j 次加工任務(wù)的代號;ki表示在機(jī)器i 上加工的工件數(shù)目;i∈［1，m］，j∈［1，ki］，Lij∈［1，n］，且Lij取互不相同的自然數(shù)，因為所有的n個工件必須在m 臺機(jī)器上加工完，所以

上述2 種編碼方式能夠保證產(chǎn)生的調(diào)度方案都是可行解，但卻有較大的隨機(jī)性，例如10 工件3機(jī)器的并行機(jī)調(diào)度問題，產(chǎn)生的排序為［3 7 2 6 8 4 5 10 9 1］，隨機(jī)產(chǎn)生的分割點為2 和8，即［3 7 ×2 6 8 4 5 10 ×9 1］，這樣勢必導(dǎo)致第二臺機(jī)器加工的工件較多，從而打破了每臺機(jī)器上的負(fù)載平衡，導(dǎo)致了該可行解惡化，因此分割點位置的產(chǎn)生非常關(guān)鍵.考慮到并行機(jī)調(diào)度問題的特點，希望每臺機(jī)器上最后一個工件的完工時間比較接近，即每臺機(jī)器上加工的工件時間越均衡，越有利于得到好的Makespan，因此本文提出了一種新的結(jié)合模型特點的編碼方式，即單機(jī)排序編碼方式.首先將n 個工件的編號進(jìn)行隨機(jī)排列并放置到單臺機(jī)器上，如果沒有考慮工件之間的調(diào)整時間，那么所有可行解中工件的完工時間累加應(yīng)該是相同的，但是因為考慮了調(diào)整時間，因此不同可行解的結(jié)果不會相同，每個可行解中n 個工件的加工時間和調(diào)整時間總和為T，那么每臺機(jī)器上期望的加工工件時間為tp=T/m，然后按照pt 進(jìn)行分段，找到最接近tp的m－1 個分割點.本文提出的這種編碼方法與上述1)方法不同之處在于并不隨機(jī)插入分隔符，而是根據(jù)權(quán)衡每臺機(jī)器上總的工件加工時間和調(diào)整時間，使分割點盡量均衡，從而更有利于最優(yōu)Makspan 的求解.

2.2 一種新的啟發(fā)式方法

一般情況下，在求解優(yōu)化問題時，初始種群是隨機(jī)產(chǎn)生的.為了更好地提高算法的收斂能力，本文提出了一種采用啟發(fā)式方法來產(chǎn)生一部分可行解作為初始種群的方法，該啟發(fā)式方法是基于單機(jī)調(diào)度模型提出來的，可以用下面步驟來描述:

①令k=1，n 表示工件的數(shù)目.

②判斷是否滿足停止條件，若滿足，跳出循環(huán)，否則，進(jìn)入③.

③以工件k 作為起始的加工工件，然后查詢該工件與其他工件之間的調(diào)整時間，找到調(diào)整時間最小的那個工件作為下一個加工工件.依此類推，直至所有工件均被加工為止.

④令k=k+1，返回②.

2.3 克隆復(fù)制操作

本文首先將抗體的親和度進(jìn)行排序，將種群中所有抗體由好到壞進(jìn)行排序，根據(jù)抗體在種群中的位置來確定抗體克隆的數(shù)目.抗體克隆數(shù)目的大小由下式表示:

式中，Nt為第t 個個體被克隆的數(shù)目;M 為表示初始種群的規(guī)模;β 為個體的克隆規(guī)模.

2.4 克隆變異操作

變異操作是克隆選擇算法當(dāng)中最主要的操作，也是保持種群多樣性和種群進(jìn)化的操作.變異方法有很多種，本文采用了文獻(xiàn)［11］中的4 種變異方法.

2.5 克隆選擇操作

將每個個體經(jīng)過克隆復(fù)制和變異之后的個體與原始個體進(jìn)行比較，若克隆復(fù)制和變異之后的個體比原始個體優(yōu)，則用變異后的個體替換原來個體進(jìn)入下一代，否則原始個體進(jìn)入下一代循環(huán).

2.6 改進(jìn)的克隆選擇算法-HSMCSA

改進(jìn)的克隆選擇算法解決并行機(jī)調(diào)度問題，主要的改進(jìn)措施為:采用單機(jī)排序編碼方式、根據(jù)單機(jī)調(diào)度最優(yōu)解與隨機(jī)混合的啟發(fā)式方法產(chǎn)生初始種群以及根據(jù)單機(jī)調(diào)度模型以及均勻插入分割點來計算種群中每個個體的親和度.改進(jìn)的克隆選擇算法主要步驟如下:

①根據(jù)啟發(fā)式方法生成一個規(guī)模為M 的初始種群pop，并確定各種參數(shù)的值.

②計算種群個體的親和度，根據(jù)目標(biāo)函數(shù)來判斷個體好壞，將個體從好到壞進(jìn)行排序，根據(jù)個體在種群中的位置來確定個體克隆復(fù)制的數(shù)目.

③對克隆后的抗體執(zhí)行變異操作，變異按概率等于1 進(jìn)行變異.

④重新計算變異后的抗體的親和度，將初始種群的每個個體與該個體行克隆復(fù)制和變異操作得到多個抗體進(jìn)行比較，選出其中最好的一個抗體進(jìn)入下一代.

⑤另迭代次數(shù)t=t +1，檢查是否滿足終止條件，若滿足，終止迭代，輸出最優(yōu)解;若不滿足，則轉(zhuǎn)到②，進(jìn)行下一個迭代操作.

3 仿真結(jié)果及其分析

3.1 四種變異算子的比較

本文所提出的采用單機(jī)排序編碼方式的克隆選擇算法對文獻(xiàn)［4］中的2 個算例進(jìn)行求解比較4種變異操作結(jié)果，一個10 工件3 機(jī)器，另外一個算例是20 工件5 機(jī)器.參數(shù)設(shè)置如下時:個體的克隆規(guī)模β=0.5，變異概率Pm=1，啟發(fā)式生成的個體占種群規(guī)模比例HR=0.5，運(yùn)行10 次，結(jié)果如表1所示，表1中“S”表示種群規(guī)模，“Best”表示運(yùn)行10 次的最好解，“Ave”表示運(yùn)行10 次的平均解.

從表1中可以看出采用兩點互換變異操作比其他三種變異操作所得到的結(jié)果優(yōu)，同時從表1可以看出，用本文所提出的克隆選擇算法找到的解要比文獻(xiàn)［4］中采用遺傳算法找到的解優(yōu).

表1 克隆選擇算法采用4 種不同變異的結(jié)果比較

3.2 啟發(fā)式方法的仿真結(jié)果

為了驗證2.2 章節(jié)提出的啟發(fā)式方法的有效性，采用文獻(xiàn)［4］中的算例進(jìn)行仿真，表2給出了不同比例下(HR)的啟發(fā)式方法產(chǎn)生初始種群的仿真結(jié)果，“HR =0”表示初始種群全部隨機(jī)產(chǎn)生，“HR=0.3”表示初始種群中有30%的個體采用啟發(fā)式方法生產(chǎn)，70%的個體隨機(jī)生成.參數(shù)的設(shè)置:種群規(guī)模M =20，最大迭代次數(shù)T =1 000，β=0.5，Pm=1，運(yùn)行20 次.表2中“Best”表示運(yùn)行20 次中找到的最好解，“Ave”表示運(yùn)行20 次的平均解，“Worst”表示運(yùn)行20 次中找到的最差解.

表2 不同比例下啟發(fā)式方法的結(jié)果比較

從表2可以看出，當(dāng)HR ＞0 時，所有的比例下得到的解均好于HR =0 的情況.這說明加入啟發(fā)式的方法產(chǎn)生初始種群比隨機(jī)產(chǎn)生初始種群更加有效.表2同時表明在全部用啟發(fā)式方法產(chǎn)生初始種群，即HR=1 得到的結(jié)果還沒有部分用啟發(fā)式方法產(chǎn)生初始種群的結(jié)果要好，說明全部用啟發(fā)式方法產(chǎn)生初始種群經(jīng)過迭代容易陷入局部最優(yōu)，然而在初始種群中加入一些隨機(jī)產(chǎn)生的解能夠增加種群的多樣性，克服早熟收斂.從表2的各種比例的對比可以進(jìn)一步發(fā)現(xiàn)當(dāng)HR =0.5 時，所得結(jié)果最優(yōu).

3.3 4 種算法的仿真結(jié)果

為了進(jìn)一步驗證本文所提出的采用單機(jī)排序編碼方式的克隆選擇算法的有效性，隨機(jī)生成了24 組算例，共有4 種規(guī)模:50 個工件5 臺并行機(jī)、60 個工件5 臺并行機(jī)、70 個工件5 臺并行機(jī)以及80 個工件5 臺并行機(jī)，每個規(guī)模隨機(jī)生成了6 個算例，工件的加工時間和機(jī)器的調(diào)整時間是根據(jù)均一分布產(chǎn)生，加工時間服從U{1，100}的均一分布，調(diào)整時間服從U{1，50}的均一分布.表3當(dāng)中的“50－5－1”表示50 個工件、5 臺并行機(jī)規(guī)模下的第一個算例.表3表示了這24 組算例的運(yùn)行結(jié)果，其算法的參數(shù)選擇如下所述:種群規(guī)模M =20，最大迭代次數(shù)T=1 000，個體的克隆規(guī)模β=0.5，變異概率Pm=1，生成的個體占種群規(guī)模比例HR =0.5，運(yùn)行20 次，采用遺傳算法(GA)，采用擴(kuò)展順序表達(dá)方式進(jìn)行編碼的克隆選擇算法(CSA)，單機(jī)排序編碼方式的克隆選擇算法(SMCSA)以及50%初始種群由啟發(fā)式方法產(chǎn)生(HR =0.5)的單機(jī)排序編碼方式的克隆選擇算法(HSMCSA)這4 種算法進(jìn)行驗證這24 組算例.遺傳算法(GA)的交叉算子采用的是文獻(xiàn)［8］中的交叉算子交叉概率Pc=0.8，變異概率Pm=0.2.本文的采用兩點互換的變異方式.同時，表3中“Best”與“Ave”表示的含義與表2相同.由表3的數(shù)據(jù)分析可得如下結(jié)論:

表3 24 組算例的運(yùn)行結(jié)果

1)3 種克隆選擇算法(CSA，SMCSA 和HSMCSA)得到的最優(yōu)解和平均解都要優(yōu)于遺傳算法的解，說明克隆選擇算法很適合并行機(jī)調(diào)度問題的求解.

2)在算例規(guī)模小的時候，SMCSA 的解與CSA 的解比較相近，但隨著問題規(guī)模的增加，SMCSA 的求解性能優(yōu)于CSA 算法，說明采用單機(jī)排序的克隆選擇算法比隨機(jī)編碼機(jī)制更有優(yōu)勢.

3)HSMCSA 算法得到的結(jié)果在4 種算法中最優(yōu)，通過24 組算例數(shù)據(jù)的計算可得出，HSMCSA 相比GA 求解性能提高了18.5%，相比CSA 提高了7.2%，相比SMCSA 提高了6.6%.而且，隨著算例規(guī)模的增大，這種優(yōu)勢更加明顯.

4 結(jié)語

本文采用了克隆選擇算法來求解帶調(diào)整時間的相同并行機(jī)調(diào)度問題.針對并行機(jī)調(diào)度問題，提出了一種基于單機(jī)排序的編碼方式.為了進(jìn)一步提高克隆算法的求解性能，提出一種新的啟發(fā)式方法產(chǎn)生初始種群，即HSMCSA.仿真結(jié)果表明，本文所提出的HSMCSA 求解帶調(diào)整時間的相同并行機(jī)調(diào)度問題非常有效，在其優(yōu)化性能上優(yōu)于本文所提出的其他算法.因此，進(jìn)一步工作可將HSMCSA 應(yīng)用于其他車間調(diào)度問題中.

References)

［1］Garey M R，Johnson D S.Computers and intractability:a guide to the theory of NP-completeness［M］.San Francisco:Freeman，USA，1979.

［2］Lee Y H，Pinedo M.Scheduling jobs on parallel machines with sequence-dependent setup times［J］.European Journal of Operational Research，1997，100(3):464-474.

［3］Armentano V A，F(xiàn)ranca M F.Minimizing total tardiness in parallel machine scheduling with setup times:an adaptive memory-based GRASP approach［J］.European Journal of Operational Research，2007，183(1):100-114.

［4］何軍輝，周泓.求解含調(diào)整時間并行機(jī)排序問題的遺傳算法［J］.系統(tǒng)工程理論方法應(yīng)用，2002，11(4):285-289.

He Junhui，Zhou Hong.A kind of genetic algorithm for solving parallel machine scheduling problems with setup times［J］.Systems Engineering-Theory Methodology Application，2002，11(4):285-289.(in Chinese)

［5］Yang Jinhui，SuLiang N，Lee H P，et al.Clonal selection based memetic algorithm for job shop scheduling problems［J］.Journal of Bionic Engineering，2008，5(2):111-119.

［6］Kumar A，Prakash A，Shankar R，et al.Psycho-clonal algorithm based approach to solve continuous flow shop scheduling problem［J］.Expert Systems with Applications，2006，31(3):504-514.

［7］劉曉冰，呂強(qiáng).免疫克隆選擇算法求解柔性生產(chǎn)調(diào)度問題［J］.控制與決策，2008，23(7):781-785.

Liu Xiaobing，Lü Qiang.Immune clonal selection algorithm for flexible job-shop scheduling problem［J］.Control and Decision，2008，23(7):781-785.(in Chinese)

［8］Castro L N，Zuben F J.Learning and optimization using the clonal selection principle［J］.IEEE Trans on Evolutionary Computation，2002，6(3):239-251.

［9］Cheng Runwei，Gen M.Parallel machine scheduling problems using memetic algorithms［J］.Computers and Industrial Engineering，1997，33(3/4):761-764.

［10］劉民，吳澄.進(jìn)化規(guī)劃方法在最小化拖期任務(wù)數(shù)并行機(jī)調(diào)度問題中的應(yīng)用［J］.電子學(xué)報，1999，27(7):132-134.

Liu Min，Wu Cheng.Application of evolutionary programming method in parallel machine scheduling problem of minimizing the number of tardy jobs［J］.Actaelectronica Sinica，1999，27(7):132-134.(in Chinese)

［11］Eiben A E，Smith J E.Introduction to evolutionary computing［M］.Springer，2007.