蟻拓最佳化演算法求解具時窗限制的併批暨排程問題

Abstract

本研究針對具時窗限制的併批暨排程優化問題提出三種蟻拓演算求解方法，並詳細定義此種問題的數學模式。求解目標是在加工型別、加工先後順序、批次容量、及時窗限制之下得到最大化機台利用率。三種求解方法分別是: (1) 視時窗為軟式限制的TW-SOFT, (2) 視時窗為硬式限制的TW-HARD, 以及(3) 視時窗為軟式限制，但候選清單建構考量時窗為硬式限制的TW-semiHARD方法。本研究同時設計四種蟻拓演算流程中的啟發項計算式，以引導蟻拓求解。這四種啟發項分別是: (1) MSD， 期許一個加工作業完工之後，其接續加工步驟可立即開始加工；(2) MPD，加工時間相近的加工步驟併成一批可提高機台利用率；(3) MSPD，是MSD和MPD的混合值； 及(4) MSCmax，最小化相同加工型別的機台的最晚結束時間。本研究並研擬多個範例問題進行測試。內容比較五種不同的蟻拓法 (AS；ACS；ASelite；ASrank；及SDAS) 的求解效能同時設立不同求解模式和啟發項的組合。本研究開發一軟體系統實作提出的求解模式和啟發項。數據驗證結果顯示在求解具時窗限制的併批暨排程優化問題時結合TW-semiHARD模式和MSCmax 啟發項可以得到較好的結果。另外，使用ACS、SDAS、 ASelite、及ASrank等在仲裁者行動時針對求解至今最佳解額外添加費洛蒙的蟻拓最佳化演算法，可以得到較好的解 。

The mathematical model of a time window constrained batching and scheduling problem is rigorously defined. This problem is subject to process type constraints between operations and machines, precedence constraints between operations of a job, machine batch capacity limits, and the time window constraints between two successive operations. Three Ant Colony Optimization (ACO) solution construction procedures are developed for finding the maximum machine utilization in the time window constrained batching and scheduling problem. The first is the TW-SOFT computation mode that regards time window constraints as soft constraints. The second is the TW-HARD computation mode that regards time window constraints as hard constraints. The third is the TW-semiHARD computation mode that treats time window constraints as soft constraint, but considers them hard constraints in candidate set construction process. Four heuristic terms are proposed to guide the ACO solution search. Among them, the MSD aims to start an operation right after its predecessor is completed; the MPD aims to fully utilize time capacities of machines; the MSPD is a hybrid of the MSD and MPD; and the MSCmax aims to minimize the maximum completion time of machines. A software prototype system is developed to implement the proposed computation modes and heuristic terms. In the system, five ACO methods are implemented with the proposed ACO technique for the discussed problem. Several numerical tests are conducted to evaluate performances of the five implemented ACO methods, including the AS, ACS, ASelite, ASrank, and SDAS. Combinations of the proposed computation modes and heuristic terms are tested to evaluate their performances. Numerical results show that the TW-semiHARD mode and MSCmax heuristic term outperforms others. In addition, the ACS, SDAS, ASelite, and ASrank are better choices for the problem.