一個區段評估法在排程問題上的應用

Abstract

在製造系統中，排程問題是最基本卻也是最困難的問題之一。大部份的排程問題皆屬於NP-Complete類的問題，所以大多數的工廠是利用啟發式排程法則或是有經驗的排程員來解決排程問題，如此無法掌握整個工廠的生產目標以及運作狀況，因此改善排程方法有其迫切的需要。 結合拉格朗日鬆散法與照單排程法是處理整體系統考量下的製造系統排程問題中最常被使用的方法。根據次佳解控制參數的觀念，我們發現拉格朗日鬆散法和照單排程法有改善的空間。在 Peter B. Luh 提出以拉格朗日鬆散法配合照單排程法求解排程問題後，許多學者紛紛提出對拉格朗日鬆散法的改善方法，但是卻沒有把研究的重心放到照單排程法。 在本論文中，我們將提出一個新的區段評估法來改善照單排程法，以獲得一個更佳的成本函數值，更為改善排程問題的方法尋找到新的研究方向。

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 generated 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 generally. Based on the idea of controlled parameters in suboptimal solution，we can find that the Lagrangian relaxation and list schedule have room for improvement. Several method that improve lagrangian relaxation technique have been presented。But none focus their attention on list scheduling. In this paper, we will present a new technique -block estimating technique - to improve list schedule. We can obtain a better cost function value and find a new way to improve scheduling problems. 第二章 排程問題之簡介 ……………………………………….….…4 2.1 排程問題的定義與分類………………………….….….4 2.3 衡量排程系統績效之準則…………………………..….7 2.3 NP-Complete問題…………………………………...…10 2.3.1 計算複………………………………..…..10 2.3.3 P類、NP類與NP-Complete類問題…..…….11 第三章 序列機種排程問題…………………………………..………13 3.1簡介……………………………………… 13 3.2 數學模型…………………………………………..….…14 3.3 解決問題的策略……………………………………...…18 3.3.1 拉格朗日鬆散法…………………………….…...19 3.3.2 動態規畫法……………………………..…….….21 3.3.3 對偶問題之解……………………………..….….22 3.3.4 建立可行之排程………………………………....23 3.4 排程結果相對績效之評估………………………..…….25 3.5 整體架構圖……………………………………….….…27 3.6 程式流程與3.7 參數說明…………………………………..28 3.7.1 收斂條件的選取………………………………….28 3.7.2 執行照單排程法的時機………………………….29 3.7.3 考慮的時間範圍3.7.4 K之選取…………………….…30 3.7.5 程式流程圖……………………………………….32 第四章 有關排程演算法之改進……………………………………..34 4.1 Facet Ascending Algorithm .…….………………………35 4.2 Reduced Complexity Bundle Method….………………...38 4.3 Surrogate Gradient Algorithm.…………………………...41 4.4 次佳解中的控制參數..…………………………….……43 4.5 分段處理演算法 .………………………………………45 4.6 照單排程問題之改善……………………………….…..47 第五章 區段評估法法…………………………………………….….48 5.1 簡介…………………………………………………..….48 5.2 區段評估演算法…………………………………….…50 5.2.1 區段之認定………………………………….51 5.2.2 區段評估……………………………………51 5.2.3 違反操作程序之修正………………………52 5.2.4 區段評估疊代法……………………………53 5.2.5 區段評估演算法……………………………54 5.3 範例模擬 結果…………………………………….…56 第六章 結論…………………………………………………………..65