跳到主要內容

臺灣博碩士論文加值系統

(3.237.38.244) 您好!臺灣時間:2021/07/24 16:22
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果 :::

詳目顯示

: 
twitterline
研究生:黃志銘
研究生(外文):Jhih-Ming Huang
論文名稱:應用限制式基因演算法於解決排程及重排程問題之研究
論文名稱(外文):Research of a Constraint-Based Genetic Algorithm Approach for Scheduling and Rescheduling Problems
指導教授:徐培倫徐培倫引用關係張政元張政元引用關係
指導教授(外文):Pei-Lun HsuCheng-Yuan Chang
學位類別:碩士
校院名稱:清雲科技大學
系所名稱:電子工程研究所
學門:工程學門
學類:電資工程學類
論文種類:學術論文
論文出版年:2007
畢業學年度:94
語文別:中文
論文頁數:96
中文關鍵詞:限制推理基因演算法派工法則零工型排程
外文關鍵詞:Constraint-Based ReasoningGenetic AlgorithmDispatching RuleJob-Shop Scheduling
相關次數:
  • 被引用被引用:4
  • 點閱點閱:630
  • 評分評分:
  • 下載下載:170
  • 收藏至我的研究室書目清單書目收藏:0
在生產製造業中,工廠排程問題一直是生產管理者所重視的課題,好的排程管理可帶來高利益少成本的效益,反之則造成營運上的虧損。工廠排程問題中,常需解決複雜的排程計劃以及符合工廠本身的限制條件,而規劃出符合工廠需求之排程結果。在實際的工廠生產線上,常會面臨一些環境的變動,包含緊急插單、緊急抽單、機器故障、及物料短缺等情形,對於一個正在運作的生產系統而言,將會造成連鎖效應使得生產系統大亂,而使得生產效益降低,因此,如何彈性的處理所面臨生產環境變更是工廠生產的重要課題。
本論文整合派工法則與限制推理技術於基因演算法,用來解決零工型排程問題,由於基因演算法主要透過適應函數方式來評估可行的排程,但針對複雜的排程問題,則缺乏有效且正確率高的解題效果。本研究整合派工法則與限制推理技術於基因演算法架構中,限制推理技術用來減少染色體產生的搜尋空間,派工法則做為挑選基因值的決策依據,使得基因演算法能夠更快速的找出符合限制之最佳解。根據上述技術,我們發展出一個生產排程系統,用來解決零工型排程問題,不僅整合派工法則及排程限制式於系統中,且針對動態改變的工廠環境,可經由系統快速重新排程機制之功能,提供新的排程結果給工廠管理者之用。由實驗結果顯示,整合派工法則與限制推理技術之基因演算法較一般傳統的基因演算法有更快速且較符合排程目標之結果。
The purpose of this research is to propose a constraint-based genetic algorithm approach for solving job-shop scheduling problems. It incorporates the constraint-based reasoning and heuristic dispatching rules into genetic algorithm to generate valid chromosome in either the initial phase or the evolutionary process. This approach allows scheduling constraints to be specified as relationships among operations according to precedent constraints, capacity constraints, due date constraints in the form of a constraint network. The constraint-based reasoning is employed to produce valid chromosomes using constraint propagation to assure the genes in complying with the predefined constraint network. The dispatching rules are used to make a decision for choosing the suitable value among the satisfied gene pool. To show the practicality of our work, we develop and implement a constraint-based scheduling prototype system for solving job-shop scheduling problems. In addition, we also provide a rescheduling framework to deal with the requirement of new adding or canceling jobs due to dynamic factory environments. The proposed approach is compared with a regular GA using well-known benchmarks for the job-shop problems. Better computational efficiency and optimal schedules are demonstrated.
中文摘要……………………………………………………………………… i
英文摘要……………………………………………………………………… ii
誌謝…………………………………………………………………………… iii
目錄…………………………………………………………………………… iv
表目錄………………………………………………………………………… vi
圖目錄………………………………………………………………………… vii
第一章 緒論…………………………………………………………………… 1
1.1研究背景與動機…………………………………………………………… 1
1.2研究目的…………………………………………………………………… 3
1.3研究範圍…………………………………………………………………… 3
1.4論文架構…………………………………………………………………… 4
第二章 文獻探討 …………………………………………………………… 5
2.1 排程問題………………………………………………………………… 5
2.1.1 排程問題分類………………………………………………………… 5
2.1.2 排程問題的求解方法………………………………………………… 9
2.1.3 零工型工廠排程問題特性…………………………………………… 10
2.2 派工法則………………………………………………………………… 11
2.2.1 派工法則分類………………………………………………………… 12
2.2.2 零工型工廠派工法則探討…………………………………………… 13
2.3 基因演算法……………………………………………………………… 14
2.3.1 基因演算法簡介……………………………………………………… 14
2.3.2 基因演算法之特性…………………………………………………… 15
2.3.3 基因演算法之運算流程……………………………………………… 16
2.3.4 基因演算法處理限制之策略………………………………………… 22
2.4 限制規劃………………………………………………………………… 24
2.4.1限制滿足問題………………………………………………………… 24
2.4.2限制推理……………………………………………………………… 26
2.4.3相關文獻探討………………………………………………………… 30
第三章 排程系統分析與建置………………………………………………… 32
3.1 排程問題分析…………………………………………………………… 32
3.2 系統架構………………………………………………………………… 36
3.3 系統分析………………………………………………………………… 43
3.3.1 限制網路……………………………………………………………… 44
3.3.2 染色體過濾機制……………………………………………………… 44
3.3.3 向前檢查法…………………………………………………………… 48
3.3.4 染色體編碼方式……………………………………………………… 50
3.3.5 適應函數……………………………………………………………… 51
3.3.6 基因運算子…………………………………………………………… 53
第四章 實驗結果與分析……………………………………………………… 56
4.1 實驗目的………………………………………………………………… 56
4.2 實驗架構………………………………………………………………… 56
4.3 排程結果與分析………………………………………………………… 57
4.4 重排程結果與分析……………………………………………………… 72
第五章 結論與未來研究方向………………………………………………… 88
5.1 結論……………………………………………………………………… 88
5.2 未來研究方向…………………………………………………………… 89
參考文獻……………………………………………………………………… 90
簡歷…………………………………………………………………………… 96
1.徐培倫,黃志銘,「應用限制式基因演算法於解決工作排程問題之研究」,第十一屆人工智慧與應用研討會,331~337頁,高雄,民國九十五年十二月。
2.陳建良,「排程概述」,機械工業雜誌,第153期,122-137頁,民國八十四年十二月。
3.M. E. Aydin and T. C. Fogarty, “A Simulated Annealing Algorithm for Multi-Agent Systems: A Job-Shop Scheduling Application,” Journal of Intelligent Manufacturing, Vol.15, No.6, pp. 805-814, 2004.
4.R. Barták, “Constraint Programming: In Pursuit of the Holy Grail,” Proceedings of Week of Doctoral Students, Prague, Czech Republic, pp.555-564, 1999.
5.P. Baptiste and C. Le Pape, “A Theoretical and Experimental Comparison of Constraint Propagation Techniques for Disjunctive Scheduling,” Proceedings of the 14th International Joint Conference on Artificial Intelligence, Montreal, Canada, pp.600-606, 1995.
6.N. Barnier and P. Brisset, “Optimization by Hybridization of a Genetic Algorithm With Constraint Satisfaction Techniques,” Proceedings of the IEEE Conference on Evolutionary Computation, ICEC, pp. 645-649, 1998.
7.C. Bessiere, “Arc-Consistency and Arc-Consistency Again,” Artificial Intelligence, Vol.65, No.1, pp.179-190, 1994.
8.C. Bessiere, E. C. Freuder and J. C. Régin, “Using Constraint Metaknowledge to Reduce Arc Consistency Computation,” Artificial Intelligence, Vol.107, No.1 pp.125-148, 1999.
9.C. Bierwirth, D. C. Mattfeld and H. Kofer, “On Permutation Representations for Scheduling Problems,” Proceedings of the 4th International Conference on Parallel Problem Solving from Nature, London, UK, pp.310-318, 1996.
10.J. H. Blackstone, D. T. Phillips and G. L. Hogg, “A State-of-the-Art Survey of Dispatching Rules for Manufacturing Job Shop Operation,” International Journal of Production Research, Vol. 20, No.1, pp.27-45, 1982.
11.S. C. Brailsford, C. N. Potts and B. M. Smith, “Constraint Satisfaction Problems: Algorithm and Applications,” European Journal of Operational Research, Vol.119, No.3, pp.557-581, 1999.
12.R. Burns, “Direct Chromosome Representation and Advanced Genetic Operators for Production Scheduling,” Proceedings of the 5th International Conference on Genetic Algorithms, San Mateo, CA, pp.352-359, 1993.
13.Y. Chang, T. Sheyoshi and R. S. Sullivan, “Ranking Dispatching Rules by data Envelopment Analysis in a Job Shop Environment,” IIE Transactions, Vol.28, No.8, pp.631-642, 1996.
14.Y. Cheng, “Arc Consistency Revisited,” Information Processing Letters, Vol.70, No.4, pp.175-184, 1999.
15.C. C. Chiu and P. L. Hsu, “A Constraint-Based Genetic Algorithm Approach for Mining Classification Rules,” IEEE Transactions on Systems, Man and Cybernetics Part C: Applications and Reviews, Vol.35, No.2, pp. 205-220, 2005.
16.L. Davis, “Applying Adaptive Algorithms to Domains,” Proceeding of the 9th International Joint Conference on Artificial Intelligence, Los Angeles, CA, pp.162-164, 1985.
17.P. D. D. Dominic, S. Kaliyamoorthy and R. Murugan, “A Conflict-Based Priority Dispatching Rule and Operation-Based Approaches to Job Shops,” International Journal of Advanced Manufacturing Technology, Vol. 24, No.1-2, pp.76-80, 2004.
18.H. Fang, P. Ross and D. Corne, “A Promising Hybrid GA/Heruistic Approach for Open-Shop Scheduling Problems,” Proceedings of the 11th European Conference on Artificial Intelligence, Amsterdam, The Netherlands, pp.590-594, 1994.
19.S. Gelinas and F. Soumis, “A Dynamic Programming Algorithm for Single Machine Scheduling with Ready Times,” Annals of Operations Research, Vol.69, pp.135-156, 1997.
20.M. Gen and R. Cheng, Genetic Algorithms and Engineering Optimization, John Wiley & Sons, New York, 2000.
21.B. Giffler and G. Thompson, “Algorithms for Solving Production Scheduling Problems,” Operations Research, Vol.8, No. 4, pp.487-503, 1960.
22.R. M. Haralick and G. L. Elliot, “Increasing Tree Search Efficiency for Constraint Satisfaction Problems,” Artificial Intelligence, Vol.14, No.3, pp.263-313, 1980.
23.R. Haupt, “A Survey of Priority Rule-Based Scheduling.” OR Spectrum, Vol.11, No.1, pp.3-16, 1989.
24.N. S. Hemant Kumar and G. Srinivasan, “A Genetic Algorithm for Job Shop Scheduling – A Case Study,” Computers in Industry, Vol.31, No.2, pp. 155-160, 1996.
25.A. Hertz and M. Widmer, “An improved Tabu Search Approach for Solving the Job Shop Scheduling Problem With Tooling Constraints,” Discrete Applied Mathematics, Vol. 65, No.1-3, pp.319-345, 1996.
26.J. H. Holland, Adaptation in Natural and Artificial Systems, Ann Arbor: The University of Michigan Press, 1975.
27.O. Holthaus, “Design of Efficient Job Shop Scheduling Rules,” Computers and Industrial Engineering, Vol.33, No.1-2, pp.249-252, 1997.
28.A. S. Jain and S. Mareen, A State-of-the-Art Review of Job-Shop Scheduling Techniques, Technical Report, University of Dundee, Department of Applied Physics, Electronic and Mechanical Engineering, 1998.
29.R. Kowalczyk, “Using Constrain Satisfaction in Genetic Algorithms,” Proceedings of the 4th Australian and New Zealand Conference on Intelligent Information Systems, Adelaide, South Australia, pp.272-275, 1996.
30.A. K. Mackworth, “Consistency in Networks of Relations,” Artificial Intelligence, Vol.8, No.1, pp.99-118, 1977.
31.R. Mohr and T. C. Henderson, “Arc and Path Consistency Revised,” Artificial Intelligence, Vol.28, No.2, pp.225-233, 1986.
32.B. A. Nadel, “Tree Search and Arc Consistency in Constraint-Satisfaction Algorithms,” Search in Artificial Intelligence, London, UK, pp.287-342, 1988.
33.W. P. M. Nuijten and E. H. L. Aarts, “A Computational Study of Constraint Satisfaction for Multiple Capacitated Job Shop Scheduling,” European Journal of Operational Research, Vol.90, No.2, pp.269-284, 1996.
34.I. Oliver, D. Smith and J. Holland, “A Study of Permutation Crossover Operators on the Traveling Salesman Problem,” Proceedings of the 2nd International Conference on Genetic Algorithms, Cambridge, MA, USA, pp. 224-230, 1987.
35.C. H. Pan, “A Study of Integer Programming Formulations for Scheduling Problems,” International Journal of Systems Science, Vol.28, No.1, pp. 33-41, 1997.
36.B. J. Park, H. R. Choi and H. S. Kim, “A Hybrid Genetic Algorithm for the Job Shop Scheduling Problems,” Computers and Industrial Engineering, Vol.45, No.4, pp. 597-613, 2003.
37.M. Pinedo, Scheduling Theory, Algorithms, and Systems, Prentice Hall, New Jersey, 1995.
38.M. Perlin, “Arc Consistency for Factorable Relations,” Artificial Intelligence, Vol.53, No.2-3, pp.329-342, 1992.
39.M. Perregaard and J. Clausen, “Parallel Branch-and-Bound Methods for the Job-Shop Scheduling Problem,” Annals of Operations Research, Vol.83, pp.137-160, 1998.
40.R. Ramasesh, “Dynamic Job Shop Scheduling: a Survey of Simulation Research.” Omega, Vol.18, No.1, pp.43-57, 1990.
41.D. Sabin and E. C. Freuder, “Contradicting Conventional Wisdom in Constraint Satisfaction,” Proceedings of the 11th European Conference on Artificial Intelligence, Amsterdam, The Netherlands, pp.125-129, 1994.
42.N. Sadeh, K. Sycara and Y. Xiong, “Backtracking Techniques for the Job Shop Scheduling Constraint Satisfaction Problem,” Artificial Intelligence, Vol.76, No.1-2, pp.455-480, 1995.
43.D. Y. Sha and C. Y. Hsu, “A Hybrid Particle Swarm Optimization for Job Shop Scheduling Problem,” Computers and Industrial Engineering, Vol.51, No.4, pp.791-808, 2006.
44.G. Syswerda, Scheduling Optimization Using Genetic Algorithms, Handbook of Genetic Algorithms, New York, Van Nostrand Reinhold, pp.332-349, 1991.
45.S. Yang and D. Wang, “Constraint Satisfaction Adaptive Neural Network and Heuristics Combined Approaches for Generalized Job-Shop Scheduling,” IEEE Transactions on Neural Networks, Vol. 11, No. 2, pp.474-486, 2000.
46.C. Zhang, P. Li, Z. Guan, et al., “A Tabu Search Algorithm with a New Neighborhood Structure for the Job Shop Scheduling Problem,” Computers and Operations Research, Vol.34, No.11, pp.3229-3242, 2007.
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top