混合式流程工廠排程之巨集啟發式演算法的比較

Abstract

在流程工廠排程問題(Flow shop scheduling；FS)中，若一個工作站有多部機台，而且一個作業可能需要多部機台合作才能加工，此種問題稱之為混合式流程工廠排程問題 (Hybrid flow shop scheduling problem；HFSP)。針對HFSP問題，過去已有許多演算法，目前以Ying & Lin (2006)的演算法表現較佳，本研究結合共識因子和田口方法提出多種巨集演算法(meta-heuristics)，希望找出一種演算法，能在績效上改進Ying & Lin (2006)的演算法。本研究使用120個案例，分成12種情境實驗測試。與Ying & Lin (2006)演算法相比，本研究所發展的演算法僅在42%的情境表現較佳，卻在58%的情境中表現較不如過去的演算法。

A hybrid flow-shop scheduling problem (HFSP) has two distinct features. A workstation may include more than one machine; and an operation may require more than one machine to process it. Much literature on HFSP has been published, in which the algorithm proposed by Ying & Lin (2006) is the most leading one. We applied the notions of consensus and Taguchi genetic operators and proposed various meta-heuristics algorithms. Extensive numerical tests that include 120 problem instances, categorized into 12 scenarios, have been carried out. Compared with the algorithm proposed by Ying & Lin (2006), our algorithm excel in 42% scenarios and lose in 58% scenarios.