跳到主要內容

臺灣博碩士論文加值系統

(35.175.191.36) 您好!臺灣時間:2021/08/01 00:03
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果 :::

詳目顯示

我願授權國圖
: 
twitterline
研究生:范雅喬
研究生(外文):Ya-Chiao Fan
論文名稱:應用基因演算法於工件可分段處理下不相關平行機台問題之研究
論文名稱(外文):A Genetic Algorithm Approach for Unrelated Parallel-Machine Scheduling Problems with Dividable Jobs
指導教授:蔡啟揚
學位類別:碩士
校院名稱:元智大學
系所名稱:工業工程與管理學系
學門:工程學門
學類:工業工程學類
論文種類:學術論文
論文出版年:2009
畢業學年度:97
語文別:中文
論文頁數:105
中文關鍵詞:基因演算法不相關平行機台排程順序相依分段處理
外文關鍵詞:genetic algorithmunrelated parallel-machineschedulingsequence dependentdividable jobs
相關次數:
  • 被引用被引用:4
  • 點閱點閱:140
  • 評分評分:
  • 下載下載:0
  • 收藏至我的研究室書目清單書目收藏:0
平行機台一直是近年來在排程問題中一個重要的研究領域之一,但平行機台的排程問題在學術上是屬於困難度極高的組合最佳化問題,除了少數特例外,此類問題均屬於NP-hard問題,需要花費相當多的時間及資源才能求得最佳解,因此本研究期望能在具有順序相依整備時間,工作是有不同到達時間且加工方式是可視為可分段處理的前提條件下,去建構出一個以總絕對延誤時間最小化的不相關平行機台排程模式。
而本研究是嘗試使用具有平行搜尋與能避免落入局部最佳解的基因演算法來求解此不相關平行機台之排程問題,並結合某偏光板廠中的PSA製程之實際案例資料去對在部份分段作業模式下的不同分段比重進行效益比較,期能提供業界或後續研究人員作為參考。
Parallel-machine scheduling has been one of the important research fields of scheduling problems in recent years. It is a difficult combinatorial optimization problem. Except for few cases, this kind of problems belongs to NP-hard problems which require considerable time and resources to find optimal solutions. This research considers parallel-machine scheduling problems where jobs can be divided into stages and do not require continuous process. An unrelated parallel-machine scheduling model with dividable jobs, sequence-dependence setup times, and non-zero arrival times, is constructed and the objective is to minimize total absolute lateness.
This research applies Genetic Algorithm Approach on the considered scheduling problem. The Genetic Algorithm has parallel searching functions and capability to avoid partial optimal solution. Numerical experiment containing various test problems with real case data of the PSA process from a Polarizer manufacturing factory is conducted to evaluate the performance of the proposed algorithm. It is the aim of this research that the results can be of valuable to industries and follow-up research.
摘要 i
英文摘要 ii
誌謝 iii
表目錄 vii
圖目錄 viii
第一章 緒論 1
1.1 研究背景與動機 1
1.2 研究目的 2
1.3 研究方法 2
1.4 研究步驟與架構 3
第二章 文獻探討 5
2.1 排程 5
2.1.1 排程問題分類 5
2.1.2 排程問題研究方法 7
2.1.3 績效指標 9
2.2 平行機台 10
2.2.1 平行機台系統定義及分類 10
2.2.2 不相關平行機台排程問題之相關文獻 11
2.3 基因演算法 15
2.3.1 基因演算法簡介 15
2.3.2 基因演算法於排程之應用 19
2.4 本章總結 22
第三章 問題描述與建構 23
3.1 產品及製程介紹 23
3.2 問題定義 24
3.3 問題限制與假設 25
3.4 不相關平行機台問題數學模型 26
3.4.1 符號說明 26
3.4.2 問題模式 26
3.4.3 目標式與限制式說明 27
3.5 作業分段問題 28
第四章 研究方法 31
4.1 現行作法說明 31
4.1.1 現行作法作業程序 32
4.1.2 現行作法範例說明 35
4.2 基因演算法 41
4.2.1 編碼 41
4.2.2 產生起始解 42
4.2.3 計算目標值 42
4.2.4 定義適合度函數 42
4.2.5 複製/選擇 43
4.2.6 交配 44
4.2.7 突變 45
4.2.8 修正不可行解 46
4.2.9 產生新群體 47
4.2.10 演化世代停止條件 47
4.3 分段作業模式效益驗證 49
4.4 效益分析 52
第五章 測試例題說明與參數設計 54
5.1 測試例題說明 54
5.1.1 問題難易度定義 54
5.1.2 問題難易度範例說明 56
5.2 部份分段選擇方式 57
5.3 基因演算法參數分析 59
5.3.1 田口實驗設計 60
5.3.2 控制因子水準設定 61
5.3.3 實驗設計與分析 62
5.4 參數分析結語 66
第六章 驗證結果與分析 67
6.1 小型規模問題 67
6.1.1 不同問題難易度下不同分段作業模式求解效果之比較 70
6.1.2 不同問題難易度下不同分段作業模式的提前時間與延後時間之比較 71
6.1.3 不同分段作業模式下不同問題難易度的改善率之比較 72
6.1.4 不同分段作業模式下不同問題難易度的CPU時間之比較 74
6.1.5 不同分段作業模式下不同問題難易度的提前時間與延後時間之比較 75
6.2 大型規模問題 78
6.2.1 不同問題難易度下不同分段作業模式求解效果之比較 81
6.2.2 不同問題難易度下不同分段作業模式的提前時間與延後時間之比較 82
6.2.3 不同分段作業模式下不同問題難易度的改善率之比較 83
6.2.4 不同分段作業模式下不同問題難易度的CPU時間之比較 85
6.2.5 不同分段作業模式下不同問題難易度的提前時間與延後時間之比較 86
6.3 不同規模問題相關比較 89
6.3.1 不同分段作業模式下不同規模問題的改善率之比較 89
6.3.2 不同分段作業模式下不同規模問題的CPU時間之比較 90
6.3.3 不同分段作業模式下不同規模問題的提前時間與延後時間之比較 92
6.4 測試結果總結 94
第七章 結論與未來研究建議 98
7.1 研究結論 98
7.2 未來研究建議 99
參考文獻 100
1.Allahverdi, A. and J. Mittenthal. 1994, “Scheduling on M Parallel Machines Subject to Random Breakdowns to Minimize Expected Mean Flow Time,” Naval Research Logistics, 41, pp.677-682.
2.Anagnostopoulos, G. C. and G. Rabadi. 2002, “A Simulated Annealing Algorithm For The Unrelated Parallel Machine Scheduling Problem,” The Fifth Bi-annual World Automation Congress (WAC), the Eighth International Symposium on Manufacturing and Applications, 3.
3.Alexander. G., S. Maxim and U. Marc. 2004, “Unrelated parallel machine scheduling with resource dependent times,” Proceedings of the 11th Conference on Integer Programming and Combinatorial Optimization.
4.Baker, K. R. 1974, Introduction to Sequencing and Scheduling, John Wiley & Sons, Inc., New York, U.S.A.
5.Cheng, R. and M. Gen. 1997, “Parallel machine scheduling problems using memeic algorithms” Computers & Industrial Engineering, 33, 3, pp.761-764.
6.Chen, J. F. and H. J. Hou. 2001, “Minimization of total tardiness on unrelated parallel machine scheduling with secondary constraints,” Chinese Institute of Industrial Engineers conference.
7.Chang, P. C. and J. C. Hsieh and S. G. Lin. 2002, “The development of gradual-priority weighting approach for the multi-objective flowshop scheduling problem,” International Journal of Production Economics, 79, pp.171-183.
8.Chang, P. C., J. C. Hsieh, and C. H. Hsiao. 2002, “Application of Genetic Algorithm to the Unrelated Parallel Machine Problem Scheduling,” Journal of the Chinese Institute of Industrial Engineering, 19(2), pp.79-95.
9.Chen, J.F., and Wu, T.H. 2006, “Total tardiness minimization on unrelated parallel machine scheduling with auxiliary equipment constraints”. Omega, 34(1), pp.81–89.
10. Davis, L. 1987, Handbook of Genetic Algorithms, Morgan Kaufmann, San
Mateo, CA.
11. Falkenaurer, E. and S. Bouffouix. 1991, “A genetic algorithm for job shop
scheduling,” Proceedings of IEEE International Conference on Robitcs and Automaion Sacramento, pp.824-829.
12. Figielska, E. 1999, “Preemptive Scheduling with Changeovers: Using Column Generation Technique and Genetic Algorithm,” Computers & Industrial Engineering, 37(1-2), pp.81-84.
13. Funda, S. S. and G. Ulusoy. 1999, “Parallel machine scheduling with earliness and tardiness penalties,” Computers & Operations Research 26, pp.773-787.
14. Goldberg, D. 1989, Genetic Algorithms in Search, Optimization and Machine Learning, Addison-Wesly, MA.
15. Glass, C. A., C. N. Potts and P. Shade. 1994, “Unrelated parallel machine
scheduling using local search,” Mathematics and Computer Modelling, 20(2), pp.41-52.
16. Ghirardi, M. and C. N. Potts. 2005, “Makespan minimization for scheduling
unrelated parallel machines: A recovering beam search approach,” European Journal of Operational Research, 165, pp.457-467.
17. Hemant Kumar, N. S. and G. Srinivasan. 1996, “A genetic algorithm for job
shop scheduling – A case study,” Computers in Industry, 31, 2, pp.155-160.
18. Murata, T. H. Ishibuchi and H. Tanaka. 1996, “Genetic algorithms for flowshop scheduling problems,” Inter national Journal of Computers and Industrial Engineering, 30, 4, pp.1061-1071.
19. Pinedo, M. 1995, “Scheduling: theory, algorithms, and systems”,Prentice-Hall.
20. Piersma, N. and W. V. Dijk. 1996, “A local search heuristic for unrelated parallel machine scheduling with efficient neighborhood search,” Mathematics and Computer Modelling, 24(9), pp.11-19.
21. Reeves, C. R. 1995, “A genetic algorithm for flowshop sequencing. “ Computers & Operations Research, 122, 1, pp.5-13.
22. Runwei Cheng, Mitsuo Gen, and Tatsumi Tozawz. 1995, “Minmax earliness/tardiness scheduling in identical parallel machine system using genetic algorithms”, Computers & Industrial Engineering, vol. 29, no.1-4 , pp.513-517.
23. Rabadi, G.. 2006, “Heuristics for the Unrelated Parallel Machine Scheduling
Problem with Setup Times”. Journal of Intelligent Manufacturing, 17, pp.85–97.
24. Suresh, V. and D. Chaudhuri. 1994, “Minimizing maximum tardiness for
unrelated parallel machines,” International Journal of Production Economics, 34(2), pp.23-239.
25. Suresh, V. and D. Chaudhuri. 1996, “Bicriteria scheduling problem for unrelated parallel machines,” Computer & Industrial Engineering, 30(1), pp.77-82.
26. Srivastava, B. 1998, “An effective heuristic for minimizing makespan on
unrelated parallel machines,” Journal of the Operational Research Society, 49, pp.886-894.
27. Shim, S. & Kim, Y. 2007, “Minimizing total tardiness in an unrelated
parallel-machine scheduling problem”, Journal of the Operational Research Society, vol. 58, no.3, pp.346-354.
28. Varela, R., C. R. Vela, J. Puente and A. Gomez. 2003, “A knowledge-based evolutionary strategy for scheduling problems with bottlenecks,” European Journal of Operational Research, 145, pp.57-71.
29. Wang, C. S. and R. Uzsoy. 2002, “A genetic algorithm to minimize maximum lateness on a batch processing machine, “Computers & Operations Research, 29, pp.1621-1640.
30. 王雅瓊(2002年12月16日) : 偏光板產業現況與展望。富邦證券投資月刊,線上檢索日期 : 2008年2月1日。綱址 : (http://info.fbs.com.tw/KM/NewsText/200301%5C0612.4.%E5%B0%88%E9%A1%8C-%E5%81%8F%E5%85%89%E6%9D%BF%E7%94%A2%E6%A5%AD%E7%8F%BE%E6%B3%81%E8%88%87%E5%B1%95%E6%9C%9B.pdf)
31. 王治元,2004,「智慧型基因演算法於多目標排程之發展與應用-以PCB鑽孔作業為例」,元智大學工業工程與管理研究所,碩士論文。
32. 王苡宸,2008,「資源限制下比例式非等效平行機台排程問題之研究」,元智大學工業工程與管理研究所,碩士論文。
33. 阮永漢,2002,「系統模擬與基因演算法於完全相同機台排程之應用」,元智大學工業工程與管理研究所,碩士論文。
34. 李勝隆,2003,「基因演算法於印刷電路板鑽孔排程之應用」,元智大學工業工程與管理研究所,碩士論文。
35. 林淳菁,2000,「應用遺傳基因演算法求解不相關平行機台之排程問題」,朝陽科技大學工業工程與管理研究所,碩士論文。
36. 林晋宏,2006,「基因演算法求解作業不同到達時間之open shop雙目標排程問題之研究」,國立勤益科技大學工業工程研究所,碩士論文。
37. 吳宛芳(2006) : 大尺寸TFT LCD上游關鍵零組件產業分析。元大京華投顧分析報告,線上檢索日期 : 2008年2月1日。綱址 : (http://intra.yuanta.com.tw/PagesA2/hot_issue/9205TFT%20LCD.html)
38. 施智懷,2004,「具動態權重之混合基因演算法求解順序相依整備時間下單機排程問題之研究」,華梵大學資訊管理研究所,碩士論文。
39. 洪振家,2008,「智慧型基因演算法於流程型工廠排程之應用─以太陽能板為例」,元智大學工業工程與管理研究所,碩士論文。
40. 洪淑賢(2008年1月11日) : 台灣光電產業高成長 2007產業規模破兩兆。電子工程專輯,線上檢索日期 : 2008年2月1日。綱址 :(http://www.eettaiwan.com/ART_8800497174_480702_NT_877954e2.HTM)
41. 徐懿亨,2006,「考量刀具數量及刀具壽命下單階非相關平行機台現場管控系統之研究」,國立屏東科技大學工業管理研究所,碩士論文。
42. 張毓仁,2001,「多階段不等效平行機之排程研究」,中原大學工業工程研究所,碩士論文。
43. 陳皇銓,2006,「規劃符合多目標與多人同時進行單一作業限制之人員派遣模式-以資訊業外派服務為例」,國立屏東科技大學工業管理研究所,碩士論文。
44. 陳建隆,2008,「基因演算法於多目標TFT-LCD模組廠排程問題之研究」
,元智大學工業工程與管理研究所,碩士論文。
45. 游擱鴻,1998,「啟發式方法求解不相關平行機器排程問題」,朝陽科技大學工業工程與管理研究所,碩士論文。
46. 曾毓文,2001,「運用系統模擬與遺傳演算法從事非相關平行機器排程之研究」,國立台北科技大學生產系統工程與管理研究所,碩士論文。
47. 黃俊龍,2005,「應用模擬退火法規劃具有加工順序限制之非相關平行機台多目標排程」,國立屏東科技大學工業管理研究所,碩士論文。
48. 黃文品,2007,「開發混合式巨集啟發式方法求解具順序相依整備時間之非等效平行機台排程問題」,國立政治大學資訊管理研究所,碩士論文。
49. 經濟部工業局(2007)。2007年我國平面顯示器產業成就。線上檢索日期: 2008年2月1日。網址 :(http://www.moeaidb.gov.tw/external/ctlr?PRO=news.NewsView&id=4536)
50. 趙文涼,2001,「基因演算法於單機交期絕對偏差及整備成本最小化排程問題之應用」,元智大學工業工程與管理研究所,碩士論文。
51. 熊詩敏,2007,「結合優勢性質與基因遺傳演算法於具有整備時間之單機與非等效平行機台之研究」,元智大學工業工程與管理研究所,碩士論文。
52. 劉志宏,2000,「不確定加工時間之平行機台排程」,國立清華大學工業工程與工程管理研究所,碩士論文。
53. 鄭志傑,2006,「基因演算法於有限資源下不相關平行機台排程問題之應用」,元智大學工業工程與管理研究所,碩士論文。
54. 賴佑華,2007,「應用分支界限法於資源限制下的不相關平行機台排程問題」,元智大學工業工程與管理研究所,碩士論文。
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top
無相關期刊