一個以隨機搜尋為基礎的解排程問題的拉格朗日鬆散法

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 generated by simple heuristic algorithm or experienced schedulers. The interaction of jobs, as they compete for limits resources, is not visible, and overall shop goal such as on-time delivery of jobs are beyond control. Thus, there is a press need for improving the scheduling operation in complex manufacturing environment. Combination of Lagrange relaxation method and list-scheduling method can be used to tackle the manufacture system scheduling problem under consideration of the whole system, and the almost optimal solution is available for the small scheduling problem. Nevertheless, it’s not ideal enough for more complex problems. Therefore, we use sectional processing method to prevent the false case and herewith it can also improve the operation of time and cost function. Besides, after adding the concept of random search and basing on the physical view of Lagrange multiplier sensitivity to do initial guess of each Lagrange multiplier, we could get the optimal value of various areas to improve the whole scheduling. In the meantime, it’s also possible to obtain the original point close to the optimal solution and save the calculating time. In this thesis, we first change the scheduling problem to the optimization problem properly, and then expand Lagrange relaxation method to accommodate to list-scheduling method to solve this kind of problem. Moreover, we combine section processing method and random search together, too. It’s an obvious improvement in the operation of time and cost function.