Title

應用模擬退火法與離散粒子群演算法在排列流程式排程問題之研究

Translated Titles

Application of Simulated Annealing and Discrete Particle Swarm Optimization Algorithm for Permutation Flow-Shop Problems

DOI

10.6841/NTUT.2009.00218

Authors

沈銘倫

Key Words

排程 ; 粒子群 ; 模擬退火法 ; Schedule ; Particle Swarm Optimization ; Simulated Annealing

PublicationName

臺北科技大學工業工程與管理系碩士班學位論文

Volume or Term/Year and Month of Publication

2009年

Academic Degree Category

碩士

Advisor

王明展

Content Language

繁體中文

Chinese Abstract

多目標排程問題都為NP-hard,通常求解此類問題需要花費較長的時間,尤其是大規模(工作數量、機器種類)問題,因此本研究提出混合式離散粒子群演算法以求解排程問題。 求解最佳化問題透過啓發式演算法,能有效地搜尋與求解NP-hard問題,其中常見NP-hard問題,例如車輛途程、生產排程、設施規劃等問題。本研究求解總完工時間與總流程時間最小化,利用本研究提出混合式離散粒子群演算法其中離散粒子群針對排程問題而內部結構改變,再加上離散粒子群本身具有探測與開發的能力,接著應用模擬退火法能夠避免離散粒子群陷入區域最佳解並改善執行效率。本研究以Taillard的排程基準並與其它演算法作比較,經過第四章的實驗結果,本研究提出的混合式離散粒子群演算法能在總完工時間與總流程時間目標求得最佳解且能適用在排列流程式排程問題。

English Abstract

All the multi-objective scheduling problems are essentially NP-hard. It usually cost us much time to solve these problems. We try to apply Hybrid discrete particle swarm optimization (HDPSO) proposed to deal with multi-objective production efficient scheduling problems. For the optimization problems, meta-heuristics have driven to be more efficiency and deal with different NP-hard problems, such as vehicle routing, production scheduling, facility layout, etc. We consider criterions which are minmize makespan and total flow time, we try to apply HDPSO where Discrete particle swarm optimization changed insides configuration to aim at scheduling problem and characteristics of exploration and exploitation itself. Furthermore, simulated annealing(SA) have escaped Discrete particle swarm optimization to trapped local optima and improvement quality solution. The proposed HDPSO was applied to well-known Taillard benchmark problems and compared with several competing meta-heuristics. Experiment result shows that we proposed HDPSO is competitive and efficient in Permutation Flow-Shop Problem(PFSP) with minmize makespan and total flow time.

Topic Category 管理學院 > 工業工程與管理系碩士班
工程學 > 工程學總論
社會科學 > 管理學
Reference
  1. [4] L. Wang, and D.Z. Zheng. ,“An effective optimization strategy for job shop scheduling problems,” Computers and Operations Research, 2001, pp.585-596.
    連結:
  2. [5] T. Yamada, and R. Nakano,“Job-shop scheduling by simulated annealing combined with deterministic local search,” In: Meta-heuristics: theory and applications. Dordrecht: Kluwer Academic Publishers, 1996, pp.237-248.
    連結:
  3. [6] J. Carlier, and E. Pinson, “An algorithm for solving the job-shop problem,” Management Science, 1989, pp.64-76.
    連結:
  4. [7] Kuo-Ling Huang ,“Ching-Jong Liao, Ant colony optimization combined with taboo search for the job shop scheduling problem,” Computers & Operations Research, vol.35 , 2008, pp.1030 -1046
    連結:
  5. [8] C. Blum, and M. Sampels, ”An ant colony optimization algorithm for shop scheduling problems ,” Journal of Mathematical Modelling and Algorithms, 2004, pp.285-308.
    連結:
  6. [9] S.M. Johnson ,“Optimal two-and three-stage production schedules,” Naval Research Logistics Quarterly ,vol. 1 ,1954, pp.61-68.
    連結:
  7. [10] D.S. Garey, Johnson, and R. Sethi ,“the complexity of flow shop and job shop scheduling,” Mathematics of Operations Research, vol. 1, 1976, pp117-129.
    連結:
  8. [11] I. Osman, and C. Potts, “Simulated annealing for permutation flow shop scheduling,” OMEGA, vol.17,no. 6 ,1989, pp.551-557.
    連結:
  9. [12] H. Ishibuchi, S. Misaki, and H. Tanaka, ”Modified simulated annealing algorithms for the flow shop sequencing problem,” European Journal of Operational Research , vol.81,1995 ,pp.388-398.
    連結:
  10. [14] Jozef Grabowski , and Mieczyslaw Wodecki, “A very fast search algorithm for the permutation flow shop problem with makespain criterion,” European Journal of Operational Research, 2004 , pp.1891-1909
    連結:
  11. [15] T. Murata, H. Ishibuchi, and H. Tanaka, ”Genetic algorithms for flowshop scheduling problems,” Computers and Industrial Engineering , vol.30, no.4, ,1996, pp.1061–1071.
    連結:
  12. [16] C. Reeves, and T. Yamada, “Genetic algorithms, path relinking and the flowshop sequencing problem,” Evolutionary Computation , vol. 6 ,1998, pp.45-60.
    連結:
  13. [17] C. Rajendran, and H. Ziegler, “Ant-colony algorithms for permutation flowshop scheduling to minimize makespan/total flowtime of jobs,” European Journal of Operational Research, vol.155, no.2 , 2004, pp426–438.
    連結:
  14. [18] M. Fatih Tasgetiren, Yun-Chia Liang, Mehmet Sevkli, and Gunes Gencyilmaz, “A particle swarm optimization algorithm for makespan and total flowtime minimization in the permutation flowshop sequencing problem,” European Journal of Operational Research , vol.177, 2007, pp.1930-1947.
    連結:
  15. [19] Lei Yuan, and Zhen-dong Zhao, “A modified binary particle swarm optimization algorighm for permutation flow shop problem,” Proceedings of the sixth International Conference on Machine Learning and Cybernetics, Hong Kong, 2007, pp.902-907
    連結:
  16. [21] James Kennedy, and Russell C. Eberhart, “A discrete binary version of the particle swarm algorithm,” Proceedings of the IEEE International Conference, 1997, pp.4104-4109.
    連結:
  17. [23] D.S. Garey, Johnson, and R. Sethi, “The complexity of flowshop and jobshop scheduling,” Mathematics of Operations Research , vol. 1 ,1976, pp117-129.
    連結:
  18. [24] Taillard E., “Some efficient heuristic methods for the flowshop sequencing problem,” European Journal of Operational Research , vol.47 ,1990, pp.67–74.
    連結:
  19. [25] Ruben Ruiz, and Concepcion Maroto , “A comprehensive review and evaluation of permutation flowshop heuristics,” European Journal of Operational Research, vol.165 , 2005 , pp.479-494.
    連結:
  20. [26] S. Chandrasekaran, P.K. Suresh, S.G. Ponnambalam, and N. Vijayakumar, “An application of particle swarm optimization algorithm to permutioan flowshop scheduling problems to minimize makesapn, total flowtime and completion time variance,” proceeding of the 2006 IEEE international conference on automation science and engineering, china, 2006, pp.513-518.
    連結:
  21. [27] S. Johnson, “Optimal two and three-stage production schedules with setup times included,” Naval Research Logistics Quarterly , vol.1 , 1954 , pp.61-65.
    連結:
  22. [28] R.A. Dudek ,and O.F. Teuton, “Development of m-stage decision rule for scheduling n jobs through m machines,” European Journal of Operations Research, vol.12 ,no.3, 1964, pp.471–497.
    連結:
  23. [29] H.G.. Campbell , R.A. Dudek , and M.L. Smith ,”A heuristic algorithm for the n job, m machine sequencing problem,” Management Science,vol.16,no.10, 1970, pp.630-637.
    連結:
  24. [30] D. Palmer, “Sequencing jobs through a multi-stage process in the minimum total time-a quick method of obtaining a near optimum,” Operational Research Quarterly , vol. 16 ,no.1, 1965, pp.101-107.
    連結:
  25. [31] J.N. Gupta, “A functional heuristic algorithm for the flowshop scheduling problem,” Operational Research Quarterly , vol.22, no. 1, 1971, pp.39-47.
    連結:
  26. [32] M. Nawaz, E.E. Enscore, and I. Ham, “A heuristic algorithm for the m-machine, n job flow-shop sequencing problem,” OMEGA, The International Journal of Management Science, vol.11, no.1,1983, pp.91–95.
    連結:
  27. [33] J.M. Framinan , R. Leisten, and C. Rajendran,“Different initial sequences for the heuristic of Nawaz, Enscore and Ham to minimize makespan, idletime or flowtime in the static permutation flowshop sequencing problem,” International Journal of Production Research, vol. 41, no.1 , 2003 , pp.121-148.
    連結:
  28. [34] D.G.. Dannenbring, ”An evaluation of flow shop sequencing heuristics,” Management Science, vol. 23, no.11 , 1977 , pp.1174-1182.
    連結:
  29. [35] M. Widmer, and A. Hertz ,”A new heuristic method for the flow shop sequencing problem,” European Journal of Operational Research , vol. 41, 1989, pp.186-193.
    連結:
  30. [39] Zhigang Lian, Xingsheng Gu, and Bin Jiao, “a similar particle swarm optimization algorithm for permutation flowshop scheduling to minimize makespan,” European Journal of Operational Research, 2006, pp773-785.
    連結:
  31. [40] Weijun xia, and Zhiming Wu, “An effective hybrid optimization approach multi-objective flexible job-shop scheduling problem,” Computers & Industrial Engineering, vol.48 , 2005 , pp.409-425.
    連結:
  32. [43] N. Metropolis, A.W. Rosenbluth, A.H. Teller, and E. Teller,“Equation of State Calculation by Fast Computing Machines,” Journal of Chemical Physics, vol. 21, no. 6, 1953, pp.1087-
    連結:
  33. 中文部分
  34. [1] 林我聰,現場排程專家系統-應用個體導向技術建立之研究,台北:資訊與電腦出版社,1994,第43-51頁。
  35. [2] 柯惠雯,結合模擬退火法與禁忌搜尋法在流程式生產排程之應用,碩士論文,大葉大學工業工程研究所,彰化,2002。
  36. [3] 張振松,「結合基因演算法和模擬退火法在機組排程決策之應用」,資訊管理展望,第7卷,第2期,2005,第113-136頁。
  37. 英文部分
  38. [13] Talip Kellegoz, Bilal Toklu, and Ahmet kursad Turker, “A combined intensification and diversification scheme for tabu search and its application to flowshop scheduling problems,” proceedings of 5th international symposium on intelligent manufacturing system, Sakarya, 2006, pp.525-536.
  39. [20] Y. Shi, and R.C. Eberhart, “A modified particle swarm optimizer,” Proceedings of the IEEE congress on evolutionary computation, NJ:Piscataway, 1998, pp.69-173
  40. [22] A.H.G. Rinnooy Kan, “Machine Scheduling Problems: Classification,” Complexity and Computations, 1976, pp.130-194.
  41. [36] J.A. Moccellin, and M.O. Santos, , “An adaptive hybrid meta-heuristic for permutation flowshop scheduling,” Control and Cybernetics ,vol.29 ,no.3, 2000, pp.761-771.
  42. [37] L. Wang , and D.Z. Zheng. ,“An Effective Hybrid Heuristic for Flow Shop Scheduling,” The International Journal of Advanced Manufacturing Technology, vol.21, 2003 ,pp.38-44.
  43. [38] J. Kennedy ,and R.C. Eberhart, “Neural Networks: Particle Swarm Optimization,” Proceedings of the IEEE International Conference, vol. 27, 1995, pp.1942–1948.
  44. [41] Y. Shi , and R.C. Eberhart, “Parameter selection in particle swarm optimization,” Proceedings of the 7th international conference on evolutionary programming , 1998, pp.591-600.
  45. [42] X. Hu., Y. Shi. and R.C. Eberhart, ”Recent advances in particle swarm,” Proceedings of the IEEE international, 2004, pp.90-97.
Times Cited
  1. 呂建霖(2014)。應用量子二進制粒子群演算法求解智慧電網復電策略。臺北科技大學電機工程系研究所學位論文。2014。1-98。 
  2. 劉俊宏(2010)。應用粒子群演算法求解雙機流程工廠群組排程問題。虎尾科技大學經營管理研究所學位論文。2010。1-49。
  3. 張淯詠(2013)。應用二進制粒子群演算法求解最佳化短期火力機組排程。臺北科技大學電機工程系所學位論文。2013。1-92。