跳到主要內容

臺灣博碩士論文加值系統

(44.200.82.149) 您好!臺灣時間:2023/06/05 12:46
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果 :::

詳目顯示

: 
twitterline
研究生:賴郁玲
研究生(外文):Lai Yu-Ling
論文名稱:以基因演算法求解最少延遲工作數下總延遲時間最小化之單機排程問題
論文名稱(外文):Genetic algorithm for single-machine scheduling to minimize total tardiness with the minimize total tardiness with the minmize number of tardy jobs
指導教授:曾文宏曾文宏引用關係
學位類別:碩士
校院名稱:南台科技大學
系所名稱:工業管理研究所
學門:商業及管理學門
學類:其他商業及管理學類
論文種類:學術論文
論文出版年:2005
畢業學年度:93
語文別:中文
中文關鍵詞:遺傳演算法Moore演算法工作分割
相關次數:
  • 被引用被引用:12
  • 點閱點閱:506
  • 評分評分:
  • 下載下載:129
  • 收藏至我的研究室書目清單書目收藏:3
生產排程是製造業中管理活動重要的一環,而排程問題日趨複雜,是屬於組合性最佳化的問題,在真實系統中欲花費大量時間求解真正最佳解之可行性極低。因此,近年來排程研究已漸漸傾向利用啟發式方法在短時間內求取近似最佳解,來有效率的解決各式複雜之排程問題。而本研究求解具有最少延遲工作數下總延遲時間最小化之單機生產排程問題,其問題假設為給定一個工作集合,所有的工作皆可隨時準備加工,每個工作具有加工時間及到期日,並以最少延遲工件數下總延遲時間最小化為目標,來探討如何選擇最佳化排程。
  針對本研究所提出的雙目標問題,分為二個部份來討論。首先,對於有關於最小化總延遲工作數的問題,利用Moore所提出一簡單的多項式演算法,求出單機排程問題的最少延遲工作數 NT。接著利用基因演算法與工作分割的觀念,對雙目標問題求解,並針對系統進行測試與評估。由測試結果發現,本研究的基因演算法所得之排程結果較Moore演算法優良,其求解時間仍在可接受範圍。此外,交配率的設定對於基因演算法並無顯著的影響,而突變率越高所求得的解較好。測試問題驗證了本研究的基因演算法所得之排程結果較Moore演算法優良,其求解時間仍在可接受範圍。
目錄
摘要 I
Abstract II
目錄 III
表目錄 V
圖目錄 VI
圖目錄 VI
第一章 緒論 1
1.1 研究動機與背景 1
1.2 研究目的 2
1.3 研究限制 3
1.4 研究方法 3
第二章 文獻探討 5
2.1 排程理論 5
2.1.1 排程問題的分類 7
2.1.2 排程問題的解法 8
2.1.3 派工法則 9
2.1.4 排程問題之績效衡量準則 10
2.2 多目標排程問題 12
2.2.1 單機多目標最佳化問題 12
2.2.2 多目標排程之相關研究 14
2.3 基因演算法 15
2.3.1 基因演算法的演變 15
2.3.2 基因演算法的運算流程 17
2.3.3 基因演算法之基本特性 18
2.3.4 基因演算法之相關文獻 21
第三章 建立基因演算法 22
3.1分割演算法 22
3.2基因演算法 23
3.2.1 編碼 23
3.2.2 產生初始族群 24
3.3 基因運算子 24
3.2.1 複製(Reproduction/Selection) 24
3.2.2 交配 (Crossover) 25
3.2.3 突變(Mutation) 26
3.2.4 終止條件(Termination Condition) 26
3.3演算法之流程 27
第四章 問題測試及分析 29
4.1 遺傳演算法之各項參數設定 29
4.1.1 測試問題 29
4.1.2 多因子變異數分析 32
4.1.3 雙因子變異數分析資料與結果 33
4.3 綜合分析 35
第五章 結論及建議 37
5.1 結論 37
5.2 未來研究方向 37
參考文獻 39
參考文獻
【1】王培珍,「應用遺傳演算法與模擬在動態排程問題之探討」,中原大學工業工程研究所,碩士論文,1996。
【2】吳宗益,「應用基因演算法及田口實驗法於模具生產排程系之研究」,高雄第一科技大學機械與自動化工程所,碩士論文,2002。
【3】林我聰,現場排程專家系統-應用個體導向技術建立之研究,資訊與電腦公司出版,1994。
【4】張育仁、李慶恩、王立志,「自我調適的動態排程系統-限制排程、模糊理論和遺傳演算法的應用」,工業工程學刊,第15 卷,第六期,1998。
【5】陳正雄,「塔布搜尋法在塑化業排程之應用-以BOPP FILM為例」,元智大學工業工程研究所,碩士論文,2000。
【6】趙文涼,「基因演算法於單機交期絕對偏差及整備成本最小化排程問題之應用」,元智大學工業工程研究所,碩士論文,2000。
【7】廖麗滿,「塔布搜尋法求解排程問題之研究」,國立台灣科技大學工業管理系,博士論文,2001。
【8】鄭价廷,「應用基因遺傳演算法於零工式工場生產排程」,國立高雄第一科技大學機械與自動化工程所,碩士論文,2001。
【9】Ahn, B. and Hyun, J., “Single Facility Multi-Class Job Scheduling,” Computers and Operations Research, 17, 265-272, 1990.
【10】Baker, R. K., “Sequence Rules and Due-Date Assignments in A Job Shop,” Management Science, 30(9), 1984.
【11】Cheng, T.C.E. and Wang, G. “Single Machine Scheduling with Learning Effect Considerations,” Annals of Operation Research, 98, 273-290, 2000.
【12】Chang, P. C., Hsieh, J. C. and Hsiao, C. H. “Application of Genetic Algorithm to the Unrelated Parallel Machine Problem Scheduling,” Journal of the Chinese Institute of Industrial Engineering, 19(2), pp.79-95, 2002.
【13】Chang, P. C., Hsieh, J. C. and Lin, S. G. “The Development of Gradual Priority Weighting Approach for the Multi-Objective Flowshop Scheduling Problem,” International Journal of Production Economics, 79(3), pp.171-181, 2002.
【14】Du, J. and Leung, J. Y. T., “Minimizing Total Tardiness on One-machine Is NP-hard, ” Mathematics of Operations Research, 15, pp. 483-495, 1990.
【15】Emmons, H., “One Machine Sequencing to Minimize Certain Functions of Job Tardiness,” Operations Research, 17, pp. 701-715, 1969.
【16】Emmons, H., “One Machine Sequencing to Minimize Mean Flow Time with Number Tardy,” Naval Research Logistics, 22(3), pp. 585-592, 1975.
【17】Emmons, H., “A Note on A Scheduling Problem with Dual Criteria,” Naval Research Logistic Quarterly, 22(3), pp. 615-616, 1975.
【18】Fry, T., Armstrong, R. and Lewis, H., “A Framework for Single Machine Multiple Objective Sequencing Research,” Omega, 17, pp. 595-607, 1989.
【19】French, S., “Sequencing and Scheduling: An Introduction to the Mathematics of the Job-shop,” John Wiley & Sons, New York, 1982.
【20】Funda, S. S. and Ulusoy, G. “Parallel Machine Scheduling with Earliness and Tardiness Penalties,” Computers & Operations. Research, 26(8), pp. 773-787, 1999.
【21】Vairaktarakis, G. L. and Lee, C., “The Single-machine Scheduling Problem to Minimize Total Tardiness Subject to Minimum Number of Tardy Jobs,” IIE Transactions, 27, pp. 250-256, 1995.
【22】Glass, C. A., Gupta, J. N. D. and Potts, C. N., “Lot Streaming in Three- stage Production Processes,” European Journal of Operational Research, 75(2), pp. 378-394, 1994.
【23】Gupta, J. N. D., “Single Facility Scheduling with Multiple Job Classes,” European Journal of Operational Research, 8, pp. 42-45, 1988.
【24】Grefenstette, J. J., “Optimization of Control Parameters for Genetic Algorithms,” IEEE Transactions on Systems, man & cybernetics, pp. 122-128, 1986.
【25】Gerodimos, A.E., Glass, C.A., and Potts, C.N., “Scheduling the Production of Two-component Jobs on A Single Machine,” European Journal of Operational Research, 120, pp. 250-259, 2000.
【26】Haupt, R.L.; “An Introduction to Genetic Algorithms for Electromagnetics, ” IEEE Antennas and Propagation Magazine, 37(2), pp. 7 -15, 1995.
【27】Johnson, J.M. and Rahmat-Samii, V, “Genetic Algorithms in Engineering Electromagnetics, ”IEEE Antennas and Propagation Magazine, 39(4), pp. 7 -21, 1997.
【28】Holland, J. “Adaptation in Natural and Artificial Systems,” Ann Arbor Univ. of Michigan Press, 1975。
【29】Kim, G. H. and Lee, C. S. G. “An Evolutionary Approach to the Job-shop Scheduling Problem”, Proceeding IEEE International Conference on Robotics and Automation, 1, pp. 501-506, 1994.
【30】Liao, C.J. and Liao, L.M., “Single Facility Scheduling with Major and Minor Setups,” Computers and Operations Research, 24, pp. 169-178, 1997.
【31】Mason, A.J. and Anderson, E.J., “Minimizing Flow Time on a Single Machine with Job Classes and Setup Times,” Naval Research Logistics, 38, pp. 333-350, 1991.
【32】Mellor, P., “A Review of Job Shop Scheduling,” Operational Research Quarterly, 17, pp. 294-301, 1992.
【33】Moreno, A. A., and Ding, F., “Goal Oriented Heuristics for the FMS Loading (and part type selection) Problems”, Proceedings of the Third ORSA/TIMS Conference on Flexible Manufacturing Systems, pp. 105-110, 1989.
【34】Moore, J. M., “An n-job, One-machine Sequencing Algorithm for Minimizing the Number of Late Jobs.” Management Science, 15, pp. 102-109, 1968.
【35】Mukhopadhyay, S. K., Maiti B. and Garg, S. “Heuristic Solution to the Scheduling Problems in Flexible Manufacturing Systems”, International Journal of Production Research, 29, pp. 2003-2024, 1991.
【36】Murata, T. and Ishibuchi, H. “Performance Evaluation of Genetic Algorithms for Flowshop Scheduling Problems”, IEEE International Conference on Robotics and Automation, 1, pp. 812-817, 1994.
【37】Nagar, A., Haddock, J. and Heragu, S. “Multiple and Bicriteria Scheduling: A Literature Survey,” European Journal of Operational Research, 81, pp. 88-104, 1995.
【38】Pan, J.C.H. and Su, C.S., “Single Machine Scheduling with Due Dates and Class Setups,” Journal of the Chinese Institute of Engineers, 20(5), pp.561-572, 1997.
【39】Pinedo, M., “Scheduling: Theory, Algorithm, and Systems,” Prentice Hall, Englewood Cliffs, New Jersey, 1995.
【40】Psaraftis, H.N., “A Dynamic Programming Approach for Sequencing Groups of Identical Jobs,” Operations Research, 28, pp.1347-1359, 1980.
【41】Rios-Mercado, R.Z. and Bard, J., “A Branch-and-Bound Algorithm for Permutation Flow Shops with Sequence-Dependent Setup Times,” IIE Transactions, 31, 721-731 (1999).
【42】Sahney, V. K., “Single-server, Two-machine Sequencing with Switching Time,” Operations Research, 20, pp.24-36, 1972.
【43】Schaffer, J. D., Richard, A., Caruana, L., Eshelman, J. and Rajarshi, D. “A Study of Control Parameters Affecting Online Performance of Genetic Algorithms for Function Optimization”, The 3rd International Conference on Genetic Algorithms and Their Applications, pp. 51-60, 1989.
【44】Shanthikumar, J. G., “Scheduling n Jobs on One Machine to Minimize the Maximum Tardiness with Minimum Number Tardy, ” Computers and Operations Research, 10, pp. 255-266, 1983.
【45】Smith, W.E. “Various Optimizers for Single-stage Production,” Naval Research Logistic Quarterly, 3(1), pp. 59-66, 1956.
【46】Tamaki, H., Nishino, E. and Abe, S. “A Genetic Algorithm Approach to Multi-Objective Scheduling Problems with Earliness and Tardiness Penalties,” Proceedings of the 1999 Congress on Evolutionary Computation, 1, pp.46-52, 1999.
【47】Villarreal, F.J. “Scheduling to Optimize Functions of Job Tardiness: Problem Structure and Algorithms,” Unpublished Ph.D. Dissertation, University of Arizona, 1982.
【48】Tseng W., “Single Scheduling to Minimize Total Tardiness with the Minimum Number of Tardy Jobs,” Master Thesis, Auburn University, 1990.
【49】Wang, C. S. and R. Uzsoy, “A genetic algorithm to minimize maximum lateness on a batch processing machine,” Computers & Operations Research, 29, pp.1621-1640, 2002.
【50】Williams, D. and Wirth, A., “A New Heuristic for a Single Machine Scheduling Problem with Set-up Times,” Journal of the Operational Research Society, pp.47, 175-180, 1996.
連結至畢業學校之論文網頁點我開啟連結
註: 此連結為研究生畢業學校所提供,不一定有電子全文可供下載,若連結有誤,請點選上方之〝勘誤回報〞功能,我們會盡快修正,謝謝!
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top