一個複合成本增量函數法在排程問題上的應用

Abstract

在製造系統中，排程問題是最基本卻也是最困難的問題之一。大部份的排程問題皆屬於NP-Complete 類的問題，所以在大多數的工廠是利用啟發式排程法則或是有經驗的排程員來解決排程問題，如此無法掌握整個工廠的生產目標以及運作狀況，因此改善排程方法有其迫切的需要。 Peter B. Luh在[4]中，提出以拉格朗日鬆散法結合照單排程來求解以整體系統為考量的排程問題，然而我們由次佳解控制參數的觀念可以瞭解到，利用啟發式方法來求得次佳解有值得改善的地方，因此我們針對照單排程來進行改善，以期能得出較佳的排程解。 本論文中，我們提出了複合成本增量函數法來改善照單排程，利用複合成本增量函數法，我們可以求得較佳的操作程序的加工順序，進而獲得一個較佳的排程解。

Scheduling is one of the most basic but the most difficult problem to be solved in the manufacturing system. The difficulty is that the most scheduling problems belong to the NP-Complete combinatorial problems, for which the development of efficient optimum-producing polynomial algorithm is unlikely. Therefore, practical schedules are commonly generaterd by simple heuristic algorithm or experienced schedulers. The interaction of jobs, as they complete for limited resources, is not visible, and overall shop goal such as on-time delivery of jobs are beyond control. Thus, there is a need for improving the scheduling operation in complex manufacturing environment. Lagrangian relaxation technique has been used to solve scheduling problems. After obtaining the dual solution, list-scheduling method is applied to produce feasible schedule. However, according to the idea of controlled parameters in suboptimal solution, we realize that using heuristic method to solve schedule problem have some room to improve. Therefore we try to improve list schedule and hope to get a better schedule result. In this paper we propose the compound incremental cost function method to improve list schedule. Using compound incremental cost function method, we can obtain a better schedule result.