差異工件流水車間批調度問題的求解

朱頎，陳成棟，陳華平

中國科學技術大學 管理學院，合肥 230026

差異工件流水車間批調度問題的求解

朱頎，陳成棟，陳華平

中國科學技術大學 管理學院，合肥 230026

1 引言

差異工件流水車間批調度問題是工業生產中一類典型的調度問題。它是對傳統流水車間問題的進一步擴展，即在流水車間的每個階段均是批處理機。求解該問題分為兩個步驟：首先工件遵循特定分批規則成批，然后將形成的批按照相同的加工順序在各批處理機上逐個進行加工。這類組合優化問題在實際應用中很常見，如電子工業的環境應力篩選過程就可抽象為一個典型的流水車間批調度問題。環境應力篩選由半導體工業的老化實驗發展而來，整個產品需要在用戶設定的不同環境下進行測試，每個篩選實驗箱可以看做一個批處理機，數量由待測試的裝配車間的數量以及特定裝備車間的測試數量決定。該問題的研究具有很好的現實意義。

目前關于求解流水車間批調度問題的研究大部分限于兩臺機器的情況，求解目標多為最小化制造跨度（Makespan）。如Mirsanei等[1]在ARA和FLA兩種啟發式算法以及模擬退火算法（SA）的基礎上提出ARSA和FLSA兩種改進算法；Purushothaman等[2]采用遺傳算法（GA）進行了求解；Alebachew等[3]在工件順序的模糊調度模型基礎上提出了基于GA的求解思路；Liao等[4]采用禁忌搜索算法（TS）對問題進行了求解，并與混合整數線性規劃進行了比較；針對多機器的情況（即3臺批處理機及以上），Ali等[5]提出了一種改進的混合整數線性規劃方法（Mixed Integer Linear Formulation），在小規模工件的情況下進行了求解。……