一個針對長時間排程問題的分段處理演算法

Abstract

在製造系統中，排程問題是最基本卻也是最困難的問題之一。大部份的排 程問題皆屬於NP-Complete類的問題，所以大多數的工廠是利用啟發式排 程法則或是有經驗的排程員來解決排程問題，如此無法掌握整個工廠的生 產目標以及運作狀況，因此改善排程方法有其迫切的需要。以整個系統為 考量的排程研究，一直都在追求一個有效率且能求出良好排程解的方法。 結合拉格朗日鬆散法與照單排程法可以用來處理整體系統考量下的製造系 統排程問題，對於小型的排程問題可以獲得非常好的近似最佳排程解。然 而使用此法處理較長時程的排程問題時，很難在很短的時間內求出很好的 近似最佳排程解，因此我們提出分段處理演算方法來處理較大型的排程問 題，用來改善排程結果與排程的效率。本論文中，我們先將排程問題適當 的轉換成最佳化問題，然後以拉格朗日鬆散法配合照單排程法來解決此類 問題。針對長時間的排程問題，我們採用分段處理演算法有效率地求得近 似最佳排程解。 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 belongs to the NP-Complete combinatorial problems, for which the development of efficient optimum-producing polynomial algorithm is unlikely. Therefore, practical schedules are commonly generate by simple heuristic algorithm or experienced schedulers. The interaction of jobs, as they complete for limits resources, is not visible, and overall shop goLagrangian relaxation technique has been used to solved scheduling problems. After obtaining the dual solution, list- scheduling method is applied to produce feasible schedule. We can use this method to obtain better results for small-size scheduling problems, but we may not obtain better result efficiently for the long-horizon scheduling problems. This likely comes from the ineffectiveness of the list-scheduling approach for constructing a feasible schedule and the computation complexity of the dynamic prog The simulation results show that the sectional-processing algorithm can improve results and efficiency for the long-horizon scheduling problems.