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

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

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

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