零工式排程之巨集啟發式演算法的比較

Abstract

零工式排程問題(Classical Job Shop Scheduling Problem；JSSP)是一個已經研究很久的問題，也已有許多文獻發表，目前以Huang & Liao (2006)的演算法表現最佳。本研究結合共識因子和田口方法提出多種巨集演算法(meta-heuristics)，希望找出一種演算法，能在績效上改進Huang & Liao (2006)的演算法。本研究使用19個案例實驗測試，贏了5個(26%)，平手7個(37%)，輸了7個(37%)。

The classical job shop scheduling problem (JSSP) has been studied for decades. Much literature has been published, and the algorithm proposed by Huang & Liao (2006) is the most leading one. We applied the notions of consensus and Taguchi genetic operators and proposed various meta-heuristics algorithms. Numerical tests that include 19 problem instances have been carried out. Compared with the algorithm proposed by Huang & Liao (2006), our algorithm excel in 5 problem instances, and has a tie in 7 problem instances, and lose in 7 problem instances.