開放車間排程問題（OSSP）在製造業和物流領域幾乎無處不在——一個車間裡有多臺機器、多個作業，每個作業的每道工序可以在任意空閒機器上完成，目標是最小化總完工時間（makespan）。這個問題看起來直觀，但計算上卻是NP-hard，隨著作業和機器數量的增加，精確求解很快變得不可行。傳統上，工程師依賴排程規則（如SPT、LPT）或元啟發式演算法（如遺傳演算法、模擬退火），但這些方法往往需要大量人工調參，且大規模下質量難以保證。
Transformer+強化學習：新思路解決老問題
最近arXiv上這篇論文，把Transformer架構和深度強化學習結合了起來。作者並沒有設計複雜的狀態編碼，而是將每個作業的加工時間矩陣直接輸入到一個編碼器-解碼器結構的Transformer中，通過多注意力頭捕捉作業與機器之間的相互依賴關係。強化學習部分則用策略梯度方法訓練模型，使其學會順序地指派工序到機器，目標是最終makespan最小。
這個思路的一個自然優勢是：模型完全是資料驅動的，不需要人工特徵或領域知識。只要給一組加工時間，它就能端到端地輸出一個完整排程方案。聽起來有點玄，但實際跑下來的結果讓人眼前一亮。
實驗結果與泛化能力：小樣本訓練，大規模應用
訓練是在經典的Taillard基準例項上進行的，規模從4x4到10x10。訓練後的模型在驗證集上生成的排程，其makespan與已知最優解的偏差通常在15%-30%之內。這個數值相比精確求解差得遠，但考慮到模型是在極小規模上訓練的，且完全依賴資料學習，其實已經相當有競爭力。
更值得關注的是泛化能力：研究者直接將訓練好的模型應用到隨機生成的大規模例項上（40x40，甚至100x100），不做任何引數調整或重訓練。與SPT、LPT、MWKR、EST四種經典排程規則相比，Transformer模型在多數規模下均能取得更優的makespan，尤其在大規模問題上優勢更為明顯。這暗示模型可能學習到了一些超越簡單優先順序規則的全域性策略。
現實意義與侷限
這項研究對工業排程從業者意味著什麼？目前來看，離直接替換現有系統還有距離。15%-30%的最優解差距在要求嚴格的生產環境中可能不夠用，但作為一種初始解生成器或啟發式的混合元件，它已經展現了實用潛力。對於運籌優化領域的研究者，這篇工作提供了一個清晰的基線：Transformer在組合優化問題上可行，且泛化性比想象中好。
當然，侷限也很明顯：模型只在單一目標（makespan）上優化，而實際排程往往需要同時考慮交期、能耗、機器負載均衡等多目標。此外，當前實驗侷限於Taillard風格例項，現實資料中的噪聲和動態擾動尚未考慮。
實用建議：如果你正為排程問題發愁，可以關注作者是否會開源模型和程式碼，嘗試在自己的小規模資料集上跑一跑。但別指望它直接給出最優解——更合理的用法是作為快速近似器，再搭配區域性搜尋進行精調。另一方面，留意該領域後續的多目標擴充套件和魯棒性研究，那才是真正落地的前奏。
總的來說，這篇論文讓我們看到：即便在最傳統的運籌優化領域，深度學習也能找到自己的位置。它不完美，但方向值得跟蹤。
評論
暫無評論
成為第一個評論的人