最小化訂單總完工時間之平行機台排程問題

Abstract

本研究探討在多部彈性之非相同平行機台下，最小化訂單總完工時間之訂單排程問題。研究目的為找出訂單中工件的最佳指派使得訂單總完工時間最小。我們驗證了兩項最佳解性質，把決策拆成兩階段並藉此建構了四個近似最佳解的演算法。在模擬實驗中我們驗證本研究所提出的演算法的有效性，並找出幾個影響演算法績效的因素。

We study the order scheduling problem under the non-identical parallel machines environment in the fully flexible case. Our goal is to minimize total order completion time and the decision is to assign all jobs to all machines. We first show two lemmas for optimal solution and separate our problem into two stages based on these lemmas. Then, we develop a series of two-stage heuristics to solve our problem. Finally, we implement numerical studies to verify the performance of our heuristics, and find out several factors that influence the performance of heuristics.