基于列生成對可重入混合流水線的調度.pdf

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

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

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