動態規劃法解排程問題之研究

Abstract

分枝定限法可能是未來排程問題真正獲得最適當答案的唯一技巧，但是分枝定限法的 計算效率，卻深受下限值與最初試行解品質的影響。由於排程作業所習用的衡量標準 ，與成本的關係絕少切合線的關聯，使得找出好的下限值與最初試行解，倍增困難。 反之，使用動態規劃法來解目標函數值與抉擇變數無線性關聯的問題，便極為適當。 本研究結合作業總耗時，遲誤時間，與特定時段付款條件特別有利的目標，整合成一 排成本目標函數，採用動態規劃法建構模式以求解，並與分枝定限法相比較，來驗證 模式的解題速率。 此外，在雙機流程型排程問題的研究裡，以平均作業總耗時為目標的問題，一直未能 有所進展，本研究亦嘗試以動態規劃法，結合分枝定限法，對此問題求解，並融入探 適法，找出較佳的最初試行解，以改善計算速率。