學術產出-學位論文
文章檢視/開啟
書目匯出
-
題名 以區域最佳解為基礎求解流程式排程問題的新啟發式方法
A new heuristic based on local best solution for Permutation Flow Shop Scheduling作者 曾宇瑞
Tzeng, Yeu Ruey貢獻者 陳春龍<br>陳俊龍
曾宇瑞
Tzeng, Yeu Ruey關鍵詞 流程式排程
最大流程時間
啟發式方法
Permutation Flow Shop Scheduling
Makespan
Metaheuristic日期 2011 上傳時間 30-十月-2012 11:43:59 (UTC+8) 摘要 本研究開發一個以區域最佳解為基礎的群體式 (population-based) 啟發式演算法(簡稱HLBS)，來求解流程式排程（flow shop）之最大流程時間的最小化問題。其中，HLBS會先建置一個跟隨模型來導引搜尋機制，然後，運用過濾策略來預防重複搜尋相同解空間而陷入區域最佳解的困境；但搜尋仍有可能會陷入區域最佳解，這時，HLBS則會啟動跳脫策略來協助跳出區域最佳解，以進入新的區域之搜尋；為驗證HLBS演算法的績效，本研究利用著名的Taillard 測試題庫來進行評估，除證明跟隨模型、過濾策略和跳脫策略的效用外，也提出實驗結果證明HLBS較其他知名群體式啟發式演算法(如基因演算法、蟻群演算法以及粒子群最佳化演算法)之效能為優。
This research proposes population-based metaheuristic based on the local best solution (HLBS) for the permutation flow shop scheduling problem (PFSP-makespan). The proposed metaheuristic operates through three mechanisms: (i) it introduces a new method to produce a trace-model for guiding the search, (ii) it applies a new filter strategy to filter the solution regions that have been reviewed and guides the search to new solution regions in order to keep the search from trapping into local optima, and (iii) it initiates a new jump strategy to help the search escape if the search does become trapped at a local optimum. Computational experiments on the well-known Taillard`s benchmark data sets will be performed to evaluate the effects of the trace-model generating rule, the filter strategy, and the jump strategy on the performance of HLBS, and to compare the performance of HLBS with all the promising population-based metaheuristics related to Genetic Algorithms (GA), Ant Colony Optimization (ACO) and Particle Swarm Optimization (PSO).參考文獻 Andreas, N. & Omirou, S. (2006). Differential evolution for sequencing and scheduling optimization. Journal of Heuristics, 12(6), 395-411.Blum, C (2005). Ant colony optimization: Introduction and recent trends. Physics of Life Reviews, 2(4), 353-373.Chen, C. L., Vempati, V. S. & Aljaber, N. (1995). An application of genetic algorithms for flow shop problems. European Journal of Operational Research, 80(2), 389-396.Chen, C. L., Neppalli, V. R. & Aljaber, N. (1996). Genetic Algorithms Applied to the Continuous Flow Shop Problem. Computers & Industrial Engineering, 30(4), 919-929.Chen, Y. M., Chen, M. C., Chang, P. C. & Chen, S. H. (2012), Extended Artificial Chromosomes Genetic Algorithm for Permutation Flowshop Scheduling problems, Computers & Industrial Engineering, 62(2), 536–545.Dorigo, M. (1992) Optimization, Learning and Natural Algorithm. Ph.D. Thesis, DEI, Politecnico di Milano, Italy.Dorigo, M. & Gambardella, L. M. (1997). Ant colony system: a cooperative learning approach to the travelling salesman problem. IEEE T Evolut Comput,1,53–66.Dorigo, M. & Stützle, T. (2004). Ant colony optimization. MIT, Cambridge.Framinan, J., Gupta, J. N. D. & Leisten, R. (2004). A review and classification of heuristics for the permutation flowshop with makespan objective. Journal of Operational Research Society, 55, 1243–1255.Garey, M. R., Johnson, D. S. & Sethi, R. (1976). The complexity of flowshop and jobshop scheduling. Mathematics of Operations Research, 1(2), 117-129. Glover, F. (1996), Tabu Search and Adaptive memory programming - Advances, applications and challenges. Interfaces in Computer Science and Operations Research. Barr, Helgason and Kennington, eds., Kluwer Academic Publishers, 1-75.Grabowski, J. & Pempera, J. (2001). New block properties for the permutation flow shop problem with application in tabu search. Journal of the Operational Research Society, 52, 210-220.Grabowski, J. & Wodecki, M. (2004). A very fast tabu search algorithm for the permutation flowshop problem with makespan criterion. Computers & Operations Research, 31(11), 1891-1909.Graham, R. L., Lawler, E. L., Lenstra, J. K. & Rinnooy Kan, A.H.G. (1979). Optimization and approximation in deterministic sequencing and scheduling : a survey. Annals of Discrete Mathematics, 5, 287-326.Hejazi, S. R. & Saghafian, S. (2005). Flowshop scheduling problems with makespan criterion: a review. International Journal of Production Research, 43(14), 2895–2929.Jin, F., Song, S.J. & Wu, C. (2007). An improved version of the NEH algorithm and its application to large-scale flow-shop scheduling problems. IIE Transactions, 39, 229-234.Kennedy, J. & Eberhart, R. (1995). Particle swarm optimization. In Proceedings of IEEE international conference on neural network, 1942–1948.Kuo, I. H., Horng, S. J., Kao, T. W., Lin, T. L., Lee, C. L., Terano, T. & Pan, Y. (2009). An efficient flow-shop scheduling algorithm based on a hybrid particle swarm optimization model. Expert Systems with Applications, 36(3), 7027–7032. Lian, Z., Gu, X. & Jiao, B. (2006). A similar particle swarm optimization algorithm for permutation flowshop scheduling to minimize makespan. Applied Mathematics and Computation, 175(1), 773–785.Lian, Z., Gu, X. & Jiao, B. (2008). A novel particle swarm optimization algorithm for permutation flow-shop scheduling to minimize makespan. Chaos, Solitons and Fractals, 35, 851–861.Liao, C. J., Tseng, C. T. & Luarn, P. (2007). A discrete version of particle swarm optimization for flowshop scheduling problems. Computers & Operations Research, 34(10), 3099-3111.Lin, S. W & Ying, K. C. (2011). Minimizing makespan and total flowtime in permutation flowshops by a bi-objective multi-start simulated-annealing algorithm. Computers & Operations Research, doi:10.1016/j.cor.2011.08.009.Liu, Y. F. & Liu, S. Y. (2011). A hybrid discrete artificial bee colony algorithm for permutation flowshop scheduling problem. Applied Soft Computing doi:10.1016/j.asoc.2011.10.024.Merkle, D. & Middendorf, M. (2000). An ant algorithm with a new pheromone evaluation rule for total tardiness problems. In: Proceedings of the EvoWorkshops, 1803(LNCS), 287–296.Nowicki, E. & Smutnicki, C. (1996). A fast tabu search algorithm for the permutation flowshop problem. European Journal of Operational Research, 91, 160-175.Ogbu, F. & Smith, D. (1990). The application of the simulated annealing algorithm to the solution of the n/m/Cmax flowshop problem. Computers & Operations Research, 17(3), 243-253.Onwubolu, G. & Davendra, D. (2006). Scheduling flow shops using differential evolution algorithm. European Journal of Operational Research, 171(2), 674-692. Osman, I. & Potts, C. (1989). Simulated annealing for permutation flow shop scheduling. OMEGA, 17(6), 551-557.Pan, Q. K., Tasgetiren, M. F. & Liang, Y. C. (2008a). A discrete particle swarm optimization algorithm for the no-wait flowshop scheduling problem. Computer & Operations Research, 35(9), 2807-2839.Pan, Q. K., Tasgetiren, M. F. & Liang, Y. C. (2008b). A Discrete differential evolution algorithm for the permutation flowshop scheduling problem. Computers & Industrial Engineering. 55(4), 795-816.Rajendran, C. & Ziegler, H. (2004). Ant-colony algorithms for permutation flowshop scheduling to minimize makespan/total flowtime of jobs. European Journal of Operational Research, 155(2), 426–438.Rameshkumar, K., Suresh, R. K. & Mohanasundaram, K. M. (2005). Discrete particle swarm optimization (DPSO) algorithm for permutation flowshop scheduling to minimize makespan. In Proceedings of the ICNC (3), 572–581.Reeves, C. R. (1993). Improving the efficiency of tabu search for machine sequencing problem. Journal of the Operational Research Society, 44(4), 375–382.Reeves, C. R. (1995). A genetic algorithm for flowshop sequencing. Computers & Operations Research. 22(1), 5–13.Reeves, C. R. & Yamada, T. (1998). Genetic algorithms, path relinking and the flowshop sequencing problem. Evolutionary Computation, 6(1), 45–60.Ruiz, R. & Maroto, C. (2005). A comprehensive review and evaluation of permutation flowshop heuristics. European Journal of Operational Research 165, 479–494.Ruiz, R., Maroto, C. & Alcaraz, J. (2006). Two new robust genetic algorithms for the flowshop scheduling problem. OMEGA, 34, 461–47. Ruiz, R. & Stützle, T. (2007). A simple and effective iterated greedy algorithm for the permutation flowshop scheduling problem. European Journal of Operational Research, 177(3),2033-2049.Stützle, T. (1998a). An ant approach to the flow shop problem. In: Proceedings of the 6th European Congress on Intelligent Techniques & Soft Computing, Aachen, Germany, 3, 1560-1564.Stützle, T. (1998b). Applying iterated local search to the permutation flowshop problem. Technical Report, AIDA-98-04, FG Intellektik, TU Darmstadt.Taillard, E. (1990). Some efficient heuristic methods for the flow shop sequencing problem. European Journal of Operational Research, 47(1), 65–74.Taillard, E. (1993). Benchmarks for basic scheduling problems. European Journal of Operational Research, 64(2), 278-285.Tasgetiren, M. F., Sevkli, M., Liang, Y. C. & Gencyilmaz, G. (2004). Particle swarm optimization algorithm for permutation flowshop sequencing problem. In Proceedings of ant colony optimization and swarm intelligence (ANTS2004), LNCS 3172, Springer-Verlag, 381-89.Watson, J. P., Barbulescu, L., Whitley, L. D. & Howe, A. E. (2002). Contrasting structured and random permutation flowshop scheduling problems: Search space topology and algorithm performance. ORSA Journal of Computing, 14(2), 98-123.Widmer, M. & Hertz, A. (1989). A new heuristic method for the flow shop sequencing problem. European Journal of Operational Research, 41(2), 186-193.Ying, K. C. & Liao, C.J. (2004). An ant colony system for permutation flow-shop sequencing. Computers & Operations Research, 31(5), 791-801. Zhang, C., Jiaxu, N. & Dantong, O. (2010). A hybrid alternate two phases particle swarm optimization algorithm for flow shop scheduling problem. Computers and Industrial Engineering, 58(1), 1–11.Zhang, J., Zhang, C. & Liang, S. (2010). The circular discrete particle swarm optimization algorithm for flow shop scheduling problem. Expert Systems with Applications, 37, 5827–5834.Zobolas, G. I., Tarantilis, C. D. & Ioannou, G. (2009). Minimizing makespan in permutation flow shop scheduling problems using a hybrid metaheuristic algorithm. Computers & Operations Research, 36(4), 1249-1267. 描述 博士
國立政治大學
資訊管理研究所
93356511
100資料來源 http://thesis.lib.nccu.edu.tw/record/#G0093356511 資料類型 thesis DOI http://dx.doi.org/10.1016/j.asoc.2014.12.011 dc.contributor.advisor 陳春龍<br>陳俊龍 zh_TW dc.contributor.author (作者) 曾宇瑞 zh_TW dc.contributor.author (作者) Tzeng, Yeu Ruey en_US dc.creator (作者) 曾宇瑞 zh_TW dc.creator (作者) Tzeng, Yeu Ruey en_US dc.date (日期) 2011 en_US dc.date.accessioned 30-十月-2012 11:43:59 (UTC+8) - dc.date.available 30-十月-2012 11:43:59 (UTC+8) - dc.date.issued (上傳時間) 30-十月-2012 11:43:59 (UTC+8) - dc.identifier (其他 識別碼) G0093356511 en_US dc.identifier.uri (URI) http://nccur.lib.nccu.edu.tw/handle/140.119/54766 - dc.description (描述) 博士 zh_TW dc.description (描述) 國立政治大學 zh_TW dc.description (描述) 資訊管理研究所 zh_TW dc.description (描述) 93356511 zh_TW dc.description (描述) 100 zh_TW dc.description.abstract (摘要) 本研究開發一個以區域最佳解為基礎的群體式 (population-based) 啟發式演算法(簡稱HLBS)，來求解流程式排程（flow shop）之最大流程時間的最小化問題。其中，HLBS會先建置一個跟隨模型來導引搜尋機制，然後，運用過濾策略來預防重複搜尋相同解空間而陷入區域最佳解的困境；但搜尋仍有可能會陷入區域最佳解，這時，HLBS則會啟動跳脫策略來協助跳出區域最佳解，以進入新的區域之搜尋；為驗證HLBS演算法的績效，本研究利用著名的Taillard 測試題庫來進行評估，除證明跟隨模型、過濾策略和跳脫策略的效用外，也提出實驗結果證明HLBS較其他知名群體式啟發式演算法(如基因演算法、蟻群演算法以及粒子群最佳化演算法)之效能為優。 zh_TW dc.description.abstract (摘要) This research proposes population-based metaheuristic based on the local best solution (HLBS) for the permutation flow shop scheduling problem (PFSP-makespan). The proposed metaheuristic operates through three mechanisms: (i) it introduces a new method to produce a trace-model for guiding the search, (ii) it applies a new filter strategy to filter the solution regions that have been reviewed and guides the search to new solution regions in order to keep the search from trapping into local optima, and (iii) it initiates a new jump strategy to help the search escape if the search does become trapped at a local optimum. Computational experiments on the well-known Taillard`s benchmark data sets will be performed to evaluate the effects of the trace-model generating rule, the filter strategy, and the jump strategy on the performance of HLBS, and to compare the performance of HLBS with all the promising population-based metaheuristics related to Genetic Algorithms (GA), Ant Colony Optimization (ACO) and Particle Swarm Optimization (PSO). en_US dc.description.tableofcontents Chapter 1. Introduction 1Chapter 2. Literature review 32.1 Problem statement: PFSP-makespan 32.2 Genetic Algorithms (GA) 42.3 Ant Colony Optimization (ACO) 62.4 Particle Swarm Optimization (PSO) 7Chapter 3. The proposed metaheuristic (HLBS) 113.1 Trace-model generating rule and solution construction method 123.2 Filter strategy 163.3 Jump strategy 18Chapter 4. Computational experiments of HLBS 204.1 Computational experiments of B-HLBS 204.2 Computational experiments of A-HLBS 28Chapter 5. Conclusions and further research 35References 37 zh_TW dc.language.iso en_US - dc.source.uri (資料來源) http://thesis.lib.nccu.edu.tw/record/#G0093356511 en_US dc.subject (關鍵詞) 流程式排程 zh_TW dc.subject (關鍵詞) 最大流程時間 zh_TW dc.subject (關鍵詞) 啟發式方法 zh_TW dc.subject (關鍵詞) Permutation Flow Shop Scheduling en_US dc.subject (關鍵詞) Makespan en_US dc.subject (關鍵詞) Metaheuristic en_US dc.title (題名) 以區域最佳解為基礎求解流程式排程問題的新啟發式方法 zh_TW dc.title (題名) A new heuristic based on local best solution for Permutation Flow Shop Scheduling en_US dc.type (資料類型) thesis en dc.relation.reference (參考文獻) Andreas, N. & Omirou, S. (2006). Differential evolution for sequencing and scheduling optimization. Journal of Heuristics, 12(6), 395-411.Blum, C (2005). Ant colony optimization: Introduction and recent trends. Physics of Life Reviews, 2(4), 353-373.Chen, C. L., Vempati, V. S. & Aljaber, N. (1995). An application of genetic algorithms for flow shop problems. European Journal of Operational Research, 80(2), 389-396.Chen, C. L., Neppalli, V. R. & Aljaber, N. (1996). Genetic Algorithms Applied to the Continuous Flow Shop Problem. Computers & Industrial Engineering, 30(4), 919-929.Chen, Y. M., Chen, M. C., Chang, P. C. & Chen, S. H. (2012), Extended Artificial Chromosomes Genetic Algorithm for Permutation Flowshop Scheduling problems, Computers & Industrial Engineering, 62(2), 536–545.Dorigo, M. (1992) Optimization, Learning and Natural Algorithm. Ph.D. Thesis, DEI, Politecnico di Milano, Italy.Dorigo, M. & Gambardella, L. M. (1997). Ant colony system: a cooperative learning approach to the travelling salesman problem. IEEE T Evolut Comput,1,53–66.Dorigo, M. & Stützle, T. (2004). Ant colony optimization. MIT, Cambridge.Framinan, J., Gupta, J. N. D. & Leisten, R. (2004). A review and classification of heuristics for the permutation flowshop with makespan objective. Journal of Operational Research Society, 55, 1243–1255.Garey, M. R., Johnson, D. S. & Sethi, R. (1976). The complexity of flowshop and jobshop scheduling. Mathematics of Operations Research, 1(2), 117-129. Glover, F. (1996), Tabu Search and Adaptive memory programming - Advances, applications and challenges. Interfaces in Computer Science and Operations Research. Barr, Helgason and Kennington, eds., Kluwer Academic Publishers, 1-75.Grabowski, J. & Pempera, J. (2001). New block properties for the permutation flow shop problem with application in tabu search. Journal of the Operational Research Society, 52, 210-220.Grabowski, J. & Wodecki, M. (2004). A very fast tabu search algorithm for the permutation flowshop problem with makespan criterion. Computers & Operations Research, 31(11), 1891-1909.Graham, R. L., Lawler, E. L., Lenstra, J. K. & Rinnooy Kan, A.H.G. (1979). Optimization and approximation in deterministic sequencing and scheduling : a survey. Annals of Discrete Mathematics, 5, 287-326.Hejazi, S. R. & Saghafian, S. (2005). Flowshop scheduling problems with makespan criterion: a review. International Journal of Production Research, 43(14), 2895–2929.Jin, F., Song, S.J. & Wu, C. (2007). An improved version of the NEH algorithm and its application to large-scale flow-shop scheduling problems. IIE Transactions, 39, 229-234.Kennedy, J. & Eberhart, R. (1995). Particle swarm optimization. In Proceedings of IEEE international conference on neural network, 1942–1948.Kuo, I. H., Horng, S. J., Kao, T. W., Lin, T. L., Lee, C. L., Terano, T. & Pan, Y. (2009). An efficient flow-shop scheduling algorithm based on a hybrid particle swarm optimization model. Expert Systems with Applications, 36(3), 7027–7032. Lian, Z., Gu, X. & Jiao, B. (2006). A similar particle swarm optimization algorithm for permutation flowshop scheduling to minimize makespan. Applied Mathematics and Computation, 175(1), 773–785.Lian, Z., Gu, X. & Jiao, B. (2008). A novel particle swarm optimization algorithm for permutation flow-shop scheduling to minimize makespan. Chaos, Solitons and Fractals, 35, 851–861.Liao, C. J., Tseng, C. T. & Luarn, P. (2007). A discrete version of particle swarm optimization for flowshop scheduling problems. Computers & Operations Research, 34(10), 3099-3111.Lin, S. W & Ying, K. C. (2011). Minimizing makespan and total flowtime in permutation flowshops by a bi-objective multi-start simulated-annealing algorithm. Computers & Operations Research, doi:10.1016/j.cor.2011.08.009.Liu, Y. F. & Liu, S. Y. (2011). A hybrid discrete artificial bee colony algorithm for permutation flowshop scheduling problem. Applied Soft Computing doi:10.1016/j.asoc.2011.10.024.Merkle, D. & Middendorf, M. (2000). An ant algorithm with a new pheromone evaluation rule for total tardiness problems. In: Proceedings of the EvoWorkshops, 1803(LNCS), 287–296.Nowicki, E. & Smutnicki, C. (1996). A fast tabu search algorithm for the permutation flowshop problem. European Journal of Operational Research, 91, 160-175.Ogbu, F. & Smith, D. (1990). The application of the simulated annealing algorithm to the solution of the n/m/Cmax flowshop problem. Computers & Operations Research, 17(3), 243-253.Onwubolu, G. & Davendra, D. (2006). Scheduling flow shops using differential evolution algorithm. European Journal of Operational Research, 171(2), 674-692. Osman, I. & Potts, C. (1989). Simulated annealing for permutation flow shop scheduling. OMEGA, 17(6), 551-557.Pan, Q. K., Tasgetiren, M. F. & Liang, Y. C. (2008a). A discrete particle swarm optimization algorithm for the no-wait flowshop scheduling problem. Computer & Operations Research, 35(9), 2807-2839.Pan, Q. K., Tasgetiren, M. F. & Liang, Y. C. (2008b). A Discrete differential evolution algorithm for the permutation flowshop scheduling problem. Computers & Industrial Engineering. 55(4), 795-816.Rajendran, C. & Ziegler, H. (2004). Ant-colony algorithms for permutation flowshop scheduling to minimize makespan/total flowtime of jobs. European Journal of Operational Research, 155(2), 426–438.Rameshkumar, K., Suresh, R. K. & Mohanasundaram, K. M. (2005). Discrete particle swarm optimization (DPSO) algorithm for permutation flowshop scheduling to minimize makespan. In Proceedings of the ICNC (3), 572–581.Reeves, C. R. (1993). Improving the efficiency of tabu search for machine sequencing problem. Journal of the Operational Research Society, 44(4), 375–382.Reeves, C. R. (1995). A genetic algorithm for flowshop sequencing. Computers & Operations Research. 22(1), 5–13.Reeves, C. R. & Yamada, T. (1998). Genetic algorithms, path relinking and the flowshop sequencing problem. Evolutionary Computation, 6(1), 45–60.Ruiz, R. & Maroto, C. (2005). A comprehensive review and evaluation of permutation flowshop heuristics. European Journal of Operational Research 165, 479–494.Ruiz, R., Maroto, C. & Alcaraz, J. (2006). Two new robust genetic algorithms for the flowshop scheduling problem. OMEGA, 34, 461–47. Ruiz, R. & Stützle, T. (2007). A simple and effective iterated greedy algorithm for the permutation flowshop scheduling problem. European Journal of Operational Research, 177(3),2033-2049.Stützle, T. (1998a). An ant approach to the flow shop problem. In: Proceedings of the 6th European Congress on Intelligent Techniques & Soft Computing, Aachen, Germany, 3, 1560-1564.Stützle, T. (1998b). Applying iterated local search to the permutation flowshop problem. Technical Report, AIDA-98-04, FG Intellektik, TU Darmstadt.Taillard, E. (1990). Some efficient heuristic methods for the flow shop sequencing problem. European Journal of Operational Research, 47(1), 65–74.Taillard, E. (1993). Benchmarks for basic scheduling problems. European Journal of Operational Research, 64(2), 278-285.Tasgetiren, M. F., Sevkli, M., Liang, Y. C. & Gencyilmaz, G. (2004). Particle swarm optimization algorithm for permutation flowshop sequencing problem. In Proceedings of ant colony optimization and swarm intelligence (ANTS2004), LNCS 3172, Springer-Verlag, 381-89.Watson, J. P., Barbulescu, L., Whitley, L. D. & Howe, A. E. (2002). Contrasting structured and random permutation flowshop scheduling problems: Search space topology and algorithm performance. ORSA Journal of Computing, 14(2), 98-123.Widmer, M. & Hertz, A. (1989). A new heuristic method for the flow shop sequencing problem. European Journal of Operational Research, 41(2), 186-193.Ying, K. C. & Liao, C.J. (2004). An ant colony system for permutation flow-shop sequencing. Computers & Operations Research, 31(5), 791-801. Zhang, C., Jiaxu, N. & Dantong, O. (2010). A hybrid alternate two phases particle swarm optimization algorithm for flow shop scheduling problem. Computers and Industrial Engineering, 58(1), 1–11.Zhang, J., Zhang, C. & Liang, S. (2010). The circular discrete particle swarm optimization algorithm for flow shop scheduling problem. Expert Systems with Applications, 37, 5827–5834.Zobolas, G. I., Tarantilis, C. D. & Ioannou, G. (2009). Minimizing makespan in permutation flow shop scheduling problems using a hybrid metaheuristic algorithm. Computers & Operations Research, 36(4), 1249-1267. zh_TW dc.identifier.doi (DOI) 10.1016/j.asoc.2014.12.011 en_US dc.doi.uri (DOI) http://dx.doi.org/10.1016/j.asoc.2014.12.011 en_US
