Enhanced MOPSL Framework

🧠 LLM Meta-Level 問題解決架構（版本2.0）

---

🎯 問題場景：Flexible Job Shop Scheduling Problem (FJSP)

• 工件需依序執行工序，每道工序可選多機台

• 排程需同時決定：

  • 機台選擇（Routing / Machine Selection, MS）

  • 作業排序（Scheduling / Operation Sequence, OS）

---

🧬 Enhanced MOPSL Framework 核心策略

對應 FJSP 的雙層結構，本架構以：

• **MS 相對機台編碼（MOPSL）**處理 routing 層決策

• OS Ready Set 限制排序處理 scheduling 層排序 並透過整合式染色體設計，實現兩層次決策的同步協調

---

✅ 染色體結構設計：Routing × Scheduling 結構

MS 編碼（Routing）

• 使用相對機台 index（合法集合內部索引）

• 自然避免非法操作與解碼錯誤

OS 編碼（Scheduling）

• 使用作業 job index 的 permutation 作為優先排序依據

• 解碼時僅允許 Ready Set 中工序參與排序，保證合法性與可執行性

---

🔁 解碼流程：雙層協同實現

• Routing：由 MS 相對 index 決定工序對應機台

• Scheduling：由 OS + Ready Set 解碼控制執行順序

• 解碼時交替執行兩層：確保每道工序安排在對應機台且滿足時間限制

---

🧠 解空間結構洞察與參數建議

解空間結構對突變率的影響：

編碼類型	解空間性質	突變率建議
傳統 MS/OS	Sparse	高（0.2~0.5）
Enhanced MOPSL (本架構)	Dense	低（0.05~0.2）

• Dense 空間：小變異 → 局部改善 → 穩定收斂

• Sparse 空間：需大幅突變以探索遠域區域

---

🧮 矩陣觀點與解空間稠密性量化

解構視角：

• 將解表示為解構矩陣：

  • MS ∈ M_{ij}: operation → machine (合法集合 index)

  • OS ∈ O_{ij}: operation 排序位置 / job index

解空間密度指標：

• 定義：

  • D = 1 / E[Δ(S)]，其中 Δ(S) 為鄰近解間的基因結構距離（如 L2 norm for MS + Kendall tau for OS）

• 計算流程：

  1. 抽樣一群解（如 30 組）

  2. 對每組進行單次突變（MS/OS 各測）

  3. 解碼並記錄 Cmax 差異與基因距離

  4. 計算平均 Δ → 推估解空間密度

---

🔧 演化操作設計

• cross_MS: 相對 index 區段交配（含逆序）

• cross_OS: 基於作業子集的導引排序交配

• mutation_MS: 融合最短處理時間、隨機與機台使用頻率偏好

• mutation_OS: reverse, insert, swap 三策略融合

---

🔍 Meta-Level 強化（VNS for Critical Chain）

• apply_vns_critical_OS: 調整 OS 排序，僅限於 Critical Path 操作

• apply_vns_critical_path: 在 Critical Path 中變更 MS 選擇（相對 index），提升瓶頸作業配置

---

📊 實驗設計 1：Routing × Scheduling 交互作用分析

2×2 Factorial 設計：

組別	MS 編碼	OS 排序
A	絕對	Ready Set 解碼
B	絕對	random 排序
C	相對 (MOPSL)	Ready Set 解碼
D	相對 (MOPSL)	random 排序

評估：

• 平均 / 標準差 Makespan

• ANOVA / 無母數交互檢定

---

📉 實驗設計 2：mutation 敏感度分析

條件：

• mutation rate 掃描範圍 0.01 ~ 0.5（step = 0.05）

• 比較 MS/OS 傳統架構與 Enhanced MOPSL 架構

評估：

• 每 rate 30 次測試，記錄解品質趨勢

• 擬合平滑曲線，觀察突變區穩定性與敏感閾值

---

📘 架構總結

• 針對 FJSP 雙層次結構，透過分離編碼 + 協同解碼有效解構並穩定搜尋

• 將結構知識融入演化策略，減少修復需求、提升演化穩定性與收斂性

• 實驗框架支援可視化、統計量化與多層驗證，可作為通用型排程架構基礎

---

📌 本架構具備「結構建模」＋「演化導引」＋「驗證可擴展性」，是具備理論意識與實作深度的 FJSP 優化策略平台。

=============================================
Even without experiment, the structural constraints of the MOPSL encoding—relative machine selection and ready-set-guided operation decoding—naturally form a denser and more topologically smooth solution space. Hence, a lower mutation rate is more suitable to exploit its local continuity, as opposed to traditional sparse MS/OS encodings that require higher mutation rates to maintain exploration capability.