簡易檢索 / 詳目顯示

回結果列表
研究生： 張麗珍
Evi - Tjandradjaja
論文名稱： 應用離散粒子群最佳化演算法與瓶頸法求解混合流程型工廠排程問題
An Approach using Discrete Particle Swarm Optimization and Bottleneck Heuristic to Solve Hybrid Flow Shop Scheduling Problem
指導教授： 廖慶榮
Ching-Jong Liao
口試委員: 郭人介
Ren-Jieh Kuo
曾兆堂
Chao-Tang Tseng
學位類別： 碩士
Master
系所名稱： 管理學院 - 工業管理系
Department of Industrial Management
論文出版年： 2010
畢業學年度： 98
語文別： 英文
論文頁數： 45
中文關鍵詞： Hybrid flow shop scheduling problem 、Makespan 、Particle swarm optimization 、Simulated annealing 、Bottleneck heuristic
外文關鍵詞： Hybrid flow shop scheduling problem, Makespan, Particle swarm optimization, Simulated annealing, Bottleneck heuristic
相關次數： 點閱：319  下載：4 
分享至:
查詢本校圖書館目錄 查詢臺灣博碩士論文知識加值系統 勘誤回報

    • The hybrid flow shop (HFS) is a common manufacturing environment in many industries, such as the glass, steel, paper and textile industries. In this thesis, we present a particle swarm optimization (PSO) algorithm for the HFS scheduling problem with minimum makespan objective. The main contribution of this thesis is to develop a new approach hybridizing PSO with bottleneck heuristic to fully exploit the bottleneck stage, and with simulated annealing to help escape from local optima. A restart procedure is also employed to avoid premature convergence. The proposed PSO algorithm is tested on the benchmark problems provide by Carlier and Neron. Experiment results show that the proposed algorithm outperform all the compared algorithms in solving the HFS problem.

    The hybrid flow shop (HFS) is a common manufacturing environment in many industries, such as the glass, steel, paper and textile industries. In this thesis, we present a particle swarm optimization (PSO) algorithm for the HFS scheduling problem with minimum makespan objective. The main contribution of this thesis is to develop a new approach hybridizing PSO with bottleneck heuristic to fully exploit the bottleneck stage, and with simulated annealing to help escape from local optima. A restart procedure is also employed to avoid premature convergence. The proposed PSO algorithm is tested on the benchmark problems provide by Carlier and Neron. Experiment results show that the proposed algorithm outperform all the compared algorithms in solving the HFS problem.

    ABSTRACT i ACKNOWLEGMENTS ii CONTENTS iii LIST OF FIGURES v LIST OF TABLES vi Chapter 1 INTRODUCTION 1 1.1. Motivation 1 1.2. Research objectives 2 1.3. Organization of thesis 3 Chapter 2 PRELIMINARIES 4 2.1. Hybrid flow shop 4 2.2. Particle swarm optimization 5 2.2.1. The idea of PSO 5 2.2.2. Basic PSO parameters 6 2.2.3. Continuous PSO 7 2.2.4. Discrete PSO 10 2.3. Simulated annealing 11 2.3.1. The idea of SA 11 2.3.2. Basic SA parameters 12 2.3.3. SA algorithm 13 Chapter 3 PROPOSED ALGORITHMS 15 3.1. Mathematical formulation 15 3.2. Proposed pure PSO algorithm 16 3.2.1. Solution representation 17 3.2.2. Update of particle 17 3.2.3. Crossover operator 19 3.2.4. Mutation operators 19 3.3. Bottleneck heuristic 20 3.4. Local search 23 3.5. Restart procedure 24 3.6. Proposed PSO algorithm 25 Chapter 4 EXPERIMENTAL RESULTS 27 4.1. Design of experiment 27 4.2. Preliminary experiment 28 4.3. Experiment results 31 4.4. User interface 36 Chapter 5 CONCLUSIONS 38 5.1. Conclusions 38 5.2. Future studies 39 REFERENCES 41

    [1] Brah, S.A., & Hunsucker, J.L. (1991). “Branch and bound algorithm for the flow shop with multiple processors”. European Journal of Operational Research, 51, 88–99.
    [2] Portmann, M.C., Vignier, A., Dardilhac, D., & Dezalay, D. (1998). “Branch and bound crossed with GA to solve hybrid flowshops”. European Journal of Operational Research, 107, 389–400.
    [3] Neron, E., Baptise, P., & Gupta, J.N.D. (2001). “Solving hybrid flow shop problem using energetic reasoning and global operations”. Omega, 29, 501-511.
    [4] Riane, F., Artibs, A., & Elmaghraby, S.E. (1998). “A hybrid three stage flow shop problem: Efficient heuristics to minimize makespan”. European Journal of Operational Research, 109, 321-329
    [5] Gupta, J.N.D. (1988). “Two-stage, hybrid flowshop scheduling problem”. Journal of the Operational Research Society, 39, 359–364.
    [6] Gupta, J.N.D., & Tunc, E.A. (1991). “Schedules for a two stage hybrid flowshop with parallel machines at the second stage”. International Journal of Production Research, 29, 1489–1502.
    [7] Gupta, J.N.D., Hariri, A.M.A., & Potts, C.N. (1997). “Scheduling a two-stage hybrid flow shop with parallel machines at the first stage”. Annals of Operations Research, 69, 171–191.
    [8] Lin, H.T., & Liao, C.J. (2003). “A case study in a two-stage hybrid flow shop with setup time and dedicated machines”. International Journal of Production Economics, 86, 133-143.
    [9] Gupta, J.N.D., & Tunc, E.A. (1994). “Scheduling a two-stage hybrid flowshop with separable setup and removal times”. European Journal Operation Research, 77, 415–428.
    [10] Heydari, M., & Fakhrzad, M.B. (2008). “A heuristic algorithm for hybrid flow shop production scheduling to minimize the sum of the earliness and tardiness costs”. Journal of the Chinese Institute of Industrial Engineers, 25, 105-115.
    [11] Janiak, A., Kozan, E., Lichtenstein, M., & Oğuz, C. (2007). “Metaheuristic approaches to hybrid flow shop scheduling problem with a cost-related criterion”. International Journal of Production Economics. 105, 407-424.
    [12] Abiri, M.B., Zandieh, M., & Tabriz, A. A. (2009). “A tabu search approach to hybrid flow shop scheduling with sequence-dependent setup time”. Journal of Applied Sciences. 9, 1740-1745.
    [13] Ruiz, R., & Maroto, C. (2006). “A genetic algorithm for hybrid flowshops with sequence dependent setup times and machine eligibility”. European Journal of Operational Research. 169, 781–800.
    [14] Oğuz, C., and Ercan, M. F. (2005). “A genetic algorithm for hybrid flow-shop scheduling with multiprocessor tasks”. Journal of Scheduling. 8, 323–351.
    [15] Naseri, M.R.A., & Nia, M.A.B. (2009). “Hybrid flow shop scheduling with parallel batching”. International Journal of Production Economics. 117, 185-196.
    [16] Besbes, W., Loukil, T., & Teghem, J. (2006). “Using genetic algorithm in the multiprocessor flow shop to minimize the makespan”. Proceedings of the International Conference on Service Systems and Service Management, France, 2, 1228 –1233.
    [17] Carlier, J., & Neron, E. (2000). “An exact method for solving the multiprocessor flowshop”. R.A.I.R.O- Operations Research, 34, 1–25
    [18] Engin, O., & Doyen, A. (2004). “A new approach to solve hybrid flow shop scheduling problems by artificial immune system”. Future Generation Computer System, 20, 1083-1095.
    [19] Niu, Q., Zhou, T., & Ma, S. (2009). “A quantum-inspired immune algorithm for hybrid flow shop with makespan criterion”. Journal of Universal Computer Science, 15, 765-785
    [20] Alaykyran, K., Engin, O., & Doyen, A. (2007). “Using ant colony optimization to solve hybrid flow shop scheduling problems”. International Journal of Advanced Manufacturing Technology, 35, 541– 550.
    [21] Khalouli, S., Ghedjati, F., & Hamzaoui, A. (2009). “An integrated ant colony optimization algorithm for the hybrid flow shop scheduling problem”. Computers & Industrial Engineering, International Conference on France, 554 – 559.
    [22] Marinakis, Y., & Marinaki, M. (2010). “A hybrid multi-swarm particle swarm optimization algorithm for the probabilistic traveling salesman problem”. Computers & Operations Research, 37, 432–442.
    [23] Ai, J., & Kachitvichyanukul, V. (2009). “A particle swarm optimization for the vehicle routing problem with simultaneous pickup and delivery”. Computers & Operations Research, 36, 1693-1702.
    [24] Liao, C.J., Tseng, C.T., & Luarn, P. (2007). “A discrete version of particle swarm optimization for flowshop scheduling problems”. Computer & Operations Research, 34, 3099–3111.
    [25] Liu, B., Wang, L., & Jin, Y. (2008). “An effective hybrid PSO-based algorithm for flow shop scheduling with limited buffers”. Computers & Operations Research, 35, 2791–2806.
    [26] Pan, Q.K., Wang, L., & Qian, B. (2009). “A novel differential evolution algorithm for bi-criteria no-wait flow shop scheduling problems”. Computers & Operations Research, 36, 2498–2511.
    [27] Pan, Q.K., Tasgetiren, M.F., & Liang, Y.C. (2008). “A discrete particle swarm optimization algorithm for the no-wait flowshop scheduling problem”. Computers & Operations Research, 35, 2807-2839.
    [28] Sha, D.Y., & Hsu, C.Y. (2008). “A new particle swarm optimization for the open shop scheduling problem”. Computers & Operations Research, 35, 3243–3261.
    [29] Hao, l., & Hu, L. (2009). “Hybrid Particle Swarm Optimization for Continuous Problem”. International Colloquium on Computing, Communication, Control, and Management, IEEE, 283-286.
    [30] Chandrasekaran, S., Ponnambalam, S.G., Suresh, R.K., & Vijayakumar, N. (2006). “A hybrid discrete particle swarm optimization algorithm to solve flow shop scheduling problems”. Cybernetics and Intelligent System IEEE Conference on June, 1-6.
    [31] Kennedy, J., & Eberhart, R.C. (1995). “Particle swarm optimization”. Proceedings of IEEE International Conference on Neural Network, Piscataway, NJ, 1942-1948.
    [32] Engelbrecht, A.P. (2005). Fundamentals of Computational Swarm Intelligent. John Wiley & Sons.
    [33] Millonas, M. (1994). Swarms, Phase Transitions, and Collective Intelligence. In C.G.Langton, editor, Artificial Life III, pages 417-445. Addison-Wiley.
    [34] Clerc, M. (2006). Particle Swarm Optimization. London: ISTE.
    [35] Kirkpatrick, S., Gelatt, Jr. C.D., & Vecchi, M.P. (1983). “Optimization by Simulated Annealing”. Science, 220, 67l-680.
    [36] Van Laarhoveb, P.J.M, & Aarts, E.H.L. (1987). Simulated Annealing: Theory and Applications. D. Reidel, Dordrecht.
    [37] Yang, X.S. (2008). Nature-Inspired Metaheuristic Algorithms. Luniver Press, United Kingdom.
    [38] Paternina-Arboleda, C.D., Montoya-Torres, J.R., Acero-Dominguez, M.J., & Herrera-Hernandez, M.C. (2008). “Scheduling jobs on k-stage flexible flow-shop”. Annals of Operations Research, 164, 29-40.
    [39] Wang, X., & Xiao, J. (2005). “PSO-based model predictive control for nonlinear processes”. Lecture Notes in Computer Science, 3611, 196–203.
    [40] Triki, E., Collette, Y., & Siarry, P. (2005). “A theoretical study on the behavior of simulated annealing leading to a new cooling schedule”. European Journal of Operational Research, 166, 77-92.
    [41] Pinedo, M. (2008). Scheduling: Theory, Algorithm, and System. Third Ed., Englewood Cliffs, NJ: Prentice-Hall.

    QR CODE