Title

應用混合式基因演算法求解流程型工廠之多目標排程問題

Translated Titles

An Application of Hybrid Genetic Algorithm for Scheduling in Flowshop with Multiple Objectives

Authors

林水耕

Key Words

基因演算法 ; 流程型工廠 ; 多目標排程問題 ; 柏拉圖最佳解 ; 變動權重 ; Genetic Algorithm ; Flowshop ; Multi-objective scheduling ; Pareto Optimal Solutions ; Variable Weights Approach

PublicationName

元智大學工業工程與管理學系學位論文

Volume or Term/Year and Month of Publication

2001年

Academic Degree Category

碩士

Advisor

張百棧

Content Language

繁體中文

Chinese Abstract

在多目標問題當中,由於各個目標之間往往是相互衝突的,若只是一昧求其中單一目標的最佳排程,經常會造成其他目標的損失。因此如何在多個具有衝突的目標之間,找到一個平衡點,來達到整體的最佳目標,使整體的目標能夠符合決策者的要求,確實是一個相當困難的問題。在本研究的基因演算法和混合式基因演算法中,為了要達到搜尋所有可能的柏柆圖最佳解,本研究提出一個以演化世代數作為權重指定的基礎,可以根據決策者所訂定的目標優先順序以漸進式的權重指定方式,來搜尋在此優先順序下的柏拉圖最佳解(Pareto Optimal Solutions)。而此方法有別於一般在同一世代內隨機指定染色體變動權重的方式。經實驗證明,本研究所提出之漸進式優先順序法在求解時間與求解品質上均具有不錯的效果。

English Abstract

The objectives are competitive in solving the multi-objective scheduling problem. Supposing that we just concentrate on searching the optimal schedule with respect to one of the objectives, it leads to the loss of the other objectives. And the optimal schedule of the specified objective is always a local optimum to the multi-objective scheduling problem. As for how to achieve the global optimization is a really hard problem. Conventionally, for lowering the complexity, multi-objective problems are transformed into single objective problem through linear combination. Supposing that the searching direction is fixed and many other superior solutions cannot be visited. In this research, to recover the key drawback of the conventional approach, we propose the gradual-priority weight assignment (GPWA) approach to search the Pareto optimal solutions. GPWA searches feasible region from the first objective in the beginning and toward the other objectives gradually. For verifying the effectiveness and efficiency, GPWA compares with the variable weights approach proposed by Murata et al. As the results of comparisons, GPWA performs quite effectively and efficiently.

Topic Category 工程學院 > 工業工程與管理學系
工程學 > 工程學總論
社會科學 > 管理學
Reference
  1. [2] Chen, C. L., V. S. Vempati and N. Aljaber, “An Application of Genetic Algorithms for Flow Shop Problems,” European Journal of Operational Research, 80, pp.389-396.1995.
    連結:
  2. [3] Davis, L., Handbook of Genetic Algorithms, Morgan Kaufmann, San Mateo, CA, 1987.
    連結:
  3. [4] French, S., Sequencing and Scheduling: An Introduction to the Mathematics of the Job-Shop, John Wiley, New York, 1982.
    連結:
  4. [5] Gangadharan, R. and C. Rajendran, “A Simulated Annealing Heuristic for Scheduling in a Flowshop with Bicriteria,” Computers & Industrial Engineering, 27, pp.473-476, 1994.
    連結:
  5. [6] Gen, M. and R. Cheng, Genetic Algorithms and Engineering Design, John Wiley, New York, 1997.
    連結:
  6. [7] Glass, C. A. and C. N. Potts, “A Comparison of Local Search Methods for Flow Shop Scheduling,” Annals of Operations Research, 63, pp.489-509, 1996.
    連結:
  7. [8] Goldberg, D. E., Genetic Algorithms in Search, Optimization and Machine Learning, Addison Wesley, Reading, MA, 1989.
    連結:
  8. [9] Ho, J. C. and Y. L. Chang, “ A New Heuristic for The n-Job, M-Machine Flow-shop Problem,” European Journal of Operational Research, 52, pp.194-202, 1991.
    連結:
  9. [10] Ishibuchi, H. and H. Murata, “Local Search Procedures in a Multi-Objective Genetic Local Search Algorithm for Scheduling Problems,” Proceedings of IEEE International Conference on SMC, pp.119-124, 1996.
    連結:
  10. [11] Ishibuchi, H. and H. Murata, “Multi-Objective Genetic Local Search Algorithm,” Proceedings of IEEE International Conference on Evolutionary Computation, pp.119-124, 1996.
    連結:
  11. [12] Ishibuchi, H. and H. Murata, “Multi-Objective Genetic Local Search Algorithm and Its Applications to Flowshop Scheduling,” IEEE Transactions on SMC, 28, pp.392-403, 1998.
    連結:
  12. [14] Michalewicz, Z., Genetic Algorithm + Data Structures = Evolution Programs, 2nd ed., Springer-Verlag, New York, 1994.
    連結:
  13. [15] Murata, T. and H. Ishibuchi, “Performance Evolution of Genetic Algorithms for Flowshop Scheduling Problems,” Proceedings of 1st IEEE International Conference on Evolutionary Computation,” pp.812-817, 1994.
    連結:
  14. [17] Murata, T. and H. Ishibuchi, “Positive and Negative Combination Effects of Crossover and Mutation Operators in Sequencing Problems,” Proceedings of IEEE International Conference on Evolutionary Computation, pp.170-175, 1996.
    連結:
  15. [19] Murata, T., H. Ishibuchi, and H. Tanaka, “Multi-Objective Genetic Algorithm and Its Applications to Flowshop Scheduling,” International Journal of Computers and Industrial Engineering, 30, pp.957-968, 1996.
    連結:
  16. [21] Nagar, A., J. Haddock and S. Heragu, “Multiple and Bicriteria Scheduling: A Literature Survey,” European Journal of Operational Research, 81, pp.88-104, 1995.
    連結:
  17. [22] Nagar, A., S. S. Heragu, and J. Haddock, “A Branch and Bound Approach for a Two-Machine Flowshop Scheduling Problem,” Journal of the Operational Research Society, 46, pp.721-734, 1995.
    連結:
  18. [23] Nagar, A., S. S. Heragu, and J. Haddock, “A Combined Branch-and-Bound and Genetic Algorithm Based Approach for a Flowshop Scheduling Problem,” Annals of Operations Research, 63, pp.397-414, 1996.
    連結:
  19. [24] Nawaz, M., E. E. Enscore and I. Ham, “A Heuristic Algorithm for the m-Machine, n-Job Flow-shop Sequencing Problem,” OMEGA, 11, pp.91-95, 1983.
    連結:
  20. [25] Neppali, V. R., C. L. Chen and J. N.D. Gupta, “Genetic Algorithms for the Two-stage Bicriteria Flowshop Problem,” European Journal of Operational Research, 95, pp.356-373, 1996.
    連結:
  21. [26] Rajendran, C. and D. Chaudhuri, “An Efficient Heuristic Approach to The Scheduling of Jobs in a Flowshop,” European Journal of Operational Research, 61, pp.318-325, 1992.
    連結:
  22. [27] Rajendran, C., “Two-stage Flowshop Scheduling Problem with Bicriteria,” Journal of the Operational Research Society, 43, pp.871-884, 1992.
    連結:
  23. [28] Rajendran, C., “Heuristics for Scheduling in Flowshop with Multiple Objectives,” European Journal of Operational Research, 82, pp.540-555, 1995.
    連結:
  24. [29] Reeves, C. R., “A Genetic Algorithm for Flowshop Sequencing,” Computer & Operations Research, 22, pp.5-13, 1995.
    連結:
  25. [30] Sridhar, J. and C. Rajendran, “Scheduling in Flowshop and Cellular Manufacturing Systems with Multiple Objectives―A Genetic Algorithmic Approach,” Production Planning & Control, 7, pp.374-382,1996.
    連結:
  26. [31] Tamaki, H., H. Kita, and S. Kobayashi, “Multi-Objective Optimization by Genetic Algorithms: A Review,” Proceedings of IEEE International Conference on Evolutionary Computation,” pp.517-522, 1996.
    連結:
  27. [32] Widmer, M. and A. Hertz, “A New Heuristic Method for the Flow Shop Sequencing Problem,” European Journal of Operational Research, 41, pp.186-193, 1989.
    連結:
  28. [1] Baker, K. R., Introduction to Sequencing and Scheduling, John Wiley, New York, 1974.
  29. [13] King, J. R., and A. S. Spachis, “Heuristic for Flow-shop Scheduling,” International Journal of Production Research, 18, pp.345-357, 1980.
  30. [16] Murata, T. and H. Ishibuchi, “MOGA: Multi-Objective Genetic Algorithms,” Proceedings of 2nd IEEE International Conference on Evolutionary Computation, pp.284-294, 1995.
  31. [18] Murata, T., H. Ishibuchi and H. Tanaka, ”Genetic Algorithm for Flowshop Scheduling Problem,” International Journal of Computers and Industrial Engineering, 30, pp.1061-1071, 1996.
  32. [20] Murata, T., H. Ishibuchi, and M. Gen, “Neighborhood Structures for Genetic Local Search Algorithms,” Proceedings of 2nd IEEE International Conference on Knowledge-based Intelligent Electronic Systems, 21-23, pp.259-263, 1998.
  33. [33] 汪玉柏,「運用基因演算法求解流程型工廠之多目標排程」,國立台灣科技大學,碩士論文,民國八十八年。
  34. [34] 周富得,「流程型工廠在雙評估準則下之排程研究」,國立交通大學,博士論文,民國八十六年。
  35. [35] 許民聖,「運用模擬退火法求解流程型工廠之多目標排程」,國立台灣科技大學,碩士論文,民國八十九年。
  36. [36] 許志義,多目標決策,一版,五南圖書出版有限公司,台北,民國八十三年。
Times Cited
  1. 徐麟(2011)。以柴比雪夫分群法建構子群體權重向量求解多目標問題。元智大學資訊管理學系學位論文。2011。1-65。 
  2. 劉育伶(2008)。應用瀰母演算法於多目標排程問題之求解。元智大學工業工程與管理學系學位論文。2008。1-105。 
  3. 陳建隆(2008)。基因演算法於多目標TFT-LCD模組廠排程問題之研究。元智大學工業工程與管理學系學位論文。2008。1-94。 
  4. 李家智(2006)。順序性移動式精英政策之子群體基因演算法於多目標問題之應用。元智大學工業工程與管理學系學位論文。2006。1-100。 
  5. 陳啟嘉(2006)。基因結構探勘於承接式子群體基因演算法求解多目標組合性問題。元智大學工業工程與管理學系學位論文。2006。1-171。 
  6. 林昆霖(2005)。子群體基因演算法於多目標排程之應用─以PCB鑽孔作業為例。元智大學工業工程與管理學系學位論文。2005。1-84。
  7. 廖昱翔(2008)。多種模擬退火法於雙目標流線型排程問題解算效果之評估比較。元智大學工業工程與管理學系學位論文。2008。1-95。
  8. 洪振家(2008)。智慧型基因演算法於流程型工廠排程之應用─以太陽能板為例。元智大學工業工程與管理學系學位論文。2008。1-68。
  9. 黃清杉(2011)。基因演算法在流程型工廠測試排程之應用-以T公司為例。元智大學工業工程與管理學系學位論文。2011。1-100。