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

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

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

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

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

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

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

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