求解置換流水車間調(diào)度問題的混合元啟發(fā)式方法

求解置換流水車間調(diào)度問題的混合元啟發(fā)式方法

1機(jī)器的化調(diào)度流動工作流的調(diào)度問題通?？梢悦枋鰹閚個(gè)操作應(yīng)該在m機(jī)器上加工。每個(gè)操作都有m個(gè)操作序列，每個(gè)操作順序應(yīng)該在不同的機(jī)器上加工。n個(gè)操作順序是每個(gè)機(jī)器上最優(yōu)的加工順序，以滿足特定的性能指標(biāo)。為了解決典型的流機(jī)工作流的問題，指針是希望每個(gè)機(jī)器上所有工作的加工順序是相同的。pfsp的技術(shù)限制相對簡單，但已證明是nip的問題。在這項(xiàng)工作中，我們主要研究了pfsp的最大生產(chǎn)時(shí)間。最大生產(chǎn)時(shí)間是生產(chǎn)計(jì)劃中最常用的性能測量指標(biāo)之一。最大生產(chǎn)時(shí)間越短，產(chǎn)品的總生產(chǎn)量越低，生產(chǎn)能力越高。換句話說，最小最小值和最大生產(chǎn)能力意味著最大生產(chǎn)能力。因此，優(yōu)化布局可以有效提高公司的生產(chǎn)效率和資源利用率。對于n個(gè)操作，m機(jī)器pfsp和j={j.j.1、2、…n}、ti和j是j在機(jī)器i上的加工時(shí)間（j.1、2、…n）。對于i和c（i，j），這意味著j在機(jī)器上的最大工作時(shí)間可以通過以下數(shù)學(xué)公式來表達(dá)。粒子群算法(ParticlesSwarmOptimization,PSO)是由Kennedy和Eberhart博士于1995年提出的一種基于群體的進(jìn)化算法,該算法主要模擬鳥群的行為.粒子群算法通用性強(qiáng),易于實(shí)現(xiàn),因此被廣泛應(yīng)用于不同的領(lǐng)域.相對于其他的一些算法,如遺傳算法(GeneticAlgorithm,GA)、模擬退火算法(SimulatedAnnealing,SA)等,應(yīng)用PSO求解車間調(diào)度問題的研究還相對較少.文獻(xiàn)最先對于PFSP問題提出了一種基于可變鄰域搜索(VariableNeighborhoodSearch,VNS)的混合粒子群算法PSOVNS,該算法采用基于隨機(jī)鍵的規(guī)則來構(gòu)造粒子的位置到作業(yè)排序之間的映射關(guān)系.該算法后來被用于求解最小化最大完成和總的流經(jīng)時(shí)間.Liao等人擴(kuò)展傳統(tǒng)的二元離散粒子群算法用于求解流水車間調(diào)度問題,并且和遺傳算法進(jìn)行了對比,實(shí)驗(yàn)證明要優(yōu)于遺傳算法.Lian等人提出了最小化最大完成時(shí)間的PFSP的一種基于PSO思想的進(jìn)化算法,他們直接利用GA的交叉和變異操作作為PSO算法中粒子速度和位置的更新操作.高亮等人提出新的基于粒子群的調(diào)度算法,該算法同樣采用遺傳操作,主要利用記憶庫來實(shí)現(xiàn)信息共享機(jī)制,降低了算法局部收斂的概率.文獻(xiàn)中提出的粒子群算法的思想和文獻(xiàn)一樣,但是通過對部分粒子的位置和速度進(jìn)行變異來降低早熟收斂現(xiàn)象發(fā)生的可能.文獻(xiàn)提出了一種改進(jìn)的離散粒子群算法,并將其用于車間調(diào)度問題.本文提出了一種混合的元啟發(fā)式方法HDCPSO用于求解置換流水車間調(diào)度問題中的最小化最大完成時(shí)間問題.該算法結(jié)合粒子群算法以及迭代貪心算法(IterativeGreedy,IG),利用IG算法中的作業(yè)毀壞(Destruction)和構(gòu)造(Construction)操作(本文簡稱DC操作)來對粒子(為了方便,本文不區(qū)分粒子和個(gè)體的概念)進(jìn)行變異,降低群體發(fā)生早熟的可能.并且引入了個(gè)體徘徊概念,用來控制個(gè)體變異.此外,通過基于插入的鄰域搜索來強(qiáng)化個(gè)體的局部搜索能力.最后,本文還提出了群體的重新初始化機(jī)制來進(jìn)一步避免群體的早熟收斂的發(fā)生.2作業(yè)排列/作業(yè)排列Ruiz等人提出了一種簡單的迭代貪心算法(IteratedGreedyAlgorithm,IG)用于流水車間調(diào)度問題,該算法利用NEH的基本原理,通過對作業(yè)排列的DC操作來獲得更好的解.給定一個(gè)作業(yè)排列π,IG算法首先對作業(yè)排列進(jìn)行毀壞處理,即隨機(jī)地、無替換地從作業(yè)排列π中刪除若干作業(yè),然后將刪除的作業(yè)依次重新插回到可能的最好的位置,這樣就重新獲得了一個(gè)完整的作業(yè)排列,然后與毀壞前的作業(yè)排列進(jìn)行比較,將滿足條件的作業(yè)排列作為當(dāng)前解,進(jìn)入下一輪迭代.3算法的基本部分在本節(jié)中,我們將粒子群算法與IG算法相結(jié)合,提出一種混合的粒子群算法HDCPSO.HDCPSO算法的基本框架如圖1所示.圖1描述了算法的基本組成部分,我們將在下面的幾個(gè)小節(jié)中具體介紹這些組成部分.3.1發(fā)式構(gòu)造型算法NEH作為一種求解PFSP問題的啟發(fā)式構(gòu)造型算法,經(jīng)常被用于群體的初始化,以實(shí)現(xiàn)快速收斂.本文中通過NEH來構(gòu)造一個(gè)粒子,剩下的粒子隨機(jī)生成.3.2速度更新傳統(tǒng)的粒子群速度和位置更新策略無法直接應(yīng)用于離散問題,但是可以通過交叉操作來實(shí)現(xiàn)相同的目的,本文算法中粒子的位置和速度直接表示成作業(yè)排列,速度和位置的更新公式如下:其中t表示迭代次數(shù),?表示交叉操作符.從上面公式可以看出,粒子的行為依然受到粒子速度、當(dāng)前個(gè)體最優(yōu)和當(dāng)前群體最優(yōu)(以下簡稱為個(gè)體最優(yōu)和群體最優(yōu))的影響,并通過信息的共享向最優(yōu)解方向前進(jìn).在更新速度時(shí)使用群體最優(yōu)容易導(dǎo)致早熟收斂,因此我們先選擇適應(yīng)度最好的一部分個(gè)體(本文選取5個(gè)),然后從中隨機(jī)選擇一個(gè)作為更新時(shí)使用的群體最優(yōu).3.3rptal交叉方式交叉操作通過交換父代個(gè)體的信息,以期望獲得更好的子代個(gè)體.Pan等人提出一種交叉方式,two-cutPTLcrossover(簡稱PTL).該交叉方式和文獻(xiàn)中的C1交叉方式類似,不同的是將作業(yè)子排列分別復(fù)制到子代個(gè)體的前面或后面.這種交叉方式的好處是即使兩個(gè)父代個(gè)體的作業(yè)排列是一樣的,交叉后也可以得到兩個(gè)不同的子代個(gè)體.受此啟發(fā),本文提出了一種隨機(jī)放置的交叉方式,稱為two-cutRandomPTLcrossover(簡稱RPTL),即兩個(gè)切點(diǎn)之間的作業(yè)子排列可以放置在子代中的任何位置,只要保證子排列在兩個(gè)子代個(gè)體中的位置對稱即可.兩種交叉方式的區(qū)別見表1.RPTL具備PTL的特點(diǎn),并且避免了PTL由于交叉程度過大而使得子代個(gè)體遠(yuǎn)離更好的區(qū)域,降低收斂速度.當(dāng)隨機(jī)選擇的位置恰好是子代中的第一個(gè)位置或者是最后一個(gè)位置,那么RPTL交叉就轉(zhuǎn)化成PTL交叉,因此可以認(rèn)為RPTL交叉是PTL交叉的一般形式.在實(shí)驗(yàn)中,我們測試了三種交叉方式的影響,即C1交叉、C1-1交叉(RPTL和C1交替執(zhí)行)和C1-2交叉(先執(zhí)行C1交叉,當(dāng)兩個(gè)排列一致時(shí)采用RPTL交叉),發(fā)現(xiàn)C1-2交叉在求解速度上接近C1交叉,并且求解質(zhì)量優(yōu)于其他兩種交叉方式,因此我們認(rèn)為RPTL交叉策略可以彌補(bǔ)C1的不足,將兩個(gè)策略結(jié)合起來是行之有效的,并且在后面實(shí)驗(yàn)中采用C1-2交叉方式.3.4關(guān)于個(gè)體-代碼算法-ig算法變異操作是通過對當(dāng)前個(gè)體的擾動來產(chǎn)生一個(gè)新的個(gè)體,從而避免早熟收斂.如果一個(gè)粒子的個(gè)體最優(yōu)連續(xù)若干代都沒有發(fā)生變化,即無法移動到更好的位置而發(fā)生停滯,我們稱之為個(gè)體徘徊.定義1個(gè)體徘徊:對于一個(gè)粒子,如果連續(xù)p代,其個(gè)體最優(yōu)都沒有發(fā)生變化,則稱為個(gè)體徘徊.我們將前面介紹的IG算法與粒子群算法結(jié)合起來,通過IG算法中的DC操作對粒子進(jìn)行變異操作.IG算法與迭代的局部搜索非常相似,只是IG是一種迭代的構(gòu)造啟發(fā)式算法,利用DC操作尋求新的個(gè)體最優(yōu)解,減少個(gè)體陷入局部極值的概率.由于相對于簡單的變異操作,DC操作需要更長的計(jì)算時(shí)間,因此我們只針對發(fā)生個(gè)體徘徊現(xiàn)象的粒子的個(gè)體最優(yōu)進(jìn)行變異.對每個(gè)個(gè)體,利用一個(gè)計(jì)數(shù)器來記錄個(gè)體最優(yōu)停滯的代數(shù),在初始化階段,每個(gè)粒子的計(jì)數(shù)器都為0.個(gè)體每停滯一代,則計(jì)數(shù)器加1,否則重新計(jì)數(shù).如果達(dá)到閾值p,則對個(gè)體最優(yōu)進(jìn)行變異操作,然后重新開始計(jì)數(shù).3.5基于引用的局部搜索大量的研究發(fā)現(xiàn),粒子群算法的局部搜索能力較弱,尤其在進(jìn)化后期,進(jìn)化變得緩慢,甚至停止進(jìn)化發(fā)生早熟收斂.文獻(xiàn)采用插入鄰域搜索,對每個(gè)個(gè)體的鄰域進(jìn)行搜索,提高了算法的收斂速度和精度.文獻(xiàn)中采用了一種基于引用的插入模式(Referencedinsertionscheme)來進(jìn)行局部搜索,利用一個(gè)引用作業(yè)排列(通過NEH獲得)來引導(dǎo)局部搜索.本文中采用這種方式,不同的是我們將適應(yīng)度最差的粒子對應(yīng)的作業(yè)排列作為引用作業(yè)排列,這樣可以使得每次局部搜索時(shí)所采用的引用作業(yè)排列都有可能不同.由于局部搜索會導(dǎo)致計(jì)算時(shí)間的增加,因此,我們只對當(dāng)前全局最優(yōu)個(gè)體采用插入鄰域搜索.3.6重新初始化機(jī)制隨著群體的不斷進(jìn)化,群體多樣性不斷降低,使得群體容易停滯在局部最優(yōu),本文采取重新初始化機(jī)制來克服該問題.當(dāng)群體最優(yōu)的停滯代數(shù)達(dá)到指定的閾值時(shí),執(zhí)行重新初始化操作,增強(qiáng)群體多樣性.重新初始化過程分為刪減階段和增添階段.3.6.1適應(yīng)度較差的個(gè)體為了不影響算法的收斂速度,不需要對整個(gè)群體全部進(jìn)行刪減,而是從個(gè)體適應(yīng)度和群體多樣性兩個(gè)方面來考慮,這樣即保證最好的個(gè)體不被刪除,同時(shí)也刪除了一部分相似度比較接近的個(gè)體,以維護(hù)整個(gè)群體的多樣性,避免陷入局部極值.第一步:對整個(gè)群體,根據(jù)個(gè)體的適應(yīng)度優(yōu)劣,我們先保留適應(yīng)度最好的前20%的個(gè)體;第二步:刪除適應(yīng)度最差的30%;第三步:刪掉多樣性相對較差的20%.在第三步操作中,首先從保留下來的適應(yīng)度最好的那20%中隨機(jī)選擇一個(gè)作為基準(zhǔn)個(gè)體,然后從前兩步中未被處理的那50%個(gè)體中隨機(jī)選擇一些(本文中取2)和基準(zhǔn)個(gè)體進(jìn)行相似度比較,刪掉和基準(zhǔn)個(gè)體之間相似度較大的那個(gè)個(gè)體,重復(fù)執(zhí)行該過程,直至總?cè)后w數(shù)中的20%被刪掉.定義2個(gè)體相似度:對于兩個(gè)個(gè)體a和b,其作業(yè)排列分別為πa和πb,那么這兩個(gè)個(gè)體的相似度定義為兩個(gè)個(gè)體作業(yè)排列間的Hamming距離,記作Ham(πa,πb).其中sign是一個(gè)符號函數(shù).3.6.2粒子的檢測策略在增添階段,我們采用分散搜索(ScatterSearch,SS)中的群體多樣性生成策略和隨機(jī)生成兩種方式來重新初始化被刪減的粒子.通過分散搜索中的群體多樣性生成策略產(chǎn)生20%個(gè)體(如果生成個(gè)體數(shù)不足20%,則在前20%適應(yīng)度較高的個(gè)體中隨機(jī)選擇一個(gè),然后執(zhí)行Shift插入操作來補(bǔ)足),隨機(jī)產(chǎn)生30%的個(gè)體.3.7hdcpss算法描述基于前面幾部分的介紹,本文提出的HDCPSO算法的偽代碼描述如下:4實(shí)驗(yàn)結(jié)果和分析在本節(jié)中,首先分析了不同的參數(shù)設(shè)置對算法性能的影響,由于本文中主要使用兩個(gè)參數(shù),即DC變異時(shí)需要?dú)牡淖鳂I(yè)個(gè)數(shù)和個(gè)體徘徊代數(shù),因此我們主要通過實(shí)驗(yàn)對個(gè)體徘徊代數(shù)進(jìn)行分析.然后,在不同規(guī)模的Taillard數(shù)據(jù)集上對本文算法進(jìn)行了測試,并和NEH以及NPSO算法做了對比.最后和Kuo等人最新提出的混合粒子群算法HPSO進(jìn)行了比較.4.1參數(shù)配置在本文算法中,關(guān)鍵的參數(shù)主要有兩個(gè),一是當(dāng)個(gè)體最優(yōu)執(zhí)行DC操作時(shí)毀壞作業(yè)的個(gè)數(shù);二是個(gè)體徘徊代數(shù),下面我們分別來討論這兩個(gè)參數(shù).4.1.1不同損壞作業(yè)個(gè)數(shù)對算法的影響在文獻(xiàn)中,Ruiz等人通過大量的實(shí)驗(yàn)來測試不同毀壞作業(yè)個(gè)數(shù)對算法的影響,并最終得出毀壞個(gè)數(shù)為4時(shí)相對性能最好.因此,本文直接采用文獻(xiàn)中的結(jié)果.4.1.2個(gè)體嘴唇數(shù)本小節(jié)我們來分析一下個(gè)體徘徊代數(shù)對算法的影響.為了測試徘徊代數(shù)的影響,我們將個(gè)體徘徊代數(shù)P分別設(shè)置為5,10,20,30,40,50,群體最優(yōu)停滯代數(shù)設(shè)置為50,毀壞作業(yè)個(gè)數(shù)為4,群體規(guī)模設(shè)置為60,最大迭代次數(shù)為500代,問題實(shí)例采用TA021、TA051和TA081.對于每個(gè)測試,算法獨(dú)立執(zhí)行20次.每次測試所得到的最優(yōu)解與已知最優(yōu)解的平均相對偏離度(AverageRelativePercentageDeviation,ARPD)定義如下:其中L表示算法執(zhí)行的次數(shù),Soli表示算法在第i次執(zhí)行時(shí)獲得的最優(yōu)解,BKS表示已知的問題最優(yōu)解,因此ARPD能反映出算法得到的最優(yōu)解與真實(shí)最優(yōu)解之間的相對偏離程度.徘徊代數(shù)對ARPD的影響見表2.從表2中可以看出,對于所有問題,徘徊代數(shù)為20時(shí)都得到了較好的結(jié)果,因此本文算法中個(gè)體徘徊代數(shù)設(shè)置為20.4.2結(jié)果4.2.1算法的魯棒性首先,我們將HDCPSO算法與NEH以及NPSO算法進(jìn)行對比,NPSO算法采用C1交叉,變異方式為移位變異(M3).HDCPSO算法采用C1-2交叉,毀壞作業(yè)個(gè)數(shù)為4,個(gè)體徘徊代數(shù)為20,群體最優(yōu)停滯代數(shù)為50,群體大小為60,最大迭代次數(shù)為500.初始化時(shí)均采用由NEH生成一個(gè)個(gè)體,而剩余的隨機(jī)生成.測試問題的大小由20×5到100×20,每個(gè)測試實(shí)例執(zhí)行10次.三個(gè)算法均采用C#語言實(shí)現(xiàn),機(jī)器配置為windowsXP系統(tǒng),處理器為Pentium4,2.8GHz,內(nèi)存大小為1G.表3～5列出了作業(yè)個(gè)數(shù)為20、50和100時(shí)算法的對比結(jié)果.從表3～5中,我們可以看出,對于9個(gè)不同規(guī)模的測試問題,本文提出的HDCPSO算法,獲得的結(jié)果(最優(yōu)解、最差解和平均值)均優(yōu)于NEH和NPSO算法.對于小規(guī)模的問題(作業(yè)數(shù)為20),除了在TA030問題實(shí)例上,HDCPSO算法都能夠獲得和已知最優(yōu)解相同的結(jié)果,而NPSO只在實(shí)例TA001上獲得了最優(yōu)解.對于中等及大規(guī)模問題上,當(dāng)機(jī)器數(shù)量比較少時(shí),HDCPSO算法對于所有的測試問題實(shí)例都獲得了最有解,而NPSO算法只針對TA061實(shí)例獲得了最優(yōu)解.此外,當(dāng)機(jī)器數(shù)量等于5時(shí),HDCPSO算法對于大多數(shù)問題實(shí)例得到的結(jié)果均值和最優(yōu)解一致,而對于其他問題,其均值也非常接近最優(yōu)解,因此我們說HDCPSO算法具有更好的魯棒性,尤其是當(dāng)機(jī)器數(shù)量較少的時(shí)候.表6列出了三個(gè)算法對于不同規(guī)模的測試問題的平均相對偏離度的對比,對于所有問題,HDCPSO的ARPD都是最小的.因此我們說,HDCPSO求得的解的質(zhì)量要優(yōu)于NPSO算法,并且更不容易陷入局部極值.為了能夠更直觀的進(jìn)行HDCPSO和NPSO算法的比較,我們給出了兩種算法對于不同問題的最優(yōu)解的均值進(jìn)化曲線的對比,由于篇幅有限,我們只給出了問題TA31和TA51的進(jìn)化曲線.以圖2(a)為例,兩個(gè)算法在執(zhí)行的初始階段,收斂速度接近,但是當(dāng)進(jìn)化到大于20代左右,NPSO算法就已經(jīng)停止進(jìn)化,發(fā)生早熟收斂現(xiàn)象.而HDCPSO算法盡管也出現(xiàn)了進(jìn)化停滯現(xiàn)象,但是由于采用DC變異和局部搜索策略,降低了早熟收斂發(fā)生的可能,從而在大約300代收斂到全局最優(yōu)解.圖2(b)的情況與圖2(a)類似,在此不再贅述.因此,我們可以看出HDCPSO算法的收斂速度快于NPSO算法,并且解的質(zhì)量也明顯優(yōu)于NPSO算法.4.2.2在群體大小和最大迭代次數(shù)上的對比在本小節(jié)中,我們將HDCPSO算法與Kuo等人最新提出的混合粒子群算法HPSO進(jìn)行比較.HPSO算法采用基于隨機(jī)鍵的實(shí)數(shù)編碼形式,并且通過個(gè)體強(qiáng)化策略來試圖找到更好的解.我們將HDCPSO算法重新執(zhí)行,對每個(gè)測試問題實(shí)例獨(dú)立執(zhí)行10次,群體大小和最大迭代次數(shù)與文獻(xiàn)一致,兩個(gè)算法的對比結(jié)果見表7.從對比結(jié)果中,我們可以看出,對于問題實(shí)例TA001、TA031和TA061,由于這些問題實(shí)例相對簡單(機(jī)器數(shù)遠(yuǎn)小于作業(yè)數(shù)量),因此兩個(gè)算法在每次執(zhí)行時(shí)都能夠找到問題最優(yōu)解.而對于其他問題,HDCPSO算法無論是最小