面向多重入製造系統在線調度的單臺設備匹配重調度方法
2023-12-07 01:24:01
專利名稱：面向多重入製造系統在線調度的單臺設備匹配重調度方法
技術領域：
多重入製造系統的在線重調度方法，特別面向微電子製造領域的生產管理技術， 是一種修正式的重調度方法。具體地，本發明涉及一種重調度方法，即局部重調度算法中的 單臺設備匹配重調度(SMUR)算法；這種算法以充分利用設備空閒時間為思想，以提升重調 度決策的有效性與生產線的穩定性。
背景技術：
對於複雜多變的多重入製造系統，許多生產線的擾動因素具有不可預測性，而這 些擾動因素往往會使得原本優化的調度方案不再優化，甚至失去了可行性，這時需要對生 產線進行重新調度，這也就引出了多重入製造系統的重調度問題。所謂重調度，是指當既定生產調度方案在其執行過程中被幹擾時，在既定調度方 案的基礎上生成新的調度方案，以適應當前狀態的過程。目前，國內外的重調度研究主要集中於單臺機器系統、並行機器系統、流水車間和 作業車間、柔性製造單元與系統。研究內容主要包括以下三個方面重調度策略、重調度方 法和重調度評價。重調度策略是根據各種重調度因素，決定何時產生重調度，採用何種重調度方法。 常見的有三種重調度策略周期性重調度策略，事件驅動重調度策略和混合重調度策略。周期性重調度策略以恆定的時間間隔有規律的對設備進行重調度，不考慮事件觸 發。周期性重調度是最普遍的重調度策略，通常是基於管理區間(如，一周或一天或一個班 次)進行的。Church和Uzsoy給出了這種重調度策略詳細的解釋。Kempf提出了一種基於 人工智慧的預先調度方法，該方法每個班次執行一次，給出優化的調度方案。Sabimcuoglu 和Karabuk在柔性製造系統中考慮重調度頻率對系統效能的影響。不同的重調度周期對生 產線的影響很大，如何決定最佳重調度周期是一項困難而重要的工作。事件驅動重調度策略由擾動事件觸發重調度，能夠即時響應動態製造系統中的擾 動事件，修改原調度方案或生成新的調度方案。Vieira等描述了在動態系統中利用分析模 型比較基於隊列長度的事件驅動重調度策略的性能。Bierwirth和Mattfeld研究的重調度 策略，當每個新工件到來時創建一個新的調度。然而，完全的事件響應可能會導致過度的計 算開銷，難以滿足實時性的要求。混合重調度策略將上述兩種重調度策略相結合，在周期性觸發重調度的基礎上， 根據擾動事件對原調度方案的影響有選擇的觸發重調度。Chacon描述了在Sony半導體中 使用的系統，採用周期性重調度策略，並且當非預期事件發生時手工進行重調度。Suwa採用 固定周期重調度策略，同時計算累積任務延遲，當累計任務延遲達到預先設定的臨界值時 開始重調度。混合型重調度既可以避免周期性重調度對非預期事件不敏感的確定，又可以 避免事件驅動型重調度易造成過度頻繁的重調度導致計算量過大的缺點。在採用流水線車間加工的生產系統中，一個傳送系統沿著工作檯運送WIP，在每個 工作檯處，完成WIP的一道不同工序。從理論上，WIP在從頭到尾加工行進期間中訪問各個工作檯一次。半導體生產線與使用流水線車間加工的大多數生產系統不同。在半導體生產 線中，WIP在加工行進過程中有可能數次訪問同一個工作檯，WIP要經歷數次清洗、氧化、沉 積、噴塗金屬、蝕刻、離子注入及脫膜等工序，直到完成半導體產品。重調度方法用於產生具有優化性能指標的重調度方案，主要有兩種方式生成式 重調度和修正式重調度。生成式重調度根據是否考慮生產線不確定因素可以分為常規性調度和魯棒性調 度。常規性調度通常忽略隨機擾動因素，旨在給出優化的靜態調度方案，但是對隨機擾動處 理能力不夠。常規性調度可以借鑑已有的調度方法，如離散時間系統仿真，運籌學，計算智 能等。魯棒性調度在常規性調度的基礎上研究生產線的各種隨機因素，在調度的時候已經 考慮各種幹擾的影響，所以給出的調度方案更適用於實際的生產。不少學者對不確性模型 的魯棒性調度展開了研究，Metha和Uzsoy提出的預期調度方案通過插入一些空閒的時間 片來減少隨機擾動的影響。Daniels和Kouvelis等人考慮生產線處於最壞情況下給出優化 調度方案，這樣可以更有效的減少隨機事件的幹擾，但是在擾動較少的情況下可能會降低 生產率。當原有的調度方案由於各種隨機因素不適用的時候，需要進行修正，即進行修正 式重調度。修正式重調度主要分為兩類局部修正式重調度、全局修正式重調度。局部修 正式重調度僅僅修正那些受擾動直接影響和間接影響的派工方案。Miyashint和Sycara 在基於約束的基礎上根據不同的情況選擇局部修正的方法，具體包括調整開始加工時間、 交換操作和切換到其他可選資源。全局修正式重調度由重調度點開始更新整個調度方案。 Bierwirth和Mattfeld在原調度方案的基礎上使用遺傳算法生成新調度，該方法可以有效 的減少重新生成調度方案的計算開銷。James等人提出了一種基於原調度方案的匹配調度 方法，考慮了多種資源約束、工件的投料和生產線擾動。重調度有許多不同的評價指標，這些評價指標大致可以分成三類有效性評價指 標、穩定性評價指標和成本評價指標。有效性評價指標通常使用一些基於時間的指標，比如加工周期，平均延遲，平均資 源利用率，最大延遲等。穩定性評價是重調度十分重要的評價指標。Wu和Storer等人認為 穩定性主要表現在新舊調度方案開始時間的偏差和新舊調度方案各個操作順序的差異。基 於時間的指標不能明顯的反映經濟效益，一些研究人員提出調度決策需要考慮一些經濟性 指標，如Shafaei和Brurm提到總成本、WIP數、延遲交貨代價和不同任務的收益等評價指 標。本發明以半導體生產線為對象，對多重入製造系統中在線重調度的策略和方法展 開研究，通過優化重調度策略和重調度方法來提高系統對不確定事件的反映能力，使新調 度方案不僅繼承了原調度的優化性同時儘可能保持調度方案的穩定性。
發明內容
本發明提出的重調度算法包括下列步驟(1)尋找匹配點，確定是否可以採用SMUR方法的判定過程，若找不到這樣的匹配點，則採用常規的右移重調度方法調整；(2)確定重調度任務集，從擾動開始時間到匹配點之間的受影響任務將是SMUR調整的對象；(3)更新任務加工時間，在等待約束的範圍內迭代更新任務的開始時間和結束時 間；其中，尋找匹配點和確定任務集的步驟是步驟1，確定故障設備kd的匹配點Γ:和需要重調度的任務集Grf .對故障設備的任務集進行刷選與排序，選擇滿足下列公式的任務，並按任務的開 始時間升序排列；Ow = min w (Xi kd | Xi kd > td)其中Om 發生擾動後，原序列中第1個任務；Xijcd 原調度中任務i在設備K上的開始時間；找出故障結束後最早滿足下列公式 的任務序號np，其中np 任務第η個操作；tu:擾動的結束時間；Pvikd 第i個操作在第k臺設備上的加工時間；從而得到，故障設備的匹配點為，故障設備的重調度任務集為
Ckd =『其中TkMd 故障設備的匹配點；X^xlkd 故障設備上第np+1個操作的開始時間；Ckj 故障設備的重調度任務集合；Om 第i個任務；步驟2，確定其他設備的匹配點:Tf和重調度任務集ζ k ；第k臺設備的匹配點可以由巧=max,64.irf U/^來確定；對於任意滿足式子~ < XKk < Tf的任務，其中k = 1，2，. . .，m且k = kd，將其加入
任務集ζX ；其中Tf :第K臺設備的匹配點；ζ k 第K臺設備的重調度任務集合；Xijk 原調度中操作i在設備k上的開始時間點；pijk 操作i在設備k上的加工時長；td:擾動的開始時間；kd 故障的設備；步驟3，確定SMUR匹配點Tp和重調度任務集ζ ；
SMUR方法的匹配點I;重調度的任務集為ζ = ζ i U ζ 2 U . . . U ζ m， 其中 k = 1，2，. . .，m ；其中Tp:全局重調度匹配點；TkM 設備的重調度匹配點；ζ i :第i臺設備的重調度任務集；更新任務時間確定了重調度匹配點後，根據匹配點是否在規定的時域範圍內選擇更新任務時間的方法。上述過程同時也確定了重調度任務集，下面介紹如何更新這些任務的開始加工時 間和結束加工時間。由於任務之間存在著上文提到的等待約束關係，調度更新被設計為一 個迭代的過程，從故障開始的一刻開始依次更新任務集中的任務，對於已經更新的任務則 從任務集中移除。這裡的任務集採用一種隊列的數據結構，如圖2所示。對於隊列中每一個任務，其 結構如圖中q所示，包含了產品號、工件號、設備號、當前步數、開始加工時間和任務加工時 間這些必要的信息。調度更新過程如圖3所示，新任務的開始加工時間由設備的最早可用時間和任務 的最早到達時間兩者的最大值確定。設備的最早可用時間，一般由兩個因素的最大值確定 (1)該設備上一個任務的結束時間；(2)設備擾動結束時間(如故障修復好的時間、維護保 養的完成時間)。任務的最早到達時間需要考慮兩種情況(1)對於單卡加工設備，任務的 最早到達時間由該任務上一步的完工時間確定；(2)對於批加工設備，任務的最早達到時 間由該批任務中工件上一步任務完工時間的最大值確定。以上SMUR重調度方法的設計目標是有效利用任務間空閒時間，快速響應生產線 擾動，及時更新調度方案，保持原調度方案的優化性能。SMUR方法只要調整部分原調度方案就可以得到新的調度，但同時可以發現，該方 法需要原調度方案比較鬆弛，具有較多的空閒時間。對於某些任務負載較重的設備，空閒時 間較少，使用上述方法會受到一定的限制。半導體生產線中，某些設備具有這樣一個特點，同一加工任務可以在多臺設備上 加工，即某些設備具有相似的功能，一般的把這些具有相似功能的設備稱為設備組。同樣以 設備故障作為生產線的擾動因素，本發明考慮設備組的匹配重調度方法。本發明的優點在於，這種算法優化了右移重調度算法，充分利用設備任務空閒，消 除擾動對調度方案的影響，大大提高生產線在重調度後的穩定性。總之，本發明提供了切實可行的半導體生產局部重調度算法，該算法的提出對研 究半導體生產重調度有一定的參考價值，對提高我國半導體生產系統領域中局部重調度算 法具有重要的指導意義。在SMUR算法中用到的一些字母符號如下nmatch-up階段中的任務數；m設備數；？^第i個任務在第k臺設備上的加工時間；kd故障的設備；
Γ/原調度中第k臺設備的調度開始時間；7廣新調度中第k臺設備的match-up時間點；Tp重調度匹配點Tmax最大match-up時間點(原調度的結束時間)；Α/加工任務i的第一臺設備；<加工任務i的最後一臺設備；ESi, k操作(i，k)可能的最早時間；LFi, k操作(i，k)可能的最遲時間；Xi, k原調度中操作(i，k)的開始時間；Yi,k新調度中操作(i，k)的開始時間；td擾動的開始時間；tu擾動的結束時間；Om發生擾動後，原序列中第i個任務；ζ k設備k的重調度任務集；ζ所有設備的重調度任務集；
圖1是SMUR的算法流程圖；圖2是重調度算法中任務隊列的數據結構示意圖；圖3是SMUR算法中迭代更新任務開始時間和結束時間示意具體實施例方式本發明提供的重調度方法的實施方式如下。本發明提供的調度方法在具體實施階段需要滿足的條件為企業必須有支撐生產 的MES系統，或者實時與實際生產同步的資料庫；由於本發明提供的兩種算法均需要仿真 作為輔助，必須至少有一種仿真平臺軟體支持。重調度系統應包括三塊內容企業資料庫、本地資料庫、重調度軟體系統、仿真平 臺。大致流程為，軟體系統每隔固定時間從企業資料庫中讀取數據，存入本地資料庫，一旦 發現重調度擾動，則觸發重調度，重調度軟體系統通過仿真接口控制仿真平臺的仿真開始、 結束，最後，將重調度後的數據通過軟體系統寫回至企業資料庫，以供MES系統使用，使線 上工作人員能及時依照最新的派工方案進行派工。以下就各部分詳細闡述本發明的實施方 式。由於企業資料庫的結構往往是異構的，且同一企業內，由於生產線的不同，所對應的資料庫也會不同。然而，本發明提供的重調度算法對生產線並無特殊需求，屬於適用性較 廣的算法。所以，要使重調度算法能夠適用於所有的生產線，需要先轉換企業資料庫至本地 資料庫。重調度算法對數據的需求並不複雜，只需要有原始的派工信息即可。本地資料庫的作用在於存儲從企業資料庫中加載的數據，目的在於比較最新的數 據與前一次加載數據的區別，以判斷是否滿足重調度的觸發條件。一般觸發條件包括三種 累計加工延時超標(指工件的實際開始加工時間或完工時間與原調度方案之間的誤差，若誤差達到一定的閥值，則說明原調度方案不再適用，必須生成重調度方案，以縮短預期調度 與實際生產之間的誤差)；設備故障(指突發的不可預測的設備故障，同時需要故障信息及 時有效的在資料庫中反映，如此才能保證重調度算法的有效性)；非計劃性投料進入生產 線(指不在計劃之內的投料，一般是企業的工程卡，即用於實驗的測試卡，且這些卡的優先 級一般比較高，一旦有這些工件的加入，勢必打亂原先的調度方案，需要重調度)。本地數據 庫的另一作用在於存儲每次重調度前後的排程方案，以方便企業通過歷史數據分析重調度 的有效性。仿真平臺，作為重調度系統的輔助工具，用於當無法找到匹配點，或算法執行超 時，可採用仿真平臺做全局重調度，仿真平臺必須提供外部接口可與軟體系統數據交互、仿 真控制等。重調度軟體系統，該部分作為重調度系統的核心部分作用在於控制企業資料庫與 本地資料庫，以及控制仿真平臺，並且實現重調度算法。在企業資料庫方面，軟體負責每隔 固定時間段加載企業資料庫中所需要的數據，並存入本地資料庫，目的在於及時地發現重 調度觸發因素。由於企業資料庫的數據量一般較大，可以採用增量形式對數據進行刷新。在 仿真平臺方面，由於本發明提供的重調度算法存在找不到匹配點或算法運行超時的情況， 在這種情況下，可選用全局重調度替代，然而全局重調度需要仿真平臺的支撐。另一方面，算法實現是軟體系統的主要部分，以下詳細闡述算法的實現過程。採用 遞歸算法實現，首先是SMUR算法。SMUR算法有三個參數，新開始時間(即當前任務的新加工開始時間)startTime， 任務Dispatch，是否調度在當前任務後的在同一設備上的任務標誌位eqpFlag，簡稱設備 標誌位。步驟1檢查startTime是否小於當前任務的原startTime，若小於則直接返回，否 則繼續下一步。因為如果新開始時間小於調度任務的原開始時間，則表示匹配點已找到，無 須繼續調度後續任務。步驟2判斷設備標誌位eqpFlag是否為真，若為真則下一步，否則跳至步驟5。步驟3尋找當前任務所對應工件的下一步工序，並找出工序所對應的任務 nextSt印Dispatch，若找到，則遞歸調用SMUR算法，參數分別為StartTime =於當前任務 flJf^nWfB] + ii^r^f^^U ；dispatch = nextStepDispatch ；eqpFlag = true ；步驟4更新當前任務的開始加工時間以及結束加工時間。步驟5尋找與當前任務處於同一設備的下一項任務，可能不止一項，因為存在組 批現象，存入列表nextEqpDispatchList中。步驟6若列表中只有一項任務，則進行步驟7，否則跳轉至步驟9。步驟7遞歸調用SMUR算法，參數分別為StartTime =於當前任務新開始時間+任 務持續時間；dispatch = nextStepDispatchList
；eqpFlag = true。步驟8尋找當前任務所對應工件的下一步工序，並找出工序所對應的任務 nextSt印Dispatch，若找到則遞歸調用SMUR算法，參數分別為StartTime =於當前任務新 開始時間+任務持續時間；dispatch = nextSt印DispatcheqpFlag = true。跳轉至步驟 12。步驟9對nextEqpDispatchList中的每一項任務做循環，直至遍歷列表中的所有
9調度任務。循環步驟為步驟10至步驟11。步驟10若當前調度任務為循環中的第一項任務，則遞歸調用SMUR算法 ，參數分別 為utartTime =於當前任務新開始時間+任務持續時間；dispatch =當前循環的調度任 務；eqpFlag = true。若當前任務並不是列表中的第一項任務，同樣遞歸調用SMUR算法，除 了 eqpFlag = false，其餘兩項參數與前面一致。步驟11尋找當前任務所對應工件的下一步工序，並找出工序所對應的任務 nextSt印Dispatch，若找到，則遞歸調用SMUR算法，參數分別為StartTime =於當前任務 flJf^nWfB] + ii^r^f^^U ；dispatch = nextStepDispatch ；eqpFlag = true。步驟12更新當前任務的開始加工時間與結束時間。最後，提供本發明在MINIFAB以及HP24FAB1半導體生產線模型中的性能表現。主 要分析修正後的調度任務與原調度任務的累計延時。仿真的前提為1.隨機設置5處故障， 每次故障持續半小時。2.採用固定數量投料，兩個月內全部投完。3.仿真時間為60天。
權利要求
一種面向多重入製造系統在線調度的單臺設備匹配重調度方法，包括下列步驟(1)尋找匹配點，確定是否可以採用SMUR方法的判定過程，若找不到這樣的匹配點，則採用常規的右移重調度方法調整；(2)確定重調度任務集，從擾動開始時間到匹配點之間的受影響任務將是SMUR調整的對象；(3)更新任務加工時間，在等待約束的範圍內迭代更新任務的開始時間和結束時間；其中，尋找匹配點和確定任務集的步驟是步驟1，確定故障設備kd的匹配點和需要重調度的任務集對故障設備的任務集進行刷選與排序，選擇滿足下列公式的任務，並按任務的開始時間升序排列； O [1] = min i ( X i , kd | X i , kd td ) 其中O[1]發生擾動後，原序列中第1個任務；原調度中任務i在設備K上的開始時間；找出故障結束後最早滿足下列公式的任務序號np， t u+ i=1 np P [i], k d - X [np+1], k d 0 其中np任務第n個操作；tu擾動的結束時間；第i個操作在第k臺設備上的加工時間；從而得到，故障設備的匹配點為故障設備的重調度任務集為其中；故障設備的匹配點；故障設備上第np+1個操作的開始時間；故障設備的重調度任務集合；O[i]第i個任務；步驟2，確定其他設備的匹配點和重調度任務集ζk第k臺設備的匹配點可以由來確定；對於任意滿足式子的任務，其中k＝1，2，...，m且k＝kd，將其加入任務集ζk；其中第K臺設備的匹配點；ζk第K臺設備的重調度任務集合；Xi，k原調度中操作i在設備k上的開始時間點；pi，k操作i在設備k上的加工時長；td擾動的開始時間；kd故障的設備；步驟3，確定SMUR匹配點Tp和重調度任務集ζ；SMUR方法的匹配點重調度的任務集為ζ＝ζ1∪ζ2∪...∪ζm，其中k＝1，2，...，m；其中Tp全局重調度匹配點；設備的重調度匹配點；ζi第i臺設備的重調度任務集。FSA00000114244100011.tif,FSA00000114244100012.tif,FSA00000114244100014.tif,FSA00000114244100021.tif,FSA00000114244100022.tif,FSA00000114244100023.tif,FSA00000114244100024.tif,FSA00000114244100025.tif,FSA00000114244100026.tif,FSA00000114244100027.tif,FSA00000114244100028.tif,FSA00000114244100029.tif,FSA000001142441000210.tif,FSA00000114244100031.tif,FSA00000114244100032.tif
全文摘要
本發明提供一種面向多重入製造系統在線調度的單臺設備匹配重調度方法，即局部重調度算法中的單臺設備匹配重調度(SMUR)算法；這種算法以充分利用設備空閒時間為思想，以提升重調度決策的有效性與生產線的穩定性。該方法主要過程是，(1)尋找匹配點，確定是否可以採用SMUR方法的判定過程，若找不到這樣的匹配點，則採用常規的右移重調度方法調整；(2)確定重調度任務集，從擾動開始時間到匹配點之間的受影響任務將是SMUR調整的對象；(3)更新任務加工時間，在等待約束的範圍內迭代更新任務的開始時間和結束時間；優點在於，這種算法優化了右移重調度算法，充分利用設備任務空閒，消除擾動對調度方案的影響，大大提高生產線在重調度後的穩定性。
文檔編號G05B19/418GK101833319SQ201010170689
公開日2010年9月15日 申請日期2010年5月11日 優先權日2010年5月11日
發明者喬非, 葉愷, 施斌 申請人:同濟大學