一種複雜大系統環境下的有預測動態調度方法
2023-05-13 05:00:31 1
專利名稱：一種複雜大系統環境下的有預測動態調度方法
技術領域：
本發明涉及一種車間作業動態調度方法，尤其是複雜大系統環境下的有預 測動態調度方法。
背景技術：
車間作業動態調度在現代機械製造、加工等行業中有著舉足輕重的作用。 它為企業實現精細化管理，在保證質量的情況下，按定單交貨期的約束按時交 貨，成為決定企業市場競爭力的主要因素。
車間作業動態調度是根據當前的工廠資源情況，為可以加工的設備實時地 制定調度方案，給出當前在設備上的待加工工單的加工優先級，並進一步優先 選擇最合適工單在設備上加工。動態調度是指作業依次進入待加工狀態，各種 作業不斷進入系統接受加工，還要考慮作業環境中不斷出現的動態擾動，如作 業的加工超時、設備的損壞等。因此，動態調度要根據系統中作業、設備等的 狀況，不斷地進行調度。而實際調度的類型往往是離散製造型，且是動態變化 的。
對於車間調度問題，如果在決策時刻全局信息完全，車間作業調動系統可
以採用靜態算法進行全局一次調度。靜態精確算法在理論上可以實現全局最優 調度，但由於問題是NP—Hard的，當問題規模增大時，存在計算的難處理性。 如果在決策時刻未來的信息未知，則車間作業調度系統只能採用動態調度算法。 而動態調度算法(如規則調度)是啟發式算法，不能實現全局最優調度，在很多 情況下甚至不能對最終的全局調度進行評估。
因此一些研究者提出靜態調度和動態調度相結合的方法，如滾動調度和被
動調度相結合等，初始全局靜態調度能夠對一段時間內的工件進行全局調度， 使得調度結果具有宏觀上的全局優化意義。而在動態調度時，根據靜態調度的 結果，作進一步的調度。由於全局靜態調度向車間定期提前釋放定單，使得調 度者可以預知部分未到達工件的信息。有預測的動態調度算法在每個決策時刻 充分利用對未來信息的預測，相對沒有預測的動態算法可以改善調度的全局性 能。
發明內容
本發明的目的在於提供一種複雜大系統環境下的有預測動態調度方法，主
要解決現有車間作業動態調度中存在的技術問題，它從ERP中導入需求、庫存
等數據，並根據工廠加工狀況，作實時車間調度，防止違法加工工藝等諸多約
束的情況發生，生成實時派工指令。使得企業有效利用生產資源，降低生產成
本，提高企業效益。
一種複雜大系統環境下的有預測動態調度方法，其特徵在於所述方法包括
以下步驟
① 伺服器從終端獲取待動態調度設備組的待動態調度工序集合，計算每個 工序的可調度時域並檢驗；
② 伺服器確定待動態調度工序集合進行動態調度優先度，且對每道工序進 行判斷為緊急工序或非緊急工序；
③ 伺服器進行動態調度計算，包括虛擬合批、判斷是否可派工、更新設備 狀態等操作，並將最終調度結果反饋給終端，以進行設備分配；
該步驟①中工序的可調度時域指工序最早最晚可派工時刻之間的時間段。 該步驟①中檢驗是指判斷該工序是否己經違反約束若是，則該工序從待
動態調度工序集合中刪除，並插入已違反約束工序集合
該步驟②中對待調度工序動態調度優先度是指在待動態調度設備組上待 動態調度工序理想的加工順序，工序優先度越高，越需要優先加工。
該步驟②中對判斷緊急工序是指當前時刻在對應設備上若該工序不派工， 而對其它工序派工，則由於該設備被其它工序佔用，導致該工序過晚加工而不 滿足約束，並可能導致廢品產生等一系列後果，緊急工序的判斷是通過工序的 最晚可派工時刻與一個經驗閾值進行比較。
該步驟③中所述的虛擬合批是指，需要對不滿足最小加工批量的工序，'根
據工序的派工優先度進行虛擬合批操作，即與其它工單同時佔用某設備。
所述所有參與虛擬合批操作的工序，加工批量之和小於最大加工批量，加
工工藝相同，加工設備相同，可調度時域的交集不為空集。
該步驟③中所述的判斷是否可派工是指設備有足夠的產能加工某工序，且 不會因此使得設備等待時間是否超過設備組派工最大可允許空閒時間。
該步驟③中所述的更新設備狀態是指設備狀態更新為從當前時刻至工序計 劃完工時刻都為佔用狀態。
本發明中採用逐步精確的方法，初始全局靜態調度能夠對一段時間內的工 件進行全局調度，使得調度結果具有宏觀上的全局優化意義，且僅利用相對比 較確定的信息，通過調度給出比較粗糙的結果，避免了調度結果需要實時修正 的問題，且整體調度建立在工序全局靜態調度的基礎上，根據實際情況，對靜 態調度的結果作進一步的調度，使得工廠實際加工情況儘量接近工單排程計劃 優化方案的同時，能夠根據工序約束情況，針對不同的事件，給出不同的優化 調整策略，生成派工指令及預警信號，且由於全局靜態調度向車間定期提前釋 放定單，使得調度者可以預知部分未到達工件的信息，有預測的動態調度算法 在每個決策時刻充分利用對未來信息的預測，相對沒有預測的動態算法可以改
善調度的全局性能，使得設備分配更為合理，從而降低了生產成本，提高了企
業的效益。
圖1是實現複雜大系統環境下的有預測動態調度方法的硬體拓撲結構示意
圖2是本發明方法中複雜大系統環境下的有預測動態調度系統流程示意
圖3是本發明方法中計算每個工序的可調度時域並檢驗流程示意圖；' 圖4是本發明方法中工序調度優先度確定流程示意圖； 圖5是本發明方法中動態調度計算流程示意圖。
具體實施例方式
以下結合附圖和實施例對本發明的技術方案作進一步描述。 本發明方法的實現基於如圖1所示的硬體拓撲結構，伺服器從各終端及數據 庫獲取所需信息，然後在伺服器端根據工廠加工狀況，作實時車間調度，防止 違法加工工藝等諸多約束的情況發生，生成實時派工指令處理，反饋給各工作 車間。
在終端、伺服器及資料庫的硬體選擇時，客戶端的功能主要是客戶端可以 採用通用的PC機，也可以是多臺獨立的小型伺服器構成，其基本要求是具有一
定的運算能力、輸入輸出功能、以及將運算結果通過網絡傳輸出去的功能，並 能夠接受遠程伺服器運算的結果。
本實施例動態調度系統的拓撲結構如圖1所示，所選用硬體的具體參數為
客戶端及各終端的基本配置為
計算機主機PIII 500 MHZ以上；
記憶容量256MB以上； 硬碟空間20 GB以上；
顯示器1024x768真彩色顯示器，建議使用1280x1024或更高配置； 磁碟需求16倍速以上之CD-ROM或DVD-ROM;
當工廠規模不大時，伺服器端可以採用通用的PC機，但建議採用大型服務 器以適應大型加工企業，其基本要求是具有較好的運算性能、具有較強的數據 存儲及維護能力，網絡傳輸高效穩定。
伺服器端的基本配置為
計算機主機Celon 2.66G以上；
記憶容量1GB以上；
硬碟空間160GB以上；
顯示器1024x768真彩色顯示器，建議使用1280x1024或更高配置； 磁碟需求16倍速以上之CD-ROM或DVD-ROM;
資料庫採用ACCESS資料庫，同時也支持如SQL Server等資料庫系統。 複雜大系統環境下的有預測動態調度方法，如圖2所示，包括以下步驟
1.伺服器獲取全局靜態調度結果及動態調度數據，各步驟的具體細節描述 如下
全局靜態調度既可是伺服器對銷售部門接受的訂單所涉及的工序，根 據倉庫部、設備管理部門、加工車間、委外單位等終端輸入的信息，依 照一定的規則運算得到的結果，也可以是生產計劃部門通過終端手動輸 入的結果。
動態調度數據是指在靜態調度結果基礎之上， 一些被確定的過去未 知信息。主要包括具有空閒設備的設備組(該設備組內某設備加工完畢
後工時匯報)，即該設備組上具有足夠物料的待加工工序(同工單前道工 序加工完畢)
2. 伺服器取待動態調度設備組的待動態調度工序集合，計算每個工序的可 調度時域並檢驗，具體流程請參閱圖3，包括以下步驟
a) 從待動態調度設備組的待動態調度工序集合中不重複的取一個工序。
b) 根據約束計算可調度時域，對此工序進行最早可派工時刻及最晚可派
工時刻的計算。
工序的最早可派工時刻是指，工序實際派工時刻必須晚於此時 亥lj，使得各個約束都滿足。工序的最晚可派工時刻是指，工序實際派 工時刻必須早於此時刻，使得各個約束都滿足。這兩個值，體現了約 束的抽象，直接影響算法的性能。此處的約束主要是指工藝約束、工 序間最大最小時間間隔約束、物料上線時刻約束、最早可開工時刻約 束、最晚可開工時刻約束等約束。最早最晚可派工時刻之間即為可調 度時域。
C)根據該工序可調度時域判斷該工序是否已經違反約束若是，則該工 序從待動態調度工序集合中刪除，並插入已違反約束工序集，以便車 間管理人員能夠作適當的調整。滿足一下條件之一，即為工序違反約 束
i. 工序最晚可派工時刻早於當前時刻。
ii. 工序最晚可派工時刻早於最早可派工時刻。
d)判斷是否遍歷完待動態調度工序集合中所有工序若否，則回到步驟 b;若是，則繼續下一步。
3. 伺服器待動態調度工序集合進行動態調度優先度確定，判斷緊急工序和
非緊急工序，各步驟的具體細節描述如下
定義緊急工序為，當前時刻在對應設備上若該工序不派工，而對其 它工序派工，則由於該設備被其它工單佔用，導致該工序過晚加工而不 滿足約束，並可能導致廢品產生等一系列後果，則該工序為緊急工序。 具體流程請參閱圖4，包括以下步驟
a. 設置設備組最大可允許空閒時間，並以此為根據獲取緊急工序
緊急工序是一個相對的概念，無法精確計算，而只能估計。對動 態調度系統，需要設置從當前時刻起的一個警戒時刻而這段時間為一 經驗閾值，滿足一下兩點
i. 警戒時間的設置過小，將失去警戒意義。
ii. 警戒時間的設置過大，導致設備大量時間被等待浪費。 在本發明中統計待動態調度工序集合中所有工序所需要的加工
時間平均值，作為警戒時間，並將該時間段稱為設備組派工最大可允 許空閒時間。根據此設置的設備組派工最大可允許空閒時間，對每道 工序進行判斷當工序的最晚可派工時刻早於警戒時刻，則說明該工 序比較緊急。
b. 按照緊急工序優先派工的啟發式規則從待動態調度工序集合中獲取第 一等派工優先度工單，優先度的高低與緊急程度一致，即最晚可派工 時刻越早，則優先度越高。判斷第一等派工優先度工序的依據為
最晚可派工時刻<=當前時刻+設備組最大可允許空閒時間。 待調度工單動態調度優先度是指在需要動態調度的設備組上待調 度工序一種理想的加工順序，工序優先度越高，越需要優先加工。 C.按照先到先服務的啟發式規則，從待動態調度工序集合中獲取第二等
派工優先度工單，優先度的高低與全局靜態調度計劃開工時刻一致， 即劃開工時刻越早，則優先度越高，且這些工序的優先度整體小於緊 急工序的優先度。判斷第二等派工優先度工序的依據為最早可派工 時刻早於當前時刻的工序。 d.按照設備利用率最大化啟發式規則賦予其餘工序第三等派工優先度。 按照最早可派工時刻早晚賦予優先度，且這些工序的優先度整體小於 前兩類工序。
4.伺服器進行動態調度計算，包括虛擬合批、判斷是否可派工、更新設備
狀態等操作，具體流程請參閱圖5，包括以下步驟
a. 待動態調度工序集合中按照優先度高低依次取一道待動態調度工序。 判斷該工序是否為第三等派工優先度若是，則轉到步驟g，否則繼續。
b. 判斷該工序是否需要虛擬合批操作若該工序不滿足最小加工批量， 且加工設備組允許虛擬合批，則進行虛擬合批操作。虛擬合批為多個 工序(工單)同時佔用同一個設備資源，例如鍋爐設備在滿足最大容 量量的前提下，可加工多個工單。虛擬合批操作需要査找滿足以下幾 個條件的工序
i. 所有參與虛擬合批操作的工序，加工批量之和小於最大加工批 量；
ii. 所有參與虛擬合批操作的工序，加工工藝相同，加工設備相同； iii. 所有參與虛擬合批的工序，可調度時域的交集不為空集。 若該待動態調度工序本身及參與虛擬合批的工序的加工批量之和小於 最小加工批量，且該工序為第二等派工優先度，則轉到步驟g，否則繼續。
C.確定該待動態調度工序計劃開工時刻。若該工序參與合批，則該待動 態調度工序計劃開工時刻為所有參與虛擬合批的工序可調度時域交 集的開始時刻。否則，該待動態調度工序計劃開工時刻為自身可調度 時域開始時刻。
d. 根據設備等待時間儘量短的原則，判斷該待動態調度工序計劃開工時 刻是否過晚。若是，則轉到步驟g。判斷的依據為工單計劃開工時 刻是否晚於當前時刻+設備組派工最大可允許空閒時間。
e. 根據工序計劃開工時刻及額定加工時間，確定工序計劃完工時刻，判
斷該工序及其合批工序是否可派工。主要的判斷依據如下
i. 從工序開工時刻到工序完工時刻，加工設備都是空閒狀態，即有足 夠的產能用以加工該工單及其虛擬合批工單；
ii. 若不滿足前一個條件，則判斷是否可以在用戶允許的時間範圍 內適當推後下班時間；
iii. 若不滿足前一個條件，則判斷是否可以中斷該工序，即該工序 是否允許暫停加工。
f. 判斷是否派工成功，若是，則更新設備狀態表及派工單列表，動態調 度計算結束。設備狀態更新為從當前時刻至工序計劃完工時刻都為佔 用狀態。派工單列表則根據工序計劃開工時刻與計劃完工時刻更新。 需要注意的是，中斷操作將影響工序計劃完工時刻，因此需要更新該 值；若否，繼續下一步驟。
g. 判斷是否遍歷完帶動態調度工序集合中所有工序若是，則在客戶端 反饋調度結果，動態調度計算結束；若否，則回到步驟a。
綜上所述僅為本發明的較佳實施例而已，並非用來限定本發明的實施範圍。即 凡依本發明申請專利範圍的內容所作的等效變化與修飾，都應為本發明的技術範 疇。
權利要求
1.一種複雜大系統環境下的有預測動態調度方法，其特徵在於所述方法包括以 下步驟 ①伺服器從終端獲取待動態調度設備組的待動態調度工序集合，計算每個工序的可調度時域並檢驗； ②伺服器確定待動態調度工序集合進行動態調度優先度，且對每道工序進行判斷為緊急工序或非緊急工序； ③伺服器進行動態調度計算，包括虛擬合批、判斷是否可派工、更新設備狀態等操作，並將最終調度結果反饋給終端，以進行設備分配。
2. 根據權禾j要求1所述的一種複雜大系統環境下的有預測動態調度方法，其特 徵在於該步驟①中工序的可調度時域指工序最早最晚可派工時刻之間的時間段。
3. 根據權禾l房求1所述的一種複雜大系統環境下的有預測動態調度方法，其特 徵在於該步驟 中檢驗是指判斷該工序是否已經違反約束若是，則該工序從待動態調度工序集合中刪除，並插入已違反約束工序集合。
4. 根據權禾l展求1所述的一種複雜大系統環境下的有預測動態調度方法，其特徵在於該步驟②中對待調度工序動態調度優先度是指在待動態調度設備組上待動態調度工序理想的加工順序，工序優先度越高，越需要優先加工。'
5. 根據權禾l」要求1所述的一種複雜大系統環境下的有預測動態調度方法，其特徵在於該步驟②中對判斷緊急工序是指當前時刻在對應設備上若該工序不派 工，而對其它工序派工，則由於該設備被其它工序佔用，導致該工序過晚加 工而不滿足約束，並可能導致廢品產生等一系列後果，緊急工序的判斷是通過工序的最晚可派工時刻與一個經驗閾值進行比較。
6. 根據權禾瞎求1所述的一種複雜大系統環境下的有預測動態調度方法，其特徵在於該步驟③中所述的虛擬合批是指，需要對不滿足最小加工批量的工序，根據工序的派工優先度進行虛擬合批操作，即與其它工單同時佔用某設備。
7. 根據權禾,求6所述的一種複雜大系統環境下的有預測動態調度方法，其特徵在於所述所有參與虛擬合批操作的工序，加工批量之和小於最大加工批 量，加工工藝相同，加工設備相同，可調度時域的交集不為空集。
8. 根據權禾l」要求1所述的一種複雜大系統環境下的有預測動態調度方法，其特 徵在於該步驟③中所述的判斷是否可派工是指設備有足夠的產能加工某工序，且不會因此使得設備等待時間是否超過設備組派工最大可允許空閒時間。
9. 根據權浪P求1所述的一種複雜大系統環境下的有預測動態調度方法，其特徵在於該步驟③中所述的更新設備狀態是指設備狀態更新為從當前時刻至工 序計劃完工時刻都為佔用狀態。
全文摘要
本發明涉及一種複雜大系統環境下的有預測動態調度方法。本發明的目的在於提供一種調度方法，主要解決現有車間作業動態調度中存在的計算難處理性或非全局最優性。本方法建立在工序全局靜態調度的基礎上，根據實際情況，對靜態調度的結果作進一步的調度，使得工廠實際加工情況儘量接近工單排程計劃優化方案的同時，能夠根據工序約束情況，針對不同的事件，給出不同的優化調整策略，生成派工指令及預警信號，且由於全局靜態調度向車間定期提前釋放定單，使得調度者可以預知部分未到達工件的信息，在每個決策時刻充分利用對未來信息的預測，相對無預測的動態算法可改善調度的全局性能，使得設備分配更為合理，從而降低了生產成本，提高了企業的效益。
文檔編號G05B19/418GK101364107SQ20081020039
公開日2009年2月11日 申請日期2008年9月24日 優先權日2008年9月24日
發明者傑 陳, 顧永明 申請人:永凱軟體技術(上海)有限公司