[發(fā)明專利]基于可變時間窗實施兩級混合優(yōu)化批處理調(diào)度的方法

有效

• 申請?zhí)枺?/td>: 201210564217.6
• 申請日: 2012-12-21
• 公開（公告）號: CN103105837A
• 公開（公告）日: 2013-05-15
• 發(fā)明（設計）人: 賈文友;江志斌;李友
• 申請（專利權）人: 上海交通大學
• 主分類號: G05B19/418
• 分類號: G05B19/418
• 代理公司: 上海漢聲知識產(chǎn)權代理有限公司 31236
• 代理人: 郭國中

所屬技術領域

本發(fā)明涉及批處理生產(chǎn)過程調(diào)度的控制方法，尤其是指一種基于可變時間窗實施兩級混合優(yōu)化批處理調(diào)度的方法。

背景技術

在半導體芯片制造中，爐管區(qū)等批處理機調(diào)度是調(diào)度與控制中的一個典型的NP-hard問題，它制約著半導體制造系統(tǒng)的整體績效，開展批處理機處的合理調(diào)度控制研究對改善半導體芯片生產(chǎn)線的性能具有重要意義。

目前，對于批處理生產(chǎn)過程調(diào)度，存在調(diào)度的精度和調(diào)度算法的運行時間矛盾，如啟發(fā)式算法可解大規(guī)模NP-hard問題，能在合理時間內(nèi)獲得可行解，但解的精度有時很難達到要求；線性整數(shù)數(shù)學精確建模求解方法在求解大規(guī)模NP-hard問題，由于CPU運行時間限制，在一定限制時間得不到最優(yōu)解；另外半導體行業(yè)的多重入特性進一步增加批處理生產(chǎn)過程調(diào)度的難度。

發(fā)明內(nèi)容

針對上述現(xiàn)有技術中存在的技術問題，本發(fā)明提供一種基于可變時間窗實施兩級混合優(yōu)化批處理調(diào)度的方法，克服了多重入半導體批處理機生產(chǎn)過程調(diào)度的要么精度低，要么調(diào)度算法的運行時間長等的不足，以及多重入特性增加調(diào)度難度的問題。

本發(fā)明具體解決其技術問題所采用的技術方案如下：

一種基于可變時間窗實施兩級混合優(yōu)化批處理調(diào)度的方法，利用復雜問題的分解法原則，即基于時間序列模型分解，分解成若干個連續(xù)的可變時間窗，基于滾動時域策略實時控制，在每個時間窗內(nèi)以最小總的加權拖延時間為目標，實施兩階段混合優(yōu)化控制。這里“時間窗”定義為相鄰兩次空閑可用批處理機的裝載時間間隔為一個時間窗，因平行批處理機出現(xiàn)空閑時間不固定，導致被裝載的時刻不固定，所以時間窗的長度不是定值，即是可變時間窗。第一階段基于多規(guī)則組合自適應原理建立實時控制平臺，采用可變時間窗下的滾動時域法獲得被加工的工件批具體的工序加工時間、工序剩余時間、產(chǎn)品交貨期，產(chǎn)品批的優(yōu)先級以及按照一定的組批原則形成的批組合等實時參數(shù)，形成數(shù)據(jù)庫鏈接到第二階段；第二階段基于松弛方法，建立松弛化的線性整數(shù)數(shù)學模型，通過.NET和ILOG?CPLEX商業(yè)化軟件聯(lián)合引擎求解，實現(xiàn)獲得批排序的優(yōu)化順序，并將結果反饋給第一階段，以便第一階段裝載優(yōu)先級最高的批到空閑可用的批處理機上。兩個階段分別解決批調(diào)度問題中如何組批和如何將所組批排序，多重入性質(zhì)被考慮，通過可變時間窗下的滾動時域法，滿足被加工的工件批的動態(tài)實時調(diào)度特性。

第一階段可獲得被加工的工件批具體的工序加工時間、工序剩余時間、產(chǎn)品交貨期，產(chǎn)品批的優(yōu)先級以及按照一定的組批原則形成的批組合等實時參數(shù)，形成數(shù)據(jù)庫，提供給第二階段進行求解，其循環(huán)執(zhí)行的具體步驟：

步驟1，上一個空閑可用的批處理機剛被裝載完畢，初始化時間窗，第一階段策略開始運行；

步驟2，獲取被調(diào)度批處理機運行狀態(tài)，獲取被調(diào)度批處理機前緩沖器里的工件數(shù)量和所屬產(chǎn)品族信息；

步驟3，當有一臺批處理機空閑可用，產(chǎn)生觸發(fā)事件，該空閑可用批處理機處于等待，第一階段的實時控制平臺立即組批，輸出當前被加工的工件批具體的工序加工時間、工序剩余時間、產(chǎn)品交貨期，產(chǎn)品批的優(yōu)先級，并建立數(shù)據(jù)庫，提供給第二階段；當?shù)诙A段將所有待加工批中優(yōu)先級最高的批反饋給第一階段時，第一階段將該批裝載到等待的空閑可用批處理機上，一個時間窗調(diào)度完畢；

步驟4，終止條件是總計劃生產(chǎn)過程調(diào)度周期完畢，如果滿足終止條件，立即停止，否則迭代返回到步驟1。

建立松弛化的線性整數(shù)數(shù)學模型并求解具體步驟：

步驟1，建立外部編程語言.NET與ILOG?CPLEX商業(yè)化軟件的連接，在外部編程語言引入ILOG.CPLEX.dll和ILOG.Concert.dll兩個空間；

步驟2，在最小總的加權拖延時間為目標下，建立基于松弛的線性混合整數(shù)數(shù)學模型：

目標