# 臺灣博碩士論文加值系統

(75.101.211.110) 您好！臺灣時間：2022/01/26 13:09

:::

### 詳目顯示

:

• 被引用: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
 國圖紙本論文
 推文當script無法執行時可按︰推文 網路書籤當script無法執行時可按︰網路書籤 推薦當script無法執行時可按︰推薦 評分當script無法執行時可按︰評分 引用網址當script無法執行時可按︰引用網址 轉寄當script無法執行時可按︰轉寄

 無相關論文

 無相關期刊

 1 具非集總步幅之修正式平行區域比例梯度法及具耦合不等式限制之非線性大型網路最佳化問題的解法 2 模糊多準則非加法型評估之研究∼以「汽車銷售服務品質」為例 3 一個針對離子植入機之錯誤檢測與錯誤判別的方法 4 5.1聲道音響撥放系統之多頻帶空間響應模擬器 5 兩個關於晶圓製造及測試程序的產能與良率之問題及解決方法 6 高科技產業研發實驗室之產能效益改善研究―福特8D與限制理論之應用 7 田口方法於球閘陣列載板製程改善之應用 8 校友會服務機制與服務關鍵項目之探討 9 半導體業導入供應鏈管理之評估方法 10 從交易成本看製造執行系統廠商的演化 11 以國際標準ISO-10303應用協定為基發展之PDMSchema--產品資料管理在數位辦公空間規劃的應用 12 晶圓廠知識管理導入架構之研究─以薄膜模組部門為例 13 半導體設備零組件供應策略之研究--應用限制理論方法 14 晶圓廠小批量之報廢準則研究 15 資料包絡分析法應用於電子、資訊領域科專計畫的效率評估

 簡易查詢 | 進階查詢 | 熱門排行 | 我的研究室