總延遲時間最小之動態單機排程問題

本研究擬針對動態單機排程同時考慮最佳化與啟發式演算法，追求總延遲時間最小化為目標。最佳化方法包括分支界限演算法、限制規劃(constrained programming)和整數規劃模式。研究中之基礎定理與優先順序關係將由相關文獻中衍生推演提出，而新提出的分支界限演算法中，我們考慮同時先將兩個工作數固定安排於首尾兩端，剩餘未安排的排程位置在依相關定理指派工作。相同定理與優先順序關係也會被應用於限制規劃模式裡。這三個最佳化的方法都必須透過實驗測試其效率，其過程與運算結果將會在研究中詳細說明。我們也會提出一啟發式演算法，其實驗結果也會在研究中詳述。

關鍵字

啟發式方法；單機；動態；最佳化方法；總延遲時間

並列摘要

This paper considers both exact and heuristic algorithms to minimize total tardiness on a single machine with unequal release dates. The exact approaches including a branch and bound algorithm, a constrained programming model, and an integer programming model. Based on the theorems and precedence relationships developed in the literatures and established in the paper, the branch and bound algorithm considers two unscheduled jobs simultaneously by fixing them respectively in both end positions. The same theorems and relationships are applied to constrained programming model. These three exact approaches are tested and detailed computational results are given. We also propose a heuristic algorithm and their results are reported.

並列關鍵字

the heuristic ； dynamic ； the optimization ； single machine ； total tardiness

參考文獻

[1] Abdul-razaq, T. S., Potts, C. N., and Van Wassenhove, L. N., 1990, A survey of algorithms for the single machine total weighted tardiness scheduling problem, Discrete Applied Mathematics, 26, 235-253.

[2] Alidaee, B., and Gopalan, S., 1997, A note on the equivalence of two heuristics to minimize total tardiness, European Journal of Operational Research, 96, 514-517.

[3] Akturk, M.S. and Ozdemir, D., 2000, An exact approach to minimizing total weighted tardiness with release dates, IIE Transactions, 32(11), 1091-1101.

[4] Akturk, M.S. and Yildirim, M.B., 1998, A new lower bounding scheme for the total weighted tardiness problem, Computers and Operations Research, 25, 265-278.

[5] Akturk, M.S. and Yildirim, M.B., 1999, A new dominance rule for the total weighted tardiness problem. Production Planning and Control, 10, 138-149.

國際替代計量

總延遲時間最小之動態單機排程問題

未授權

主題瀏覽