基于目標(biāo)增量的無(wú)等待流水調(diào)度算法研究.pdf

1、無(wú)等待流水調(diào)度(NWFS)是一類重要的約束流水調(diào)度問(wèn)題，它要求任務(wù)的加工從開始到結(jié)束必須連續(xù)進(jìn)行，不能出現(xiàn)等待，即任務(wù)在給定機(jī)器上的開始時(shí)間必須延遲以滿足該工序的完成時(shí)間與下一個(gè)工序在下一臺(tái)機(jī)器上的開始時(shí)間相符合。該問(wèn)題廣泛存在于冶金、塑料、化工和食品加工等行業(yè)，高級(jí)制造環(huán)境如JIT、FMS以及機(jī)器之間具有高度協(xié)作的加工環(huán)境，通常也被模型化為無(wú)等待調(diào)度。無(wú)等待調(diào)度的優(yōu)化目標(biāo)可模型化為相鄰任務(wù)間“距離”或“總空閑時(shí)間”的加權(quán)和，通過(guò)分析發(fā)

2、現(xiàn)這些“距離”或“總空閑時(shí)間”只與相關(guān)任務(wù)的加工時(shí)間有關(guān)，獨(dú)立于調(diào)度序列中的其他任務(wù)，故可事先確定，算法搜索過(guò)程中產(chǎn)生的調(diào)度是否更優(yōu)可以通過(guò)計(jì)算所有變化點(diǎn)的目標(biāo)增量和來(lái)評(píng)價(jià)，而不需要計(jì)算整個(gè)調(diào)度中所有任務(wù)的時(shí)間參數(shù)，可大大降低算法的時(shí)間復(fù)雜度?；谠摕o(wú)等待流水調(diào)度特性，通過(guò)對(duì)該問(wèn)題國(guó)內(nèi)外研究現(xiàn)狀的分析，論文重點(diǎn)圍繞最小化最大完工時(shí)間(Makespan)、最小化總完工時(shí)間(Flowtime)以及最小化二者的雙目標(biāo)無(wú)等待調(diào)度問(wèn)題進(jìn)行深入研究

3、，主要工作和創(chuàng)新點(diǎn)如下： (1)構(gòu)建最大完工時(shí)間和總完工時(shí)間最小化的無(wú)等待調(diào)度模型：根據(jù)最大左移長(zhǎng)度(Tri-L)將一個(gè)任務(wù)的最大完工時(shí)間等價(jià)轉(zhuǎn)化為其前面任務(wù)間距離和，從而將目標(biāo)函數(shù)Flowtime等價(jià)轉(zhuǎn)化為相鄰任務(wù)距離加權(quán)和的形式；根據(jù)最大左移長(zhǎng)度，將最小化Makespan問(wèn)題等價(jià)轉(zhuǎn)化為求解所有機(jī)器上總空閑時(shí)間和最小的問(wèn)題：而Flowtime與Makespan雙目標(biāo)則轉(zhuǎn)化為相鄰任務(wù)的距離加權(quán)和。分析出目標(biāo)函數(shù)值的獨(dú)立性。

4、 (2)提出基于增量的最大完工時(shí)間最小化無(wú)等待調(diào)度混合遺傳算法：根據(jù)問(wèn)題特點(diǎn)分析并推導(dǎo)啟發(fā)式算法插入、刪除、移位和對(duì)換等基本操作的基本最大完工時(shí)間增量性質(zhì)及其擴(kuò)展性質(zhì)；構(gòu)造MBJI、MBJT和MBJS三種基本目標(biāo)增量法；分析了混合算法的基本結(jié)構(gòu)與優(yōu)化策略，設(shè)計(jì)混合遺傳算法IIHG，并將其與求解該問(wèn)題的最有效算法在120個(gè)Benchmark實(shí)例上進(jìn)行了比較，驗(yàn)證了IIHG在性能和效率上的優(yōu)勢(shì)。 (3)提出基于增量的總完工時(shí)間最小

5、化無(wú)等待調(diào)度復(fù)合啟發(fā)式算法：根據(jù)問(wèn)題特點(diǎn)分析并推導(dǎo)啟發(fā)式算法插入、刪除、移位和對(duì)換等基本操作的總完工時(shí)間增量性質(zhì)：構(gòu)造FBJI、FBJT年IIFBJS基本目標(biāo)增量法；將該性質(zhì)推廣到任意一臺(tái)機(jī)器，并構(gòu)造FGBI、FGBT和FGBS通用總完工時(shí)間增量法；設(shè)計(jì)復(fù)合啟發(fā)式算法OICH1和OICH2；實(shí)驗(yàn)結(jié)果表明，OICH1在性能和效率方面均優(yōu)于當(dāng)前最好的啟發(fā)式算法PHlp: OICH2在性能上比OICH1好，但其時(shí)間開銷較大。 (4)提

6、出基于增量的總完工時(shí)間最小化無(wú)等待調(diào)度智能優(yōu)化算法：設(shè)計(jì)基于分段重構(gòu)策略和迭代全局搜索的快速迭代貪婪算法FIG、基于動(dòng)態(tài)選擇策略和唯一性穩(wěn)態(tài)繁殖策略的混合遺傳算法DSHG、以及基于高概率輪轉(zhuǎn)擾動(dòng)的微型進(jìn)化算法MEA等三種智能優(yōu)化方法；實(shí)驗(yàn)結(jié)果表明，F(xiàn)IG在性能上優(yōu)于PHlp和SRTS，略遜于DPSOvnd，在效率上優(yōu)于SRTS和DPSOvnd，比PHlp略差；DSHG在性能上遠(yuǎn)好于PHlp、SRTS和TGA，在效率上優(yōu)于TGA，遜于PH

7、lp和SRTS: MEA算法與目前求解該問(wèn)題最好的算法DPSOvnd相比，在計(jì)算效率相近的情況下其性能更優(yōu)。 (5)提出基于增量的最大完工時(shí)間與總完工時(shí)間雙目標(biāo)最小化無(wú)等待調(diào)度智能優(yōu)化算法：根據(jù)問(wèn)題特點(diǎn)分析并推導(dǎo)啟發(fā)式算法插入、刪除、移位和對(duì)換等基本操作的加權(quán)和目標(biāo)增量性質(zhì)；設(shè)計(jì)混合遺傳算法OIMOGA，并將其與求解該問(wèn)題的最有效算法在30個(gè)Benchmark實(shí)例上進(jìn)行了比較，結(jié)果表明OIMOGA在不同情況下所獲得的最優(yōu)解都充滿