圖靈學院
科楠
2024-11-22
前言
在現今高度競爭的製造環境中,企業必須不斷優化生產流程才能保持競爭力。整合批量和作業生產線排程問題 (lot-sizing and job shop scheduling problem, LSJSSP) 是製造業中常見且極具挑戰性的問題,需要同時決定產品的生產批量和生產排程,以最小化生產、庫存和設置成本。傳統方法在處理作業生產線 (job shop
, JS) 環境下的批量和排程問題 (Lot-sizing and scheduling, LSS) 時,常因簡化的容量計算和無法有效處理JS環境的複雜性而遇到瓶頸。我們圖靈學院近期將針對如何使用演算法或AI的方式在解決製造業在生產上所遇到的瓶頸相關研究論文,提供台灣製造業在數位轉型及精實生產上提供一些解決的思考方向。
近期一篇發表於國際期刊《生產研究》的論文 "A cooperative coevolutionary hyper-heuristic approach to solve lot-sizing and job shop scheduling problems using genetic programming",提出了一種結合模擬式貪婪演算法和協同共演化基因規劃超啟發式演算法 (CC-GP-HH) 的創新方法,為解決 LSJSSP 問題提供了新的解決方案。
克服傳統方法限制的模擬式貪婪演算法(greedy heuristic)
傳統方法多採用簡單的容量加總來評估可行性,忽略了作業生產線環境中,不同產品的操作可能共用相同機器的複雜性,導致容量估算不足,產生不可行的排程方案。 論文中提出的模擬式貪婪演算法,透過以下步驟克服了這些限制:
1.初始生產計劃: 根據淨需求 (需求減去上期庫存) 定義每個產品在特定期間的生產數量。
2.增加批量程序: 若特定期間存在剩餘產能,則利用成本節約指數 (CSI) 評估增加批量所能節省的成本,並嘗試將未來期間的需求提前生產,以降低總成本。 此時,必須進行可行性檢查以確保增加批量後不會超出產能限制。
3.回溯機制: 若特定期間的產能不足以滿足所有需求,則啟動回溯機制,將部分生產數量移至較早的期間生產。 首先,演算法會嘗試將超出的生產數量添加到現有批量中,以避免額外的設置成本。如果仍然存在未分配的生產數量,則會在較早的期間創建新的批量進行預先生產。
4.基於離散事件模擬 (DES) 的可行性驗證: 這是該演算法最核心的創新之處。 不同於傳統方法依賴簡單的容量計算,此方法透過 DES 建構詳細的排程,並模擬生產過程,精確地評估每個時間點的資源使用狀況,從而更準確地判斷方案的可行性。即使在複雜的作業生產線環境中,也能確保生成的排程方案切實可行。
CC-GP-HH架構如何透過個體適應度演化規則
CC-GP-HH 架構包含兩個模組:LSSP 生成器和適應度評估器。 LSSP 生成器利用基因規劃演化批量規則 (LSR) 和作業排序規則 (JSR),並將兩者組合成 LSSP (批量和排程策略)。適應度評估器使用 DES 模組和模擬式貪婪式啟發式演算法來評估 LSSP 的適應度 (平均總成本)。 CC-GP-HH 架構透過以下步驟,利用個體 (LSSP) 的適應度來演化 LSR 和 JSR:
1.生成初始種群: CC-GP-HH 架構包含兩個子種群,分別代表 LSR 和 JSR。初始種群由隨機生成的 LSR 和 JSR 個體組成。
2.協同演化: 來自兩個子種群的個體配對組合成 LSSP,並利用模擬式貪婪演算法和 DES 模擬來評估其在訓練集上的平均總成本,作為該 LSSP 的適應度。
3.選擇與繁殖: 根據適應度排名,選擇表現較好的 LSSP 進行繁殖,透過基因規劃的交叉和變異操作產生新的 LSR 和 JSR 個體。
4.更新種群: 將新產生的個體加入子種群,替換表現較差的個體,形成新的種群。
5.重複步驟2-4: 重複協同演化、選擇與繁殖的過程,直到達到預設的世代數或停止條件。
透過此演化過程,CC-GP-HH 架構不斷優化 LSR 和 JSR,最終得到針對特定問題或通用場景的最佳規則組合,有效提升貪婪演算法的求解品質。
特定問題規則與通用規則的效能比較
論文透過兩個實驗探討了專門針對特定問題類別演化的規則與通用規則的效能差異:
此篇論文中作者如何評估所提方法的效能?
作者們透過一系列的計算實驗來評估所提出的模擬式貪婪啟發式演算法和協同共演化基因規劃超啟發式演算法 (CC-GP-HH) 的效能。 他們主要關注以下幾個方面:
1. 與Cplex的比較
2. 與現有規則的比較
3. 執行時間比較
4. 穩健性分析
5. 大型實例的測試
結論
作者透過多種指標和實驗設計,全面評估了所提出的方法的效能。 實驗結果表明,模擬式貪婪啟發式演算法和 CC-GP-HH 方法在求解效率、解的質量和穩健性方面都優於現有方法,特別是在處理大型實例時更具優勢。
論文提出的模擬式貪婪演算法結合 CC-GP-HH 架構,有效克服了傳統方法在處理 JS 環境下 LSS 問題的限制,並透過演化過程,獲得了效能更佳的特定問題規則和通用規則。 這為解決複雜的生產排程問題提供了新的思路和方法。未來研究可以進一步探索使用代理模型加速訓練過程、優化基因規劃演算法的設計,並將該方法應用於更複雜的動態製造環境和實際案例。
原文來源:
Zeiträg, Y., Rui Figueira, J., & Figueira, G. (2024). A cooperative coevolutionary hyper-heuristic approach to solve lot-sizing and job shop scheduling problems using genetic programming. International Journal of Production Research, 62(16), 5850–5877. https://doi.org/10.1080/00207543.2023.2301044
Copyright © 2024 利創智能科技股份有限公司 All rights reserved.
Replace this text with information about you and your business or add information that will be useful for your customers.