基於空閒矩陣的多約束無等待混合流水調度建模方法

2023-04-27 17:07:06

基於空閒矩陣的多約束無等待混合流水調度建模方法
【專利摘要】本發明公開了一種基於空閒矩陣的多約束無等待混合流水調度建模方法。首先進行約束預處理：對於存在跳過處理單元約束，可將該任務在該單元上的處理時間設置為0;對於存在先序或禁止轉換約束，則在計算目標函數值時附加一個很大的懲罰項；對於存在順序依賴的準備時間，準備時間加入前一任務處理時間之後。其次，對於具有並行機的階段，採用基於甘特圖的軟壓縮調整方法進行處理，構造出空閒矩陣。最後，以空閒矩陣為基礎，根據調度目標構造出調度模型。該方法將一個具有上述複雜約束的無等待混合流水調度問題轉化為一個不帶約束的普通的無等待流水調度問題，再基於空閒矩陣建立調度模型，從而降低了模型的複雜性和求解難度。
【專利說明】基於空閒矩陣的多約束無等待混合流水調度建模方法

【技術領域】
[0001] 本發明屬於無等待混合流水調度建模領域，特別涉及一種基於空閒矩陣的多約束 無等待混合流水調度建模方法。

【背景技術】
[0002] 無等待流水調度問題是一類重要的約束型流水調度問題，是典型的N P難問題， 廣泛存在於流程式企業中，如化工製造、鋼鐵鑄造、食品加工、製藥、塑料製造等，其生產技 術需要的一系列處理過程需緊密相連以防止衰變或汙染。具有並行機的無等待流水調度又 稱為無等待混合（或柔性）流水調度。現有關於無等待混合流水調度研究主要是建立在對 實際過程簡化和理想狀態假設基礎上的，沒有系統的考慮實際過程中的多種約束，主要存 在如下一些問題：現有的研究大都忽略了在處理單元上的準備時間或認為其時間是一個固 定值，但實際生產中，這部分時間往往對無等待調度問題具有重要影響且準備時間還跟生 產任務順序相關，需要在調度時對其單獨考慮；現有的研究大都假設所有的產品依次經過 所有的階段且生產次序可以任意切換，但對於實際加工過程，產品間生產次序禁止從一種 產品切換到另一種產品、或產品具有先序要求，或某些產品可能會不需要經過某些階段；對 於多階段且具有複雜約束的無等待混合流水調度問題，用已有方法建立的模型複雜、難以 求解。而在化工製造、鋼鐵鑄造、食品加工、製藥等一些實際生產過程中需要考慮上述實際 約束。近幾年，結合無等待流水調度特徵的空閒時間調度理論因能降低無等待流水調度的 計算複雜性，而成為研究無等待流水調度問題的有效方法，但該方法還不能應用於多約束 無等待混合流水調度。


【發明內容】

[0003] 本發明的目的是提供一種基於空閒矩陣的多約束無等待混合流水調度建模方法， 在理論上能實現對存在並行機、順序關聯的準備時間、禁止切換、先序要求和跳過處理單元 等多種約束的有效處理，使建立的模型更加實用和有效。
[0004] 本發明方法的思路：當存在並行機、順序關聯的準備時間、禁止切換、先序要求和 跳過處理單元等五種約束時，分析對空閒矩陣影響的一般規律，並分別提出基於空閒矩陣 的軟處理方法，從而將一個具有上述複雜約束的無等待混合流水調度問題轉化為一個不帶 約束的普通的無等待流水調度問題，並建立其基於空閒矩陣的調度模型。
[0005] 具體步驟為：
[0006] (1)準備工作階段
[0007] 對於一般的以最小化最大完工時間makespan為目標的零等待流水線調度問題， 採用兩步法來進行處理：第一步為臨時分配階段，即根據構造基本的零等待流水調度；第 二步為調整階段，即儘可能的將後面的任務啟動時間向前移，以減少最後一階段上的空閒 時間。
[0008] 引入一個空間時間矩陣T，表示相鄰的任務i和j在最後一個階段Μ上的空閒 時間，只要知道每個任務在各單元上的處理時間，很容易計算出任意兩個任務之間在最後 一個階段Μ上的空閒時間ty。則調度目標最小化最大完工時間(：_等價於最小化最後一階 段上機器的總空閒時間。藉助於空閒時間矩陣T，如果把空閒時間矩陣中的元素看成是 兩點之間的距離的話，則尋找最佳的調度排列等價於基於T尋找一條最短的路徑，由於 是非對稱的，因此原問題被轉換成一個非對稱旅行商問題，即ATSP。
[0009] (2)約束預處理
[0010] a.具有順序依賴的準備時間的預處理方法
[0011] 對於具有順序依賴的準備時間，任務間的準備時間與前後兩任務的順序相關，只 要確定了順序，準備時間就確定了，可把其單獨作為一個時間片處理，假設在前一個任務完 成後立即進行下一階段的準備工作。再按準備工作階段所述的二步法進行處理。在執行調 整階段時，因準備時間的存在，會影響到後繼任務前移的最長時間，準備時間看作前一任務 後續處理時間。
[0012] b.帶有禁止轉換和先序要求的預處理方法
[0013] 對於這兩種情況都可採用類似罰函數的處理方法。若兩個任務i，j之間禁止轉 換，則將空閒時間矩陣的時間增量設置為一個很大的數C?。對於實際計算過程，不必再 考慮禁止轉換約束，即對於含有禁止切換的候選解，仍然認為其是可行的。但對於含有禁止 切換的候選解，因任務間轉換的時間很大，其目標函數值必然要劣於不含禁止切換的解，因 而並不會被選中，這樣並不會影響算法最終的尋優結果。
[0014] 對於帶有先序要求的調度問題，類似的上面的處理方法。在處理過程中，對於違反 先序要求的候選解仍然認為是可行的，只是在計算目標函數值時加上一個很大的數…作為 懲罰，這樣導致這些解會因劣於不違反先序要求的解，而不會被選中，不會影響算法的尋優 結果。
[0015] c.跳過某些處理單元的預處理方法
[0016] 若某些任務跳過某些處理單元，仍然按所有的任務都需要經過所有的單元來對 待，若有任務要跳過的某個階段，則只需要將其在該階段的處理時間設置為〇即可。
[0017] (3)並行機建模
[0018] a.按不帶並行機的情況進行處理。
[0019] b.進行軟約束壓縮調整，具體過程如下：
[0020] 壓縮調整過程對於關鍵點在不具有並行設備的階段其約束條件為硬約束，不能違 反。若關鍵點在具有並行機處理階段的，則認為其約束為軟約束，可以對其進行進一步採取 壓縮處理。在並行處理的任務不超過並行處理機的個數的情況下，使得壓縮後的關鍵時間 點轉移到不含並行處理機的階段上為止。
[0021] (4)構建空閒矩陣
[0022] 假設調度系統中有N個任務和Μ個處理階段，調度的目標是最小化最大完成時間， 即生產周期，調度系統可以描述如下：

【權利要求】
1. 一種基於空閒矩陣的多約束無等待混合流水調度建模方法，其特徵在於具體步驟 為： (1) 準備工作階段 對於一般的以最小化最大完工時間makespan為目標的零等待流水線調度問題，採用 兩步法來進行處理：第一步為臨時分配階段，即根據構造基本的零等待流水調度；第二步 為調整階段，即儘可能的將後面的任務啟動時間向前移，以減少最後一階段上的空閒時間； 引入一個空間時間矩陣T，表示相鄰的任務i和j在最後一個階段Μ上的空閒時間，只 要知道每個任務在各單元上的處理時間，很容易計算出任意兩個任務之間在最後一個階段 Μ上的空閒時間ti;j ;則調度目標最小化最大完工時間Cmax等價於最小化最後一階段上機器 的總空閒時間；藉助於空閒時間矩陣T，如果把空閒時間矩陣中的元素看成是兩點之間 的距離的話，則尋找最佳的調度排列等價於基於τ尋找一條最短的路徑，由於是非對稱 的，因此原問題被轉換成一個非對稱旅行商問題，即ATSP ; (2) 約束預處理 a. 具有順序依賴的準備時間的預處理方法 對於具有順序依賴的準備時間，任務間的準備時間與前後兩任務的順序相關，只要確 定了順序，準備時間就確定了，可把其單獨作為一個時間片處理，假設在前一個任務完成後 立即進行下一階段的準備工作；再按準備工作階段所述的二步法進行處理；在執行調整階 段時，因準備時間的存在，會影響到後繼任務前移的最長時間，準備時間看作前一任務後續 處理時間； b. 帶有禁止轉換和先序要求的預處理方法 對於這兩種情況都可採用類似罰函數的處理方法；若兩個任務i，j之間禁止轉換，則 將空閒時間矩陣的時間增量設置為一個很大的數…；對於實際計算過程，不必再考慮 禁止轉換約束，即對於含有禁止切換的候選解，仍然認為其是可行的；但對於含有禁止切換 的候選解，因任務間轉換的時間很大，其目標函數值必然要劣於不含禁止切換的解，因而並 不會被選中，這樣並不會影響算法最終的尋優結果； 對於帶有先序要求的調度問題，類似的上面的處理方法；在處理過程中，對於違反先 序要求的候選解仍然認為是可行的，只是在計算目標函數值時加上一個很大的數…作為懲 罰，這樣導致這些解會因劣於不違反先序要求的解，而不會被選中，不會影響算法的尋優結 果； c. 跳過某些處理單元的預處理方法 若某些任務跳過某些處理單元，仍然按所有的任務都需要經過所有的單元來對待，若 有任務要跳過的某個階段，則只需要將其在該階段的處理時間設置為〇即可； (3) 並行機建模 a. 按不帶並行機的情況進行處理； b. 進行軟約束壓縮調整，具體過程如下： 壓縮調整過程對於關鍵點在不具有並行設備的階段其約束條件為硬約束，不能違反； 若關鍵點在具有並行機處理階段的，則認為其約束為軟約束，可以對其進行進一步採取壓 縮處理；在並行處理的任務不超過並行處理機的個數的情況下，使得壓縮後的關鍵時間點 轉移到不含並行處理機的階段上為止； (4) 構建空閒矩陣 假設調度系統中有N個任務和Μ個處理階段，調度的目標是最小化最大完成時間，即生 產周期，調度系統可以描述如下：
其中
和I\m分別表示任務j在階段m中的開始時間、結束時間和處理時間；按 照上面介紹的臨時分配方法，兩個任務間的空閒時間DT可以按下面公式計算獲得；
SUi，^為任務i，j在階段m中的順序依賴的準備時間；由於生產周期指標僅依賴於每 個任務的完成時間，這裡引入了一個空閒時間矩陣T，Tu表示任務i和j在最後一個階段 Μ上的空閒時間，那麼有
(5) 建立調度模型 對於任意一個排列Π = 有：
很容易看出，對所有的可行解來說total是一個常量； 原優化目標可以轉換成以下形式：
因此，如果把空閒時間矩陣T看成一個距離矩陣的話，新的優化目標可以看成是基於T 來尋找一條最優的路徑；因 T是非對稱的，所以這是一個非對稱旅行商模型。
【文檔編號】G06Q10/06GK104217287SQ201410437295
【公開日】2014年12月17日 申請日期:2014年8月30日 優先權日:2014年8月30日
【發明者】董明剛, 程小輝, 牛秦洲, 葉漢民, 姜傳賢 申請人:桂林理工大學