郭麗萍，李向濤，谷文祥，2，殷明浩

(1.東北師范大學(xué)計(jì)算機(jī)科學(xué)與信息技術(shù)學(xué)院，吉林長春130117;2.長春建筑學(xué)院基礎(chǔ)教學(xué)部，吉林長春130607)

流水線調(diào)度問題是一類重要的組合優(yōu)化問題，阻塞流水線調(diào)度問題作為其中的一個(gè)重要分支，由于具有很強(qiáng)的工程背景和實(shí)際意義，而得到了越來越多學(xué)者的關(guān)注，目前人們已經(jīng)證明包含2臺機(jī)器以上的阻塞流水線調(diào)度問題的計(jì)算復(fù)雜性為NP-hard［1］.該問題的解決方法主要分為構(gòu)造性啟發(fā)式方法［2-3］和元啟發(fā)式方法［4-7］.螢火蟲算法［8］是由劍橋大學(xué)的Yang在2008年提出來的一個(gè)模擬自然界中螢火蟲發(fā)光行為的仿生算法，目前該算法在函數(shù)優(yōu)化方面表現(xiàn)出較優(yōu)的性能［9］.為了使螢火蟲算法適用于求解阻塞流水線調(diào)度問題，本文對螢火蟲算法進(jìn)行了一些改進(jìn)，加強(qiáng)了算法的搜索性能，且避免了螢火蟲算法早熟的問題.

1 阻塞流水線調(diào)度問題

阻塞流水線調(diào)度問題可以描述為:n個(gè)作業(yè)J1，J2，…，Jn要在 m 臺機(jī)器 M1，M2，…，Mm上運(yùn)行，每個(gè)作業(yè)包含m道工序，每個(gè)作業(yè)的工序必須按照統(tǒng)一順序在m臺機(jī)器上執(zhí)行，每個(gè)作業(yè)在每臺機(jī)器上的運(yùn)行時(shí)間是固定的，要求協(xié)調(diào)不同作業(yè)的執(zhí)行順序，使得某種生產(chǎn)性能指標(biāo)達(dá)到最優(yōu).阻塞流水線調(diào)度問題的約束條件包括如下:

1)每個(gè)作業(yè)在每臺機(jī)器上只能加工1次;

2)每臺機(jī)器每次最多只能加工1道工序;

3)每臺機(jī)器上的作業(yè)加工順序相同;

4)作業(yè)的某道工序在某臺機(jī)器上的加工一旦開始，便不能終止;

5)一個(gè)作業(yè)完成某道工序后，該作業(yè)將在當(dāng)前機(jī)器上滯留直到下游機(jī)器變?yōu)榭捎脼橹?

在該問題中，用 π ={π1，π2，…，πn}表示一個(gè)調(diào)度序列，oj，k(j=1，2，…，n;k=1，2，…，m)表示作業(yè)j在機(jī)器k上執(zhí)行一個(gè)無間斷的工序，其所需時(shí)間為 pj，k(j=1，2，…，n;k=1，2，…，m)，ej，k(j=1，2，…，n;k=0，1，…，m)表示第j個(gè)作業(yè)在第k臺機(jī)器上的離開時(shí)間.則有:

本文選取最大完工時(shí)間最小為優(yōu)化指標(biāo)，那么最大完工時(shí)間Cmax(π)=en，m，且它的計(jì)算復(fù)雜性為O(mn).

以3個(gè)作業(yè)J1、J2、J3為例，下面舉例說明如何求解阻塞流水線調(diào)度問題，3個(gè)作業(yè)在3臺機(jī)器上運(yùn)行所需時(shí)間如表1所示.第1個(gè)作業(yè)在第1臺機(jī)器上運(yùn)行所需要的時(shí)間為3，第1個(gè)作業(yè)在第2臺機(jī)器上運(yùn)行所需要的時(shí)間為4，依此類推.

表1 時(shí)間矩陣Table 1 Time matrix of an example

由式(1)～(5)可以計(jì)算出該問題的最大完工時(shí)間的最小值 e3，3為21，對應(yīng)的作業(yè)執(zhí)行順序?yàn)閧J3，J2，J1}，如圖 1 所示.

圖1 問題的甘特圖表示Fig.1 The Gantt chart of the example

2 螢火蟲算法

螢火蟲算法是一種通過模擬自然界中螢火蟲發(fā)光行為的仿生算法.目前，人們對自然界中螢火蟲的發(fā)光行為的意義還存在很多爭議，不過有2點(diǎn)是確定的:吸引配偶和吸引潛在的獵物.

一般情況下，可見光的強(qiáng)度隨著當(dāng)前位置到光源距離的增大而減小，另外，空氣還要吸收一部分光源.因此，螢火蟲發(fā)出光只在一定的距離范圍內(nèi)可以被其他螢火蟲看見.螢火蟲算法約定［9］:1)螢火蟲之間不存在性別之分，每只螢火蟲都可以吸引其他的螢火蟲，也可以被其他的螢火蟲吸引;2)螢火蟲的吸引力和它們發(fā)出的光的亮度成正比，因此，對于任意2只螢火蟲來說，亮度較弱的螢火蟲會(huì)朝著亮度較強(qiáng)的螢火蟲飛行;如果當(dāng)前可見光距離范圍內(nèi)，沒有比自己更亮的螢火蟲時(shí)，則該螢火蟲實(shí)行隨機(jī)飛行策略;3)光的亮度一般由求解問題的目標(biāo)函數(shù)決定.

在螢火蟲算法中，每只螢火蟲稱為一個(gè)“個(gè)體”，每個(gè)個(gè)體包含亮度、吸引力、位置等屬性.在該算法中，個(gè)體在某個(gè)固定位置的亮度I是固定的，該變量的設(shè)定取決于具體問題的目標(biāo)函數(shù).其他個(gè)體看到該個(gè)體的亮度則隨著它們之間距離的增大而減小，此外，傳播介質(zhì)也會(huì)吸收一部分光線，因此，個(gè)體在距離當(dāng)前位置r處的亮度還和介質(zhì)的吸收率有關(guān)［9］.一般把一個(gè)個(gè)體在距離該個(gè)體r處的亮度表示為

式中:I0為個(gè)體在當(dāng)前所處位置的亮度，γ為介質(zhì)的吸收率.有時(shí)，為了減小個(gè)體亮度變?nèi)醯乃俾剩?6)也可用如下公式代替:

每個(gè)個(gè)體對其他個(gè)體的吸引力β也是相對的，它隨著2個(gè)個(gè)體之間距離的增大而減小;此外，吸引力還和介質(zhì)的吸收率有關(guān)［9］.因此把個(gè)體在距離該個(gè)體為r的位置對其他個(gè)體的吸引力定義為

式中:β0表示2個(gè)個(gè)體距離為0時(shí)，當(dāng)前個(gè)體對另外1個(gè)個(gè)體的吸引力，γ為介質(zhì)的吸收率.

在該算法中，2個(gè)個(gè)體之間的距離r采用歐式距離.個(gè)體i向著比它更亮的個(gè)體j進(jìn)行更新的公式定義為

式中:xi和xj分別表示個(gè)體i和個(gè)體j在整個(gè)種群更新之前的位置，x'i表示個(gè)體i朝著比自己更亮的個(gè)體j更新之后的位置，rij代表個(gè)體i和個(gè)體j之間的距離，β0e－γr2ij表示個(gè)體 j對個(gè)體 i的吸引力，α 是一個(gè)［0，1］內(nèi)的隨機(jī)數(shù)，R為一個(gè)隨機(jī)數(shù)生成函數(shù)，生成［0，1］內(nèi)的隨機(jī)數(shù).

3 改進(jìn)的螢火蟲算法求解阻塞流水線調(diào)度問題

雖然螢火蟲算法在函數(shù)優(yōu)化方面表現(xiàn)出了較好的計(jì)算性能，但是，它在求解阻塞流水線調(diào)度問題中仍然存在早熟現(xiàn)象，為了提高算法的尋優(yōu)性能，本文對螢火蟲算法進(jìn)行了一些改進(jìn).

螢火蟲算法應(yīng)用于求解阻塞流水線調(diào)度問題時(shí)，首先遇到的問題就是如何將實(shí)數(shù)編碼離散化.本文提出一種最小排序方法，這種方法可以將個(gè)體的實(shí)數(shù)編碼形式轉(zhuǎn)化成離散的調(diào)度序列.該方法對初始化后的實(shí)數(shù)序列從小到大進(jìn)行排序，它們的排序序號構(gòu)成一個(gè)離散序列，將這個(gè)序列作為該實(shí)數(shù)序列對應(yīng)的離散調(diào)度序列.如表2所示，0.43是實(shí)數(shù)編碼序列中最小的實(shí)數(shù)，從小到大排序后，它的序號應(yīng)該為1;同理，0.91是實(shí)數(shù)序列中最大的，因此其序號為5.新生產(chǎn)的序列{4，2，5，1，3}作為實(shí)數(shù)序列{0.85，0.56，0.91，0.43，0.76}對應(yīng)的離散調(diào)度序列.

表2 個(gè)體表示形式Table 2 The presentation of an object

其次，在種群初始化時(shí)，本文設(shè)計(jì)了一種雙重初始化方法:分別生成2個(gè)種群，計(jì)算2個(gè)種群中每個(gè)個(gè)體的最小完工時(shí)間.讓2個(gè)種群中的個(gè)體按序號兩兩進(jìn)行比較:種群1中的第1個(gè)個(gè)體和種群2中的第1個(gè)個(gè)體進(jìn)行比較，選擇其中最小完工時(shí)間較小的個(gè)體，作為新種群的第1個(gè)個(gè)體;種群1中的第2個(gè)個(gè)體和種群2中的第2個(gè)個(gè)體進(jìn)行比較，選擇其中最小完工時(shí)間較小的一個(gè)，作為新種群的第2個(gè)個(gè)體;依此類推，新種群作為初始化種群.此外，由于 NEH(Nawaz-Enscore-Ham)［10］啟發(fā)式算法是目前求解流水線調(diào)度最有效的啟發(fā)式方法之一，因此，在初始化種群時(shí)還引入了NEH的思想.種群的第1個(gè)個(gè)體由NEH啟發(fā)式方法生成，其他個(gè)體由雙重初始化方式生成，從而使得算法有一個(gè)較好的初始化環(huán)境.

目前，人們已經(jīng)發(fā)現(xiàn)很多昆蟲存在萊維飛行(Lévy flights)［11-12］，且萊維飛行已經(jīng)應(yīng)用于優(yōu)化領(lǐng)域，并取得了預(yù)期的良好效果.為了增強(qiáng)算法的全局搜索性能，避免種群陷入局部最優(yōu)，在螢火蟲算法的搜索過程中，如果當(dāng)前個(gè)體找不到比自己更優(yōu)的個(gè)體時(shí)，選擇萊維飛行代替原算法中的隨機(jī)飛行.此外，對于那些種群中非最優(yōu)的個(gè)體，對它們的飛行公式進(jìn)行改進(jìn):當(dāng)它們發(fā)現(xiàn)比自己更亮的個(gè)體時(shí)，首先由系統(tǒng)產(chǎn)生一個(gè)隨機(jī)數(shù)q，如果q小于0.5，則按照式(8)進(jìn)行更新;否則，仍采用式(7)對個(gè)體的位置進(jìn)行更新.

式中:xj仍然表示個(gè)體j在整個(gè)種群更新之前的位置，x'i表示的是第i個(gè)個(gè)體朝著前j－1個(gè)體中比自己亮的個(gè)體更新之后的新位置，x″i表示x'i朝著比自己亮的個(gè)體j更新之后的位置，rij代表個(gè)體i和個(gè)體j之間的距離，β0e－γr2ij表示個(gè)體 j對個(gè)體 i的吸引力.可以看出，式(8)是實(shí)時(shí)更新的，式(7)僅僅依賴于整個(gè)種群移動(dòng)之前的個(gè)體位置.這樣的飛行更新方式能夠增加飛行的隨機(jī)性，有利于保持種群的多樣性，增大種群搜索空間.

為了加速種群的收斂，本文還提出了一種α的更新方式，使得α隨著迭代次數(shù)逐漸減小，更新公式為

式中:α0選用0.9，t為迭代次數(shù).

對于一個(gè)調(diào)度序列而言，目前主要有3種產(chǎn)生新序列的方法:插入、交換和逆序［6］.其中，插入方法被證明為最適合產(chǎn)生一個(gè)新序列的方法.為了加強(qiáng)螢火蟲算法的局部搜索能力，本文引入了一個(gè)局部搜索算法.局部搜索算法可以描述如下［7］:

2)i=i+1，如果 i＞n，則 i=i－n.

3)把πr賦給中間序列U，把序列U中的第i個(gè)作業(yè)從U中去除，將插入U(xiǎn)中所有可以插入的位置，選取其中最好的調(diào)度序列πbest.

4)分別求解序列πbest和序列U的最小完工時(shí)間 f(πbest)和 f(U)，如果 f(πbest)＜f(U)，則 U=πbest，j=0;否則 j=j+1.

5)如果 j≤n，轉(zhuǎn)步驟2);否則，算法結(jié)束，πr=U.

在這個(gè)算法中，i和j用來控制循環(huán)次數(shù)，沒有實(shí)際意義，n是作業(yè)的數(shù)目，也是解的維數(shù).

這種局部搜索算法的好處在于:首先，局部搜索策略并沒有直接對所選序列進(jìn)行修改，而是應(yīng)用于一個(gè)中間序列U，避免算法陷入局部最優(yōu);其次，在每次搜索過程中，只有找到更好的解時(shí)，才對中間序列進(jìn)行更新，有利于算法逐步向更優(yōu)的解靠近.因此，局部搜索算法在一定程度上加強(qiáng)了螢火蟲算法的局部搜索能力.

改進(jìn)后的螢火蟲算法和原算法相比，初始化部分使得算法有一個(gè)較好的搜索域，局部搜索算法又進(jìn)一步提高了算法的搜索性能.改進(jìn)后的螢火蟲算法求解阻塞流水線調(diào)度問題的步驟如下:

1)初始化種群，包括迭代次數(shù)t=0、最大迭代次數(shù)tmax、隨機(jī)參數(shù) α0、個(gè)體吸引力 β0、介質(zhì)吸收率γ、局部搜索概率p.

2)按照式(1)～(5)計(jì)算每個(gè)個(gè)體的最小完工時(shí)間.

3)螢火蟲算法.

①更新α;

②對當(dāng)前個(gè)體，如果有比自己更亮的個(gè)體，則按照改進(jìn)后的更新方式，利用式(7)或(8)對當(dāng)前個(gè)體的位置進(jìn)行更新;否則，采用萊維飛行對個(gè)體位置進(jìn)行更新.

4)按照式(1)～(5)計(jì)算每個(gè)個(gè)體的最小完工時(shí)間.

5)系統(tǒng)產(chǎn)生一個(gè)隨機(jī)數(shù)，如果這個(gè)隨機(jī)數(shù)小于局部搜索概率p，則對種群個(gè)體進(jìn)行局部搜索，并更新種群.

6)t=t+1，如果t≥tmax或算法達(dá)到其他標(biāo)準(zhǔn)，則算法終止;否則，轉(zhuǎn)步驟3).

4 仿真實(shí)驗(yàn)

實(shí)驗(yàn)所用PC機(jī)的處理器為AMD Athlon64 X2 3600+1.91 GHz，內(nèi)存為 960 MB，編程工具采用Matlab 7.0.

4.1 數(shù)據(jù)集

本文采用著名的Taillard數(shù)據(jù)集作為測試實(shí)例，該數(shù)據(jù)集包含12個(gè)子集，每個(gè)子集包含10個(gè)測試實(shí)例.為了檢驗(yàn)算法的有效性，從這些子集中選取了部分具有代表性的實(shí)例作為測試數(shù)據(jù)，所選實(shí)例涵蓋了從20個(gè)作業(yè)5臺機(jī)器到200個(gè)作業(yè)10臺機(jī)器不同難度的測試實(shí)例，具有很好的代表性.所選實(shí)例的規(guī)模如表3所示.例如在Ta04實(shí)例中，20×5表示20個(gè)作業(yè)在5臺機(jī)器上運(yùn)行.

表3 實(shí)例規(guī)模Table 3 The size of instances

4.2 實(shí)驗(yàn)結(jié)果及分析

實(shí)驗(yàn)中，種群大小為10，最大迭代次數(shù)tmax為100，α0、β0、γ 的設(shè)置參考了螢火蟲算法相關(guān)文獻(xiàn)［9，13-14］中的參數(shù)設(shè)置，α0設(shè)置為 0.9，β0設(shè)置為1.0，γ 設(shè)置為 0.9，局部搜索概率 p 設(shè)置為 0.2.對于前6個(gè)實(shí)例，每個(gè)實(shí)例進(jìn)行10次獨(dú)立實(shí)驗(yàn);對于后4個(gè)實(shí)例，由于數(shù)據(jù)量較大，每個(gè)個(gè)體進(jìn)行5次獨(dú)立實(shí)驗(yàn).為了測試改進(jìn)后的螢火蟲算法在阻塞流水線調(diào)度問題中的性能，還對同等條件下的未改進(jìn)的螢火蟲算法和標(biāo)準(zhǔn)的粒子群算法進(jìn)行了測試.表4為未改進(jìn)的螢火蟲算法的測試結(jié)果，表5為標(biāo)準(zhǔn)粒子群算法的測試結(jié)果，改進(jìn)的螢火蟲算法的測試結(jié)果列于表6中.其中，在標(biāo)準(zhǔn)的粒子群算法中，2個(gè)學(xué)習(xí)因子c1和c2取值為2，慣性權(quán)重 ω設(shè)置為 0.7.

由表4、5可以看出，無論是最小值、最大值，還是平均值，螢火蟲算法的求解結(jié)果普遍優(yōu)于標(biāo)準(zhǔn)粒子群算法.對比表4和表6，可以發(fā)現(xiàn)，改進(jìn)的螢火蟲算法在求解效果上要遠(yuǎn)遠(yuǎn)優(yōu)于基本的螢火蟲算法，而且求解結(jié)果更加穩(wěn)定.綜合表4～6，改進(jìn)后的螢火蟲算法的求解效果明顯優(yōu)于基本的螢火蟲算法和標(biāo)準(zhǔn)的粒子群算法.并且隨著種群的增大，這種差距更加明顯，充分體現(xiàn)了算法的有效性，而且新算法的求解效果更加穩(wěn)定.

表4 螢火蟲算法測試結(jié)果Table 4 The experiment results of firefly algorithm

表5 粒子群算法求解結(jié)果Table 5 The experiment results of particle swarm algorithm

表6 改進(jìn)的螢火蟲算法求解結(jié)果Table 6 The experiment results of improved firefly algorithm

5 結(jié)束語

本文提出了一種改進(jìn)的螢火蟲算法，設(shè)計(jì)了雙重初始化方法，引入了NEH啟發(fā)式方法，重新設(shè)計(jì)了算法中個(gè)體位置的更新方式，并引入了萊維飛行來增大種群的搜索域.在求解阻塞流水線調(diào)度問題時(shí)，設(shè)計(jì)了一種將實(shí)數(shù)編碼離散化的機(jī)制，實(shí)現(xiàn)了實(shí)數(shù)編碼算法對離散化問題的求解.此外，本文還引入了一種局部搜索算法來加強(qiáng)算法的局部搜索能力.實(shí)驗(yàn)結(jié)果表明，改進(jìn)后的螢火蟲算法在求解阻塞流水線調(diào)度問題時(shí)，性能有了明顯提高，而且隨著問題規(guī)模的增大，這種提高更加明顯，體現(xiàn)了算法的有效性和魯棒性.

由于阻塞流水線調(diào)度問題具有很重要的實(shí)際應(yīng)用價(jià)值，因此將來的工作會(huì)考慮把其他優(yōu)秀的算法引入到這個(gè)問題中進(jìn)行求解.另外，由于元啟發(fā)式算法普遍存在計(jì)算量大的問題，將來的工作還應(yīng)該考慮如何提高求解效率.

［1］ALLAHYERDI A，NG C T，CHENG T C E，et al.A survey of scheduling problems with setup times or costs［J］.European Journal of Operational Research，2008，187(3):985-1032.

［2］MCCORMICK S T，PINEDO M L，SHENKER S，et al.Sequencing in an assembly line with blocking to minimize cycle time［J］.Operations Research，1989，37(6):925-935.

［3］RONCONI D P.A note on constructive heuristics for the flowshop problem with blocking［J］.International Journal of Production Economics，2004，87(1):39-48.

［4］CARAFFA V，IANES S，BAGCHI T P，et al.Minimizing makespan in a blocking flowshop using genetic algorithms［J］.International Journal of Production Economics，2001，70(2):101-115.

［5］RONCONI D P.A branch-and-bound algorithm to minimize the makespan in a flowshop with blocking［J］.Annals of Operations Research，2005，138(1):53-65.

［6］GRABOWSKI J，PEMPERA J.The permutation flow shop problem with blocking.A tabu search approach［J］.Omega，2007，35(3):302-311.

［7］WANG Ling，PAN Quanke，SUGANTHAN P N，et al.A novel hybrid discrete differential evolution algorithm for blocking flow shop scheduling problems［J］.Computers ＆ Operations Research，2010，37(3):509-520.

［8］YANG Xinshe.Nature-inspired metaheuristic algorithms［M］.Frome，UK:Luniver Press，2008:81-96.

［9］YANG Xinshe.Firefly algorithms for multimodal optimization［C］//Proceedings of the 5th International Conference on Stochastic Algorithms:Foundations and Applications.Berlin/Heidelberg，Germany:Springer-Verlag，2009:169-178.

［10］NAWAZ M，ENSCORE E E J，HAM I.A heuristic algorithm for the m-machine，n-job flow shop sequencing problem［J］.Omega，1983，11(1):91-95.

［11］BROWN C T，LIEBOVITCH L S，GLENDON R.Lévy flights in Dobe Ju/＇hoansi foraging patterns［J］.Human Ecology，2007，35(1):129-138.

［12］PAVLYUKEVICH I.Lévy flights，non-local search and simulated annealing［J］.Journal of Computational Physics，2007，226(2):1830-1844.

［13］YANG Xinshe.Firefly algorithm，Lévy flights and global optimization［C］//Research and Development in Intelligent Systems XXVI.London，UK:Springer，2010:209-218.

［14］YANG Xinshe.Firefly algorithm，stochastic test functions and design optimization［J］.International Journal of Bio-Inspired Computation，2010，2(2):78-84.