多部彈性機台下最小化延遲訂單數問題

Abstract

本研究在最小化延遲訂單數的目標下，探討多部彈性機台的訂單排程問題。首先我們研究問題的複雜度並證明了此問題是NP-complete。然後證明了兩項性質來建構數學模型。同時，我們根據此二性質建構了兩種分別以LPT與BIN排法為基礎進行指派的近似最佳解演算法。最後，在模擬實驗中驗證本研究所提出之演算法的有效性。

We consider the order scheduling problem on fully flexible machine environment. Our objective is to minimize number of late orders. We show that our problem, PFm | πk | ∑Uj , is NP-complete. We also show two properties for formulating the mathematical model of our problem. Then, we develop two types of two-stage heuristics based on these two properties to solve our problem. These two types of heuristics are based on the assignment of LPT rule and BIN rule, respectively. Finally, numerical studies are implemented to validate the performance of our heuristics.