基于列生成對可重入混合流水線的調(diào)度.pdf

1、可重入生產(chǎn)系統(tǒng)作為半導(dǎo)體制造業(yè)中典型的生產(chǎn)系統(tǒng)，自提出以來就成為了研究熱點，并在計算機網(wǎng)絡(luò)、通訊網(wǎng)絡(luò)、鋼管工業(yè)等領(lǐng)域也都發(fā)現(xiàn)具有類似可重入特性的系統(tǒng)，可重入的概念對現(xiàn)代科技有重大影響。不同于傳統(tǒng)流水線和車間作業(yè)，可重入生產(chǎn)系統(tǒng)中工件路徑會發(fā)生多次回流、工藝繁雜、機器利用率高，系統(tǒng)相當(dāng)復(fù)雜，傳統(tǒng)的理論和方法難以適用。
　　可重入混合流水線是一類典型的可重入生產(chǎn)系統(tǒng)，本文以此作為研究對象。調(diào)度問題是可重入生產(chǎn)系統(tǒng)研究領(lǐng)域的一個重要課題

2、，對可重入混合流水線調(diào)度問題的研究具有十分重大的理論和經(jīng)濟意義。目前對可重入混合流水線調(diào)度問題的研究主要集中在建模和求解上，由于其本身的復(fù)雜性，使得無論在建模還是求解方面都有很大的難度，尚未形成一套被證明確定有用的理論和方法，研究尚屬于探索階段。
　　近年來，列生成算法在傳統(tǒng)機器調(diào)度領(lǐng)域有很好表現(xiàn)，但是目前還尚未有研究在應(yīng)用列生成算法時考慮到可重入的約束。本文首次使用列生成算法調(diào)度可重入混合流水線，來探索列生成對解決這類問題的效果

3、。
　　論文針對基本的可重入混合流水線，首先在傳統(tǒng)混合流水線調(diào)度問題的整數(shù)規(guī)劃模型基礎(chǔ)上考慮了可重入約束，以最小化加權(quán)完工時間和為目標函數(shù)，建立了可重入混合流水線的調(diào)度模型。然后通過Dantzig-Wolfe分解法將初始模型轉(zhuǎn)化成包含工件級子問題的集合分割模型，進而構(gòu)造具體的列生成算法來求解。
　　數(shù)值實驗結(jié)果表明，所建立模型合理，基于列生成的求解算法能提供在計算精度和運算效率兩方面都較為滿意的混合流水生產(chǎn)線的可行調(diào)度方案。