政大機構典藏-National Chengchi University Institutional Repository(NCCUR):Item 140.119/54766
English  |  正體中文  |  简体中文  |  Post-Print筆數 : 27 |  Items with full text/Total items : 113318/144297 (79%)
Visitors : 50951613      Online Users : 947
RC Version 6.0 © Powered By DSPACE, MIT. Enhanced by NTU Library IR team.
Scope Tips:
  • please add "double quotation mark" for query phrases to get precise results
  • please goto advance search for comprehansive author search
    •  Adv. Search
    Home ‧ Login ‧ Upload ‧ Help ‧ About ‧ Administer Goto mobile version
    政大典藏 > College of Commerce > Department of MIS > Theses >  Item 140.119/54766


    Please use this identifier to cite or link to this item: https://nccur.lib.nccu.edu.tw/handle/140.119/54766


    Title: 以區域最佳解為基礎求解流程式排程問題的新啟發式方法
    A new heuristic based on local best solution for Permutation Flow Shop Scheduling
    Authors: 曾宇瑞
    Tzeng, Yeu Ruey
    Contributors: 陳春龍
    陳俊龍
    曾宇瑞
    Tzeng, Yeu Ruey
    Keywords: 流程式排程
    最大流程時間
    啟發式方法
    Permutation Flow Shop Scheduling
    Makespan
    Metaheuristic
    Date: 2011
    Issue Date: 2012-10-30 11:43:59 (UTC+8)
    Abstract: 本研究開發一個以區域最佳解為基礎的群體式 (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).
    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.
    Description: 博士
    國立政治大學
    資訊管理研究所
    93356511
    100
    Source URI: http://thesis.lib.nccu.edu.tw/record/#G0093356511
    Data Type: thesis
    DOI link: http://dx.doi.org/10.1016/j.asoc.2014.12.011
    DOI: 10.1016/j.asoc.2014.12.011
    Appears in Collections:[Department of MIS] Theses

    Files in This Item:

    File SizeFormat
    651101.pdf509KbAdobe PDF2548View/Open


    All items in 政大典藏 are protected by copyright, with all rights reserved.


    社群 sharing

    著作權政策宣告 Copyright Announcement
    1.本網站之數位內容為國立政治大學所收錄之機構典藏，無償提供學術研究與公眾教育等公益性使用，惟仍請適度，合理使用本網站之內容，以尊重著作權人之權益。商業上之利用，則請先取得著作權人之授權。
    The digital content of this website is part of National Chengchi University Institutional Repository. It provides free access to academic research and public education for non-commercial use. Please utilize it in a proper and reasonable manner and respect the rights of copyright owners. For commercial use, please obtain authorization from the copyright owner in advance.

    2.本網站之製作，已盡力防止侵害著作權人之權益，如仍發現本網站之數位內容有侵害著作權人權益情事者，請權利人通知本網站維護人員(nccur@nccu.edu.tw)，維護人員將立即採取移除該數位著作等補救措施。
    NCCU Institutional Repository is made to protect the interests of copyright owners. If you believe that any material on the website infringes copyright, please contact our staff(nccur@nccu.edu.tw). We will remove the work from the repository and investigate your claim.
    DSpace Software Copyright © 2002-2004  MIT &  Hewlett-Packard  /   Enhanced by   NTU Library IR team Copyright ©   - Feedback