跳到主要內容

臺灣博碩士論文加值系統

(75.101.211.110) 您好!臺灣時間:2022/01/26 13:09
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果 :::

詳目顯示

我願授權國圖
: 
twitterline
研究生:梁傑愷
研究生(外文):Jie_Kai Liang
論文名稱:一個以隨機搜尋為基礎的解排程問題的拉格朗日鬆散法
論文名稱(外文):A random search based Lagrange relaxation method for job-shop scheduling problems
指導教授:林心宇
指導教授(外文):Shin_Yeu Lin
學位類別:碩士
校院名稱:國立交通大學
系所名稱:電機與控制工程系
學門:工程學門
學類:電資工程學類
論文種類:學術論文
論文出版年:2002
畢業學年度:90
語文別:中文
論文頁數:94
中文關鍵詞:拉格朗日鬆散法隨機搜尋分段處理動態規劃法
外文關鍵詞:Lagrange relaxation methodrandom searchsectional processingdynamic programming
相關次數:
  • 被引用被引用:0
  • 點閱點閱:267
  • 評分評分:
  • 下載下載:0
  • 收藏至我的研究室書目清單書目收藏:0
在製造系統中,排程問題是最基本卻也是最困難的問題之一。大部份的排程問題皆屬於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.

中文摘要 … ………………………………………………………………..i
英文摘要 …………………………………………………………………….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 解決問題的策略 …………………………………………...13
3.3.1 拉格朗日鬆散法 ……………………………………14
3.3.1 擴展拉格朗日鬆散法 …………………………………17
3.3.3 子問題的解法 …………………………………………20
3.3.4 對偶問題之解 …………………………………………22
3.3.5 建立可行之排程………………………………………23
3.4 排程結果相對績效之評估 ……………………………….28
3.5 整體架構圖 ……………………………………………….28
3.6程式流程與參數說明 ………………………………………..29
3.6.1 收斂條件的選取 ………………………………………29
3.6.2 執行照單排程法的時機 ………………………………30
3.6.3 考慮的時間範圍K之選取………………………………31
3.6.4 程式流程圖 ……………………………………………32
3.7 範例模擬與結果 …………………………………………...34
第四章 分段處理演算法 …………………………………………………39
4.1 簡介 ………………………………………………………….39
4.2 分段處理演算法 …………………………………………….40
4.3 使用分段處理演算法的效果 ………………………………..42
4.3.1 分段處理演算法改善排程結果 ………………………44
4.3.2 分段處理演算法改善排程效率 ………………………44
4.4 範例模擬與結果 ……………………………………………45
第五章 以隨機搜尋為基礎的拉格朗日鬆散法………..…………………50
5.1 簡介 ………………………………………………………….50
5.2以隨機搜尋為基礎的拉格朗日鬆散……………………………51
5.3 範例模擬與結果 …………………………………………….56
第六章 結合分段處理及以隨機搜尋為基礎的拉格朗日鬆散法 ………..61
6.1 簡介 …………………………………………………………..61
6.2 結合分段處理及以隨機搜尋為基礎的拉格朗日鬆散法…..62
6.3 範例模擬與結果 …………………………………………...66
6.4 參數設定對模擬結果的影響………………………………...76
第七章 結論 …………………………………………………………………78
參考文獻 ……………………………………………………………………79
附錄一 ……………………………………………………………………….81

[1] M. Numao, and S. Morishita, “A scheduling environment for steel-making processes,” in Proc. Fifth Conf. Artificial Intelligence Allp., IEEE Computer Society, Miami, FL, pp.279-286, Mar. 6-10, 1989
[2] Peter B. Luh, Debra J. Hoitomt, Eric Max, and Krishna R. Pattipati, “Scheduling generation and reconfiguration for parallel machines,” IEEE Trans. Robotics Automat., vol. 6, no. 6, pp.687-696, DEC. 1990
[3] Debra J. Hoitomt, Peter B. Luh, Eric Max, and Krishna R. Pattipati, “Scheduling jobs with simple precedence constraints on parallel machines,” IEEE Contr. Syst. Mag., vol. 10, no. 2, pp.34-40, 1990
[4] Debra J. Hoitomt, Peter B. Luh, and Krishna R. Pattipati, “A practical approach to job-shop scheduling problems,” IEEE Trans. Robotics Automa., vol. 9, no. 1, pp1-13, Feb. 1993
[5] Shin-Yeu Lin, Jung-Shou Huang, Shao-Kung Chang, Chao-Fan Chang, “Controlled Parameters in Suboptimal Solution” ECC’99,Karlsruke, Aug. 31- Sept. 3 1999.
[6] Smith M. L., Ramesh R., Dudek R. A., and Blair E. L., “Characteristics of U.S. flexible manufacturing system — A survey,” Proceedings of the second ORSA/TIMS Conference on FMS, 1986
[7] J. Blazewicz, K. Ecker, G. Schmidt, and J. Weglarz, Scheduling in Computer and Manufacturing System, Springer-Verlag Berlin. Heidelberg 1993.
[8] Stecke, K, E., and J. J. Solberg, “Scheduling of operations in computerized manufacturing system,” Working Paper, School of IE Purdue University, 1977.
[9] D. G. Luenberger, Linear and Nonlinear Programming, 2nd ed. Reading, MA: Addison-Wesley, 1984
[10] Zhigliavsky, Anatoly A., Theory of global random search, Dordrecht/Kluwer Academic,1991
[11] Jihua Wang, Peter B. Luh, “A combined lagrangian relaxation and dynamic programming algorithm for job shop scheduling,” Proceeding of Rensselaer’s 5th International Conference on Computer Integrated Manufacturing & Automation Technology, Grenoble, France, May 1996, pp. 3-8
[12] CHEN, H., C Chu, and J. M. Proth, “A more efficient lagrangian relaxation approach to job-shop scheduling problems,” Proc. of IEEE Int. Conf. on Robotics and Automation, 1995, pp.496-501
[13] B. T. Polyak, “Minimization of unsmooth functionals,” USSR Comput. Math., and Math. Physics, vol. 9, pp.14-29, 1969
[14] A. M. Geoffrion, “Lagrangian relaxation for integer programming,” Math. Programming Study, vol1.2, pp.82-114, 1974.
[15] Jihua Wang, Peter B. Luh, “A combined lagrangian relaxation and dynamic programming algorithm for job shop scheduling,” Proceeding of Rensselaer’s 5th International Conference on Computer Integrated Manufacturing & Automation Technology, Grenoble, France, May 1996, pp. 3-8
[16] Xing Zhao, Peter B. Luh, and Jihua Wang, “The surrogate gradient algorithm for lagrangian relaxation method,” Proceeding of the 36th Conference on Decision & Control, San Diego, California USA, December 1997, pp. 305-310
[17] Tsu-Shuan Chang, Jian Yang, Shin-Ho Wang, “On the use of linear programming for manufacturing scheduling via lagrangian relaxation,” Proceeding of the 36th Conference on Decision & Control, San Diego, California USA, December 1997, pp. 1123-1127

QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top