結合分段處理及改善排單之照單排程法解長時間的排程問題

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. Lagrangian relaxation technique has been used to solve scheduling problems. After obtaining the dual solution, list scheduling method is applied to produce feasible schedule for minor scheduling problems. However, if we use the linear incremental cost function of list scheduling to evaluate nonlinear scheduling problems for deciding the prior orders during the operation procedure, we may distort the real situation, due to the sensitive-response feature in linear analytic method. For improving this distortion, we can apply the compound incremental cost function when we use the linear method to evaluate the nonlinear problems. Although it is difficult to find out a quasi-optimal solution for the long-horizon job shop flow problems within a short time, section processing algorithm is able to both substantially reduce the CPU time and improve its cost function to some extent. In this thesis, we are going to transform the scheduling problems into the optimal ones first, and then apply Lagrangian relaxation technique and the list-scheduling alogrithm to produce the feasible solution. As for the long-horizon job shop flows problems, we will combine section processing and compound incremental cost function to solve them and to greatly improve both the CPU time and the cost function. 英文摘要 …………………………………………………………………………….ii 誌 謝 ………………………………………………………………………………iii 目 錄 ……………………………………………………………………………….iv 表目錄 ……………………………………………………………………………….vi 圖目錄 ……………………………………………………………………………viii 第一章 緒論 …………………………………………………………………………1 第二章 排程問題之簡介 ……………………………………………………………3 2.1 排程問題的定義與分類 ……………………………………………….3 2.2 衡量排程問題績效之準則 …………………………………………….5 2.3 NP-Complete問題 ……………………………………………………...7 2.3.1 計算複雜度 ………………………………………………………7 2.3.2 P類、NP類與NP-Complete類問題 ……………………………8 第三章 成批機種 ……………………………………………………………………9 3.1 簡介 …………………………………………………………………….9 3.2 數學模型 ……………………………………………………………...10 3.3 解決問題的策略 ……………………………………………………...14 3.3.1 拉格朗日鬆散法 ………………………………………………15 3.3.2 子問題的解法 …………………………………………………17 3.3.3 對偶問題之解 …………………………………………………22 3.3.4 建立可行之排程 ………………………………………………23 3.4 排程結果相對績效之評估 ………………………………………….28 3.5 整體架構圖 ………………………………………………………….28 3.6程式流程與參數說明 ………………………………………………..29 3.6.1 收斂條件的選取 ………………………………………………29 3.6.2 執行照單排程法的時機 ………………………………………30 3.6.3 考慮的時間範圍K之選取 ……………………………………32 3.6.4 程式流程圖 ……………………………………………………33 3.7 範例模擬與結果 ……………………………………………………...35 第四章 分段處理演算法 …………………………………………………………40 4.1 簡介 ………………………………………………………………….40 4.2 分段處理演算法 …………………………………………………….41 4.3 使用分段處理演算法的效果 ………………………………………..43 4.3.1 分段處理演算法改善排程結果 ………………………………43 4.3.2 分段處理演算法改善排程效率 ………………………………44 4.4 範例模擬與結果 ……………………………………………………45 第五章 複合成本增量函數法 ……………………………………………………51 5.1 簡介 ………………………………………………………………….51 5.2 複合成本增量函數法 ………………………………………………52 5.3 範例模擬與結果 …………………………………………………….56 第六章 結合分段處理及複合成本增量法 ………………………………………62 6.1 簡介 …………………………………………………………………..62 6.2 結合分段處理及複合成本增量函數法 ……………………………..62 6.3 範例模擬與結果 ……………………………………………………...63 第七章 結論 ………………………………………………………………………67 參考文獻 ……………………………………………………………………………68 附錄一 ………...…………………………………………………………………….70