考慮機台可用限制下最小化完工時間與共同到期日之絕對偏差

Abstract

本研究探討考慮機台可用能力限制下，以最小化完工時間與共同到期日之絕對偏差(sum of absolute deviations, SAD)為目標的排程問題。此績效評估指標乃闡述即時化生產系統之核心概念：一個理想的作業排程為所有的訂單皆可準時在指定交期日完工，不必要的在製品與製成品存貨應徹底排除，以達到成本最小化之決策能力。同時將提早與延遲完工納入考量的排程模式目前已受到廣泛地討論。然而，大多數的相關研究皆假設機台為可連續運轉。在製造實務上，定期性的維護保養作業或機台故障皆可能使得加工中斷。此時若無一妥善的排程規劃可能使得整體生產系統效能與顧客服務水準大為降低。有鑑於此，我們需將機台可用能力限制納入評估以訂定最佳機台排程策略。 共同到期日SAD問題之計算複雜度已被證明為NP-Complete，機台可用能力限制的考量將使其困難度更為提高。因此，我們首先分析此問題所具備之最佳解特性，以縮減需考慮的排程組合；接著以最佳解特性為基礎建構兩種求解模式：混合整數線性規劃模型與動態規劃演算法。我們將討論如何運用四種代表不同排程決策思維的二元變數來建構數學模式，並指出藉由將搜尋過程聚焦於某特定凌駕區域中，動態規劃所需之計算量將可大幅降低。最後，我們評估運用這些方法於不同測試規模和情境下的求解績效，和描述某些可在多項式時間內求解之問題特例。實驗結果顯示，在單機排程模式中動態規劃演算法表現較具優勢；而在平行機台模式中，混合整數線性規劃模型與動態規劃演算法則具互補性。

This study addresses the problem of scheduling independent jobs with limited machine availability to minimize the sum of absolute deviations (SAD) of job completion times from a common due date. This performance measure is compatible with the just-in-time production philosophy, which espouses the notion that an ideal schedule consists of all customer orders can be fulfilled exactly on the due date. Both earliness and tardiness should be discouraged in order to minimize the costs associated with these two measures. It is well known that the recognition version of the common due date SAD problem has been proven to be NP-complete in the ordinary sense even for the single-machine case. The existence of availability constraints tends to make it considerably more difficult to solve. To begin with, we develop some general insights into this complicated problem. Several dominance properties are provided to simplify the search for an optimum. Then, based on the results of our analysis, we propose two exact methods: mixed integer linear programming and dynamic programming. These methods are tested intensively on a large data set and their performances are analytically compared and evaluated. Finally, we describe some special cases of the problem which are polynomial solvable. The numerical experiments show that the dynamic programming method outperforms the mixed integer linear programming method in single-machine model, and these two methods are complementary in parallel-machine model.