更深入探討LSJSSP問題的創新解法：模擬、共演化與規則效能
圖靈學院
科楠
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 建構詳細的排程，並模擬生產過程，精確地評估每個時間點的資源使用狀況，從而更準確地判斷方案的可行性。即使在複雜的作業生產線環境中，也能確保生成的排程方案切實可行。
圖 1. 提議的架構。Zeiträg et al., (2024)
CC-GP-HH架構如何透過個體適應度演化規則
CC-GP-HH 架構包含兩個模組：LSSP 生成器和適應度評估器。 LSSP 生成器利用基因規劃演化批量規則 (LSR) 和作業排序規則 (JSR)，並將兩者組合成 LSSP (批量和排程策略)。適應度評估器使用 DES 模組和模擬式貪婪式啟發式演算法來評估 LSSP 的適應度 (平均總成本)。 CC-GP-HH 架構透過以下步驟，利用個體 (LSSP) 的適應度來演化 LSR 和 JSR：
圖 2. 合作式共同演進解碼方案。Zeiträg et al., (2024)
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 架構的學習能力。
- 實驗二: 使用包含所有實例類別的訓練集演化通用規則。 結果顯示，通用規則雖然在某些特定問題上的表現略遜於特定規則，但在多數情況下仍優於現有規則，且在不同實例類別上表現穩定。
- 實驗結果表明，針對特定問題類別演化的規則在特定問題上具有優勢，但通用規則在面對多樣化問題時更具穩健性。選擇哪種規則取決於實際應用場景的需求。若問題類型單一且追求最佳效能，則特定規則更為合適；若問題類型多樣且注重穩定性，則通用規則更佳。
此篇論文中作者如何評估所提方法的效能？
作者們透過一系列的計算實驗來評估所提出的模擬式貪婪啟發式演算法和協同共演化基因規劃超啟發式演算法 (CC-GP-HH) 的效能。 他們主要關注以下幾個方面：
1. 與Cplex的比較
- 作者將演化規則的結果與使用 IBM ILOG CPLEX Optimization Studio 12.10.0 求解的混合整數規劃模型 (MIP) 的最優解進行比較。
- 由於 CPLEX 在求解某些實例時無法在一小時內找到最優解，因此作者使用 CPLEX 的相對 MIP 間隙來衡量演化規則的效能。
- 相對 MIP 間隙表示當前解與已知最佳解的接近程度。
2. 與現有規則的比較
- 作者還將演化規則與文獻中已知的批量規則和作業排序規則進行比較。
- 他們選擇了每個領域中最具代表性的五個規則，並將其應用於模擬式貪婪啟發式演算法中。
- 透過比較演化規則與這些現有規則的效能，作者可以評估 CC-GP-HH 方法是否能夠生成更有效的規則。
3. 執行時間比較
- 作者比較了 CPLEX、最佳現有規則和演化規則的平均執行時間。
- 結果顯示，模擬式貪婪啟發式演算法 (無論使用現有規則還是演化規則) 都能在不到一秒的時間內找到解，而 CPLEX 平均需要超過 1400 秒。
- 這突顯了模擬式貪婪啟發式演算法在求解效率上的優勢。
4. 穩健性分析
- 作者透過將演化規則應用於不同於訓練集的實例來評估其穩健性。
- 他們比較了針對特定問題類別演化的規則和通用規則在不同實例類別上的效能。
- 結果顯示，針對特定問題類別演化的規則在特定問題上表現最佳，但在其他實例類別上的效能會下降。
- 而通用規則在所有實例類別上都表現出更一致的效能，表明其具有更好的泛化能力。
5. 大型實例的測試
- 作者還測試了演化規則在大型實例（如 30×30×20）上的效能。
- 結果顯示，即使在處理大型實例時，演化規則仍然優於 CPLEX 和現有規則。
- 這表明 CC-GP-HH 方法和模擬式貪婪啟發式演算法具有良好的可擴展性。
結論
作者透過多種指標和實驗設計，全面評估了所提出的方法的效能。 實驗結果表明，模擬式貪婪啟發式演算法和 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
