基於多階段智能優化算法的動態柔性作業車間調度控制方法
2023-10-04 17:03:39 1
基於多階段智能優化算法的動態柔性作業車間調度控制方法
【專利摘要】本發明提供基於多階段智能優化算法的動態柔性作業車間調度控制方法，解決了動態調度過程處理事件重調度時策略單一的問題。其方案是：包括第一階段：初始調度方案的優化與選擇；第二階段：判斷車間工具機故障，並記錄車間工具機故障信息；第三階段：進行重調度，確定重調度執行方案。本發明在整個動態調度與控制過程中建立多階段，並且在每個階段藉助自適應遺傳算法進行優化求解，在不同階段採取不同的執行方案，加速處理動態事件的響應時間，提高重調度方案的可行性和穩定性，以獲得高質量的適合車間實際生產的調度方案，縮短生產時間。
【專利說明】基於多階段智能優化算法的動態柔性作業車間調度控制方 法
【技術領域】
[0001] 本發明設及車間生產調度控制【技術領域】，特別是用於柔性車間生產過程的調度管 理與優化的基於多階段智能優化算法的動態柔性作業車間調度控制方法。
【背景技術】
[0002] 進入21世紀W來，隨著全球市場競爭的加劇、客戶需求越來越多樣化和個性化， 企業生產正朝著"品種多樣、批量變小、注重交貨期、減少庫存"的方向發展，現代企業要想 在激烈的競爭中立於不敗之地，必須W最低的成本、最好的質量、最快的速度和最優的服務 來快速響應市場，其中，車間生產調度是實現企業生產高效率、高柔性和高可靠性的關鍵因 素之一，是企業製造系統的基礎，生產調度與控制的優化技術是先進位造技術和現代管理 技術的核屯、，科學地制定生產調度方案，對於縮短產品生產周期，控制車間的在制品庫存， 提高產品交貨期滿足率和提高企業生產率起著至關重要的作用。
[0003] 在傳統車間調度模型中，一般簡化為若干調度模型，其中作業車間調度問題（Job shop scheduling problem, JS巧是一種十分典型的模型，它的特點是每個工序使用的工具機 被事先確定，並且是唯一的，但是，該並不符合實際加工情況，容易導致加工計劃與實際生 產調度相脫節。在現代企業的實際加工過程中，柔性製造系統和數控加工中屯、等一些柔性 生產系統的出現使得一道工序可W在多臺工具機上被加工，也就產生了柔性作業車間調度問 題（Flexible job shop scheduling problem, FJSP)，它的核屯、是工件的每道工序可W在 一個工具機集合（由加工能力相同的多臺工具機組成的集合）中任意一臺工具機上加工。在實際 生產過程中，當每道工序可W在多臺機器上加工時可W有效的提高設備的利用率，而且還 可W有效的維持生產的穩定性，一方面，柔性作業車間調度問題包含兩個子問題：確定各工 件的加工機器（機器選擇子問題）和確定各個機器上的加工先後順序（工序排序子問題）； 另一方面，柔性作業車間調度問題是典型的NP-hard問題，一直吸引著學者的廣泛關注，是 製造系統領域的研究熱點之一。
[0004] 從1990年首次提出柔性作業車間調度問題至今，對柔性作業車間調度問題的研 究主要集中在靜態、確定的假設條件下進行的，造成理論成果與在實際中應用程度還存在 一定的距離，在實際生產中會出現動態事件，比如，原材料緊缺、緊急任務插入、新訂單到 達、交貨期變更W及車間內部人員曠休、機器故障、零件報廢或返工等，需要對動態事件做 出動態調整，進行重新調度，否則，會導致生產無法順利進行；另一方面，在求解動態柔性作 業車間調度問題是，精確的數學方法，例如：分支界定法、整數規劃、拉格朗日鬆弛法等，是 過去經常被使用，然而，精確數學方法只能求解小規模的柔性作業車間調度問題，與實際生 產數據無法匹配，從而造成實際中無法使用。
[0005] 基於多階段智能優化算法的動態不確定柔性作業車間調度方法是有效利用柔性 作業車間具有加工機器可選性和工件工藝路線柔性化的特點，充分考慮在初始調度和重調 度過程中調度人員具有豐富經驗的作用，在整個動態調度與控制過程中建立多個階段，並 且在每個階段藉助於智能優化算法進行優化求解，加速處理動態事件的響應時間，提高重 調度方案的可行性和穩定性。
【發明內容】
[0006] 針對上述情況，為克服現有技術之缺陷，本發明之目的在於提供一種基於多階段 智能優化算法的動態柔性作業車間調度控制方法，有效解決了動態調度過程處理事件重調 度時策略單一的問題。
[0007] 其解決的技術方案是，本發明基於多階段智能優化算法的動態柔性作業車間調度 控制方法，包括：
[000引第一階段；初始調度方案的優化與選擇。所述第一階段包括兩個步驟：
[0009] 步驟一；根據車間生產任務、工件工藝信息和車間工具機設備信息，通過自適應遺傳 算法產生具有目標值相同的多個初始調度方案集；
[0010] 步驟二；依據工具機設備信息，調度人員根據車間生產任務、工件工藝信息和車間機 床設備信息從步驟一由自適應遺傳算法產生的具有目標值相同的多個初始調度方案集中 選擇一個調度方案作為初始調度方案，並執行；
[0011] 第二階段；判斷車間工具機故障，並記錄車間工具機故障信息。所述第二階段包括兩個 步驟：
[0012] 步驟判斷是否有車間工具機故障事件的發生，如果沒有車間工具機發生故障繼續 執行初始調度方案；否則，開始執行步驟四；
[0013] 步驟四：記錄車間工具機故障事件發生時刻，各臺故障車間工具機上正在加工W及後 續未加工的工序信息，並獲取故障車間工具機的相關信息，尤其是故障車間工具機的維修時間 f目息；
[0014] 第=階段；進行重調度，確定重調度執行方案。所述第=階段包括=個步驟：
[0015] 步驟五：判斷是否必須啟動重調度，如果需要啟動重調度，開始執行步驟6 ;否則， 繼續執行初始調度方案；
[0016] 步驟六：根據故障車間工具機上的正在加工W及後續未加工的工序信息，利用自適 應遺傳算法產生重調度生產調度方案集；
[0017] 步驟走；調度人員根據車間生產任務、工件工藝信息、車間工具機設備信息和故障車 間工具機上的正在加工W及後續未加工的工序信息，從步驟六的利用自適應遺傳算法產生的 重調度生產調度方案集中，選擇一個調度方案作為執行方案。
[001引本發明在整個動態調度與控制過程中建立多階段，並且在每個階段藉助自適應遺 傳算法進行優化求解，在不同階段採取不同的執行方案，加速處理動態事件的響應時間，提 高重調度方案的可行性和穩定性，W獲得高質量的適合車間實際生產的調度方案，縮短生 產時間。
【專利附圖】
【附圖說明】
[0019] 圖1為本發明實現對動態柔性作業車間調度基於多階段智能優化算法的控制方 法的流程圖。
[0020] 圖2為本發明的一個柔性作業車間調度問題測試數據表。
[0021] 圖3為本發明的5種車間工具機故障動態信息數據表。
[0022] 圖4為本發明的實施例中方案a圖。
[0023] 圖5為本發明的實施例中方案b圖。
[0024] 圖6為本發明的實施例的情景3中方案a在時刻5重調度的甘特圖。
[0025] 圖7為本發明的實施例的情景5中方案b在時刻5右移策略的甘特圖。
[0026] 圖8為本發明的實施例的情景5中方案b在時刻5重調度的甘特圖。
【具體實施方式】
[0027] W下結合附圖，對本發明的【具體實施方式】作進一步詳細說明。
[002引現結合圖1至圖8所示，對基於多階段智能優化算法的動態柔性作業車間調度控 制方法中的=階段中採用的自適應遺傳算法求解步驟，包括：
[0029] 步驟1 ;設置算法參數，包括種群數目、迭代次數、交叉概率、變異概率W及a、0 的值；
[0030] 步驟2 ;染色體編碼，隨機產生初始種群；
[003U 根據FJSP問題特點，需要解決車間工具機選擇和工序排序選擇兩個子問題，採用車 間工具機染色體和工序排序染色體兩段融合的染色體整數編碼方法；
[0032] 車間工具機染色體確定每道工序的加工車間工具機，車間工具機染色體長度等於總的工 序數，車間工具機染色體上的基因按照工件工序的先後約束順序排列，每個基因位上的整數 代表該工件工序可選車間工具機集中的加工車間工具機的序號，而不是車間工具機號，假設一個 車間工具機染色體為[121323121211]，長度為12,其中，工序〇12的可選車間工具機集Mi2= {M2， M4,Mg}，那麼可選車間工具機集中的順序號分別為{1，2, 3}，車間工具機染色體中工序〇12對應基 因位上的值為2,即代表在第2臺車間工具機上進行加工，也就是車間工具機M4,而非車間工具機 M2;
[0033] 工序排序染色體採用基於工序的實數編碼方式進行編碼，每一個基因位的值用工 件號直接編碼，且每一個基因位的值出現的次數等於該工件的工序數，工序排序染色體長 度等於所有工序的總和，在工序排序染色體解碼時，染色體從左到右依此進行編譯，工件號 出現的順序表示該工件工序間的先後加工順序，即第一個工件號表示該工件的第一道工 序，第二個該工件號表示第二道工序，W此類推，保證了同一工件工序的先後約束，假設有4 個工件需要加工，工件11^2^3^4分別用工件號1、2、3、4代替，每個工件有^道工序，也就 是每個工件號出現3次，工序排序染色體長度為12,假設隨機產生一個工序排序染色體為 [134323421241]，對應的工序排序為{〇11, 〇31, 〇41, 〇32,化 1, 〇33, 〇42,化2, 〇12,化3, 〇43, O13};
[0034] 步驟3 ;對種群中每一個染色體進行解碼，計算個體適應度值；
[0035] 在對車間工具機染色體和工序排序染色體的解碼過程中，首先對車間工具機染色體進 行解碼，然後對工序排序染色體進行解碼，並且將工序排序染色體解碼成對應於車間工具機 選擇部分的活動調度，具體的解碼步驟如下：
[0036] 1)對車間工具機染色體從左到右依次讀取並轉換成車間工具機矩陣M和時間矩陣T， 對步驟2中給出的車間工具機染色體轉換後為：
[0037]
【權利要求】
1. 基於多階段智能優化算法的動態柔性作業車間調度控制方法，其特徵在於，包括： 第一階段：初始調度方案的優化與選擇。所述第一階段包括兩個步驟： 步驟一：根據車間生產任務、工件工藝信息和車間工具機設備信息，通過自適應遺傳算法 產生具有目標值相同的多個初始調度方案集； 步驟二：依據工具機設備信息，調度人員根據車間生產任務、工件工藝信息和車間工具機設 備信息從步驟一由自適應遺傳算法產生的具有目標值相同的多個初始調度方案集中選擇 一個調度方案作為初始調度方案，並執行； 第二階段：判斷車間工具機故障，並記錄車間工具機故障信息。所述第二階段包括兩個步 驟： 步驟三：判斷是否有車間工具機故障事件的發生，如果沒有車間工具機發生故障繼續執行 初始調度方案；否則，開始執行步驟四； 步驟四：記錄車間工具機故障事件發生時刻，各臺故障車間工具機上正在加工以及後續 未加工的工序信息，並獲取故障車間工具機的相關信息，尤其是故障車間工具機的維修時間信 息； 第三階段：進行重調度，確定重調度執行方案。所述第三階段包括三個步驟： 步驟五：判斷是否必須啟動重調度，如果需要啟動重調度，開始執行步驟6 ;否則，繼續 執行初始調度方案； 步驟六：根據故障車間工具機上的正在加工以及後續未加工的工序信息，利用自適應遺 傳算法產生重調度生產調度方案集； 步驟七：調度人員根據車間生產任務、工件工藝信息、車間工具機設備信息和故障車間機 床上的正在加工以及後續未加工的工序信息，從步驟六的利用自適應遺傳算法產生的重調 度生產調度方案集中，選擇一個調度方案作為執行方案。
2. 根據權利要求1所述的基於多階段智能優化算法的動態柔性作業車間調度控制方 法，其特徵在於，對基於多階段智能優化算法的動態柔性作業車間調度控制方法中的三階 段中採用的自適應遺傳算法求解步驟，包括： 步驟1:設置算法參數，包括種群數目、迭代次數、交叉概率、變異概率以及a、0的 值； 步驟2 :染色體編碼，隨機產生初始種群； 車間工具機染色體確定每道工序的加工車間工具機，車間工具機染色體長度等於總的工序 數，車間工具機染色體上的基因按照工件工序的先後約束順序排列，每個基因位上的整數代 表該工件工序可選車間工具機集中的加工車間工具機的序號，而不是車間工具機號，假設一個車 間工具機染色體為[1 2 1 3 2 3I2I2I1]，長度為12,其中，工序O12的可選車間工具機集 M12 ={M2，M4，MJ，那麼可選車間工具機集中的順序號分別為{1，2，3}，車間工具機染色體中工序 O12對應基因位上的值為2,即代表在第2臺車間工具機上進行加工，也就是車間工具機M4，而非 車間工具機M2; 工序排序染色體採用基於工序的實數編碼方式進行編碼，每一個基因位的值用工件 號直接編碼，且每一個基因位的值出現的次數等於該工件的工序數，工序排序染色體長度 等於所有工序的總和，在工序排序染色體解碼時，染色體從左到右依此進行編譯，工件號出 現的順序表示該工件工序間的先後加工順序，即第一個工件號表示該工件的第一道工序， 第二個該工件號表示第二道工序，以此類推，保證了同一工件工序的先後約束，假設有4個 工件需要加工，工件1、J2、J3、J4分別用工件號1、2、3、4代替，每個工件有三道工序，也就 是每個工件號出現3次，工序排序染色體長度為12,假設隨機產生一個工序排序染色體為 [1 3432342124 1]，對應的工序排序為{On，031，041，032, 021，033, 042 , 022 , 012 , 023,O43 >0Isl； 步驟3 :對種群中每一個染色體進行解碼，計算個體適應度值； 在對車間工具機染色體和工序排序染色體的解碼過程中，首先對車間工具機染色體進行解 碼，然後對工序排序染色體進行解碼，並且將工序排序染色體解碼成對應於車間工具機選擇 部分的活動調度，具體的解碼步驟如下： 1) 對車間工具機染色體從左到右依次讀取並轉換成車間工具機矩陣M和時間矩陣T，對步 驟2中給出的車間工具機染色體轉換後為：
車間工具機矩陣M和時間矩陣T中，每行代表工件，每列代表工序，如工序O12的加工機器 為機器M4，對應的加工時間為2 ; 2) 對工序排序染色體從左到右依次讀取，將每個工序排序按照對應的車間工具機矩陣M 和時間矩陣T，轉換成活動調度，並得到最後一個工序的完成時間，也就是該調度方案的完 工時間； 3) 重複步驟1)和步驟2)對種群中所有車間工具機染色體和工序排序染色體進行解碼， 並對個體適應度值進行比較； 步驟4 :更新外部精英庫中的優良解； 在外部精英庫更新時，基於海明距離的更新方法，優先比較目標值，目標值好的個體替 換目標值差的個體；當目標值相同時，比較個體之間的海明距離，若海明距離為〇,則不替 換；若海明距離不為0,替換記憶庫中的最差個體； 步驟5 :判斷是否滿足最優個體的目標值達到預先設定的目標值或者迭代的代數超過 了設定的迭代次數的條件，如果滿足則輸出外部精英庫中的優良解；否則，轉到步驟6 ; 步驟6 :選擇操作； 採用錦標賽選擇（tournamentselection)方法，每次從種群中選擇3個個體進行適應 度比較，將適應度較高的個體插入到交叉池中，如此循環直到填滿交叉池； 步驟7 :自適應交叉操作； 交叉率的設定採用自適應的方式，根據算法迭代次數進行變化，公式（1); Pc=pcs (1-Curlter/Maxlter) (I) (1)式中，Pes表示設定的交叉率初始值，CurIter表示當前迭代次數，MaxIter表示最 大迭代次數； 步驟8:自適應變異操作； 米用自適應的變異概率： Pm=pms (1-Curlter/Maxlter) (2) 式中，Pms表示設定的變異率初始值，CurIter表示當前迭代次數，MaxIter表示最大迭 代次數； 步驟9 :通過選擇、交叉、變異操作後得到下一代群體，轉到步驟3,循環執行後續操作， 直到算法滿足停止條件。
【文檔編號】G06Q10/06GK104504540SQ201510015487
【公開日】2015年4月8日 申請日期:2015年1月13日 優先權日:2015年1月13日
【發明者】張國輝, 張理濤, 張凌傑, 陳洪根, 王永成, 毛學港, 王佳佳 申請人:鄭州航空工業管理學院