臺灣博碩士論文加值系統

粒子群演算法(Particle Swarm Optimization, PSO)是一種群體搜尋最佳化演算法，於1995年被提出。原始的PSO是應用於求解連續最佳化問題。當PSO用來求解離散最佳化問題時，我們必須修改粒子位置、粒子移動以及粒子速度的表達方式，讓PSO更適於求解離散最佳化問題問題。本研究之主要貢獻為提出數種適合求解離散最佳化問題之PSO設計。這些新的設計和原始的設計不同且更適合求解離散最佳化問題。
在本篇論文中，我們將分別提出適合求解零壹多限制式背包問題(Multidimensional 0-1 Knapsack Problem, MKP)、零工式排程問題(Job Shop Scheduling Problem JSSP)以及開放式排程問題(Open Shop Scheduling Problem, OSSP)的PSO。在求解MKP的PSO中，我們以零壹變數表達粒子位置，以區塊建立(building blocks)的概念表達粒子移動方式。在求解JSSP的PSO中，我們以偏好列表(preference-list)表達粒子位置，以交換運算子(swap operator)表達粒子移動方式。在求解OSSP的PSO中，我們以優先權重(priority)表達粒子位置，以插入運算子(insert operator)表達粒子移動方式。除此之外，我們在求解MKP的PSO中加入區域搜尋法(local search)，在求解JSSP的PSO與塔布搜尋(tabu search)混合，以及將求解OSSP的PSO與集束搜尋法(beam search)混合。計算結果顯示，我們的PSO比其它傳統的啟發式解法要來的好。

Particle Swarm Optimization (PSO) is a population-based optimization algorithm, which was developed in 1995. The original PSO is used to solve continuous optimization problems. Due to solution spaces of discrete optimization problems are discrete, we have to modify the particle position representation, particle movement, and particle velocity to better suit PSO for discrete optimization problems. The contribution of this research is that we proposed several PSO designs for discrete optimization problems. The new PSO designs are better suit for discrete optimization problems, and differ from the original PSO.
In this thesis, we propose three PSOs for three discrete optimization problems respectively: the multidimensional 0-1 knapsack problem (MKP), the job shop scheduling problem (JSSP) and the open shop scheduling problem (OSSP). In the PSO for MKP, the particle position is represented by binary variables, and the particle movement are based on the concept of building blocks. In the PSO for JSSP, we modified the particle position representation using preference-lists and the particle movement using a swap operator. In the PSO for OSSP, we modified the particle position representation using priorities and the particle movement using an insert operator. Furthermore, we hybridized the PSO for MKP with a local search procedure, the PSO for JSSP with tabu search (TS), and the PSO for OSSP with beam search (BS). The computational results show that our PSOs are better than other traditional metaheuristics.

中文摘要 Ⅰ
ABSTRACT Ⅱ
誌謝 Ⅲ
CONTENTS Ⅳ
LIST OF FIGURES Ⅶ
LIST OF TABLES Ⅷ
CHAPTER 1 INTRODUCTION 1
1.1 Research Motivations 1
1.2 Research Objectives 1
1.3 Organization 2
CHAPTER 2 LITERATURE REVIEW 3
2.1 Particle Swarm Optimization 3
2.2 Multidimensional 0-1 Knapsack Problem 3
2.3 Job Shop Scheduling Problem 9
2.4 Open Shop Scheduling Problem 11
CHAPTER 3 DEVELOPING A PARTICLE SWARM OPTIMIZATION FOR A DISCRETE OPTIMIZATION PROBLEM 13
3.1 Particle Position Representation 13
3.2 Particle Velocity and Particle Movement 14
3.3 Decoding Operator 15
3.4 Other Search Strategies 15
3.5 The Process to Develop a New Particle Swarm Optimization 16
CHAPTER 4 A DISCRETE BINARY PARTICLE SWARM OPTIMIZATION FOR THE MULTIDIMENSIONAL 0-1 KNAPSACK PROBLEM 18
4.1 Particle Position Representation 19
4.2 Particle Velocity 20
4.3 Particle Movement 21
4.4 Repair Operator 22
4.5 The Diversification Strategy 24
4.6 The Selection Strategy 25
4.7 Local Search 26
4.8 Computational Results 28
4.9 Concluding Remarks 31
4.10 Appendix 33
CHAPTER 5 A PARTICLE SWARM OPTIMIZATION FOR THE JOB SHOP SCHEDULING PROBLEM 34
5.1 Particle Position Representation 34
5.2 Particle Velocity 44
5.3 Particle Movement 45
5.4 The Diversification Strategy 50
5.5 Local Search 51
5.6 Computational Results 53
5.7 Concluding Remarks 62
5.8 Appendix 64
CHAPTER 6 A PARTICLE SWARM OPTIMIZATION FOR THE OPEN SHOP SCHEDULING PROBLEM 65
6.1 Particle Position Representation 65
6.2 Particle Velocity 68
6.3 Particle Movement 70
6.4 Decoding Operators 72
6.4.1 Decoding Operator 1 (A-ND) 75
6.4.2 Decoding Operator 2 (mP-ASG) 75
6.4.3 Decoding Operator 3 (mP-ASG2) 77
6.4.4 Decoding Operator 4 (mP-ASG2+BS) 79
6.5 The Diversification Strategy 81
6.6 Computational Results 81
6.6.1 Comparison of Decoding Operators 82
6.6.2 Comparison with Other Metaheuristics 85
6.7 Concluding Remarks 93
6.8 Appendix 95
CHAPTER 7 CONCLUSION AND FUTURE WORK 96
7.1 Conclusions 96
7.2 Future Works 97
References 98

1.Adams, J., Balas, E., & Zawack, D. (1988). The shifting bottleneck procedure for job shop scheduling. Management Science, 34(3), 391-401.
2.Alcaide, D., Sicilia, J., & Vigo, D. (1997). Heuristic approaches for the minimum makespan open shop problem. Trabajos de Investigación Operativa, 5(2), 283-296.
3.Allahverdi, A, & Al-Anzi, F.S. (2006). A PSO and a tabu search heuristics for the assembly scheduling problem of the two-stage distributed database application. Computers and Operations Research, 33(4), 1056-1080.
4.Angeline, P.J. (1998). Using selection to improve particle swarm optimization. Proceedings of the IEEE International Conference on Evolutionary Computation, 84–89.
5.Bagchi, T.P. (1999). Multiobjective scheduling by genetic algorithms. Kluwer Academic Publishers.
6.Balas, E., & Vazacopoulos, A. (1998). Guided local search with shifting bottleneck for job shop scheduling. Management Science, 44(2), 262-275.
7.Bean, J. (1994). Genetic algorithms and random keys for sequencing and optimization. Operations Research Society of America (ORSA) Journal on Computing, 6, 154-160.
8.Beasley J.E. (1990). OR-Library: distributing test problems by electronic mail. Journal of the Operational Research Society, 14, 1069-1072.
9.Blum, C. (2005). Beam-ACO—hybridizing ant colony optimization with beam search: and application to open shop scheduling. Computers & Operations Research, 32, 1565-1591.
10.Brucker, P., Hurink, J., Jurisch, B., & Wöstmann, B. (1997). A branch & bound algorithm for the open-shop problem. Discrete Applied Mathematics, 76, 43-59.
11.Chu, P.C., & Beasley, J.E. (1998). A genetic algorithm for the multidimensional knapsack problem. Journal of Heuristic, 4, 63–86.
12.Colak, S., & Agarwal, A. (2005). Non-greedy heuristics and augmented neural networks for the open-shop scheduling problem. Naval Research Logistics, 52, 631-644.
13.Davis, L. (1985). Job shop scheduling with genetic algorithm. Proceedings of the first International Conference on Genetic Algorithms, 163-140.
14.Dorndorf, U., Pesch, E., & Phan-Huy, T. (2001). Solving the open-shop scheduling problem. Journal of scheduling, 4(3), 157-174.
15.Drexl, A. (1988). A simulated annealing approach to the multiconstraint zero-one knapsack problem. Computing, 40, 1–8.
16.Eberhart R., & Shi Y. (2001). Particle swarm optimization: developments, applications and resources. Proceedings of the 2001 IEEE Congress on Evolutionary Computation, 81-86.
17.Fisher, H., & Thompson, G.L. (1963). Industrial Scheduling. Englewood Cliffs, NJ: Prentice-Hall.
18.French, S. (1982). Sequencing and scheduling: an introduction to the mathematics of the job-shop. UK: Horwood.
19.Fréville, A. (2004). The multidimensional 0–1 knapsack problem: An overview. European Journal of Operational Research, 155(1), 1–21.
20.Fréville, A., & Hanafi, S. (2005). The multidimensional 0-1 knapsack problem — bounds and computational aspects. Annals of Operations Research, 139, 195–227.
21.Garey, M.R., Johnson, D.S., & Sethi, R. (1976). The complexity of flowshop and jobshop scheduling. Mathematics of Operations Research, 1, 117-129.
22.Gen, M., & Cheng, R. (1997). Genetic algorithms and engineering design. New York: Wiley.
23.Giffler, J., & Thompson, G.L. (1960). Algorithms for solving production scheduling problems. Operations Research, 8, 487-503.
24.Glover, F. (1986). Future paths for integer programming and links to artificial intelligence. Computers and Operations Research, 13, 533-549.
25.Glover, F. (1989). Tabu search: Part I. ORSA Journal on Computing, 1, 190-206.
26.Glover, F. (1990). Tabu search: Part II. ORSA Journal on Computing, 2, 4-32.
27.Glover, F., & Kochenberger G.A. (1996). Critical event tabu search for multidimensional knapsack problems, in I.H. Osman, and J.P. Kelly, (Eds.), Metaheuristics: The Theory and Applications, Kluwer Academic Publishers, Dordrecht, pp.407–427.
28.Goldberg, D.E. (2002). The Design of Innovation: Lessons from and for Competent Genetic Algorithms. Kluwer Academic Publishers, Dordrecht.
29.Gonçalves, J.F., & Beirão, N.C., (1999). Um Algoritmo Genético Baseado em Chaves Aleatórias para Sequenciamento de Operações. Revista Associação Portuguesa de Desenvolvimento e Investigação Operacional 19, 123-137 (in Portuguese).
30.Gonçalves, J.F., Mendes, J.J. M., & Resende, M.G.C. (2005). A hybrid genetic algorithm for the job shop scheduling problem. European Journal of Operational Research, 167(1), 77-95.
31.Gonzalez, T., & Sahni, S. (1976). Open shop scheduling to minimize finish time. Journal of the ACM, 23(4), 665-679.
32.Guéret, C., & Prins, C. (1998). Classical and new heuristics for the open-shop problem: a computational evaluation, European Journal of Operational Research, 107(2), 306-314.
33.Guéret, C., & Prins, C. (1999). A new lower bound for the open-shop problem. Annals of Operations Research, 92, 165-183.
34.Hanafi, S., & Fréville, A. (1998). An efficient tabu search approach for the 0-1 multidimensional knapsack problem. European Journal of Operational Research, 106, 659–675.
35.Jain, A.S., Rangaswamy, B., & Meeran, S. (2000). New and “stronger” job-shop neighbourhoods: a focus on the method of Nowicki and Smutnicki (1996). Journal of Heuristics, 6, 457-480.
36.Jin, Y.X., Cheng, H.Z., Yan, J.Y., Zhang, L. (2007). New discrete method for particle swarm optimization and its application in transmission network expansion planning. Electric Power Systems Research, 77(3-4), 227-233.
37.Kennedy, J., & Eberhart, R.C. (1995). Particle swarm optimization. Proceedings of the 1995 IEEE International Conference on Neural Networks, 4, 1942-1948.
38.Kennedy, J., & Eberhart, R.C. (1997). A discrete binary version of the particle swarm algorithm. Proceedings of the IEEE International Conference on Systems, Man, and Cybernetics, 5, 4104–4108.
39.Kobayashi, S., Ono, I., & Yamamura, M. (1995). An efficient genetic algorithm for job shop scheduling problems. Proceedings of the Sixth International Conference on Genetic Algorithms, 506-511.
40.Lawrence, S., (1984). Resource constrained project scheduling: An experimental investigation of heuristic scheduling techniques. Graduate School of Industrial Administration (GSIA), Carnegie Mellon University, Pittsburgh, PA.
41.Li, N., Liu, F., Sun, D., & Huang, C. (2004). Particle Swarm Optimization for Constrained Layout Optimization. Proceedings of Fifth World Congress on Intelligent Control and Automation (WCICA 2004), 3, 2214-2218.
42.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.
43.Liao, C.J., Tseng, C.T., & Pin, L. (2007). A discrete version of particle swarm optimization for flowshop scheduling problems. Computers and Operations Research, 34(10), 3099-3111.
44.Liaw, C-F. (1999a). Applying simulated annealing to the open shop scheduling problem. IIE Transactions, 31, 457-465.
45.Liaw, C-F. (1999b). A tabu search algorithm for the open shop scheduling problem. Computers & Operations Research, 26, 109-126.
46.Liaw, C-F (2000). A hybrid genetic algorithm for the open shop scheduling problem. European Journal of Operational Research, 124, 28-42.
47.Lourenço, H.R. (1995). Local optimization and the job-shop scheduling problem. European Journal of Operational Research, 83, 347-364.
48.Mattfeld, D.C. (1996). Evolutionary Search and the Job Shop: Investigations on Genetic Algorithms for Production Scheduling. Physica-Verlag, Heidelberg, Germany.
49.Nowicki, E., & Smutnicki, C. (1996). A fast taboo search algorithm for the job shop problem. Management Science, 42(6), 797-813.
50.Osorio, M.A., Glover, F., & Hammer, P. (2002). Cutting and surrogate constraint analysis for improved multidimensional knapsack solutions. Annals of Operations Research, 117, 71–93.
51.Ow, P.S., & Morton, T.E. (1988). Filtered beam search in scheduling. International Journal of Production Research, 26, 297-307.
52.Pang, W., Wang, K.P., Zhou, C.G.., Dong, L.J., Liu, M., Zhang, H.Y., & Wang, J.Y. (2004). Modified particle swarm optimization based on space transformation for solving traveling salesman problem. Proceedings of 2004 International Conference on Machine Learning and Cybernetics, 4, 2342-2346.
53.Pezzella, F., & Merelli, E. (2000). A tabu search method guided by shifting bottleneck for the job shop scheduling problem. European Journal of Operational Research, 120(2), 297-310.
54.Pirkul, H. (1987). A heuristic solution procedure for the multiconstraint zero-one knapsack problem. Naval Research Logistics, 34, 161–172.
55.Prins, C. (2000). Competitive genetic algorithms for the open-shop scheduling problem. Mathematical Methods of Operations Research, 52, 389-411.
56.Rastegar, R., Meybodi, M.R., & Badie, K. (2004). A new discrete binary particle swarm optimization based on learning automata. Proceedings of the IEEE International Conference on Machine Learning and Applications, 456–465.
57.Salman, A., Ahmad, I., & Al-Madani, S. (2002). Particle swarm optimization for task assignment problem. Microprocessors and Microsystems, 26(8), 363-371.
58.Sha, D.Y., & C.-Y. Hsu. (2006). “A modified parameterized active schedule generation algorithm for the job shop scheduling problem,” Proceedings of the 36th International Conference on Computers and Industrial Engineering (ICCIE 2006), pp. 702-712, Taiwan, ROC.
59.Shi Y, & Eberhart R.C. (1998a). Parameter selection in particle swarm optimization. Proceedings of the 7th International Conference on Evolutionary Programming, 591-600.
60.Shi Y, & Eberhart R.C. (1998b). A modified particle swarm optimizer. Proceedings of the 1998 IEEE International Conference on Evolutionary Computation, 69-73.
61.Stacey, A., Jancic, M., & Grundy, I. (2003). Particle swarm optimization with mutation. Proceedings of the 2003 IEEE Congress on Evolutionary Computation, 2, 1425-1430.
62.Sun, D., Batta, R., & Lin, L. (1995). Effective job shop scheduling through active chain manipulation. Computers & Operations Research, 22(2), 159-172.
63.Taillard, E.D. (1993), Benchmarks for basic scheduling problems, European Journal of Operational Research, 64, 278-285.
64.Tasgetiren, M.F., Liang, Y-C., Sevkli, M., & Gencyilmaz, G. (2007). A particle swarm optimization algorithm for makespan and total flowtime minimization in the permutation flowshop sequencing. European Journal of Operational Research, 177(3), 1930-1947.
65.Vasquez, M., & Hao, J.K. (2001). A hybrid approach for the 0-1 multidimensional knapsack problem. Proceedings of the 7th International Joint Conference on Artificial Intelligence, 1, 328–333.
66.Vasquez, M., & Vimont, Y. (2005). Improved results on the 0-1 multidimensional knapsack problem. European Journal of Operational Research, 165, 70–81.
67.Wang, K.P., Huang, L., Zhou, C.G., & Pang, W. (2003). Particle swarm optimization for traveling salesman problem. Proceedings of International Conference on Machine Learning and Cybernetics, 3, 1583-1585.
68.Wang, L., & Zheng, D. (2001). An effective hybrid optimization strategy for job-shop scheduling problems. Computers & Operations Research, 28, 585-596.
69.Wu, B., Zhao, Y., Ma Y., Dong, H., & Wang, W. (2004). Particle Swarm Optimization method for Vehicle Routing Problem. Proceedings of Fifth World Congress on Intelligent Control and Automation (WCICA 2004), 3, 2219 – 2221.
70.Xia, W., & Wu, Z. (2005). An effective hybrid optimization approach for multi-objective flexible job-shop scheduling problems. Computers & Industrial Engineering, 48(2), 409-425.
71.Yin, P.Y., Yu, S.S., Wang, P.P., & Wang, Y.T. (2007a). Multi-objective task allocation in distributed computing systems by hybrid particle swarm optimization. Applied Mathematics and Computation, 184(2), 407-420.
72.Yin, P.Y., Yu, S.S., Wang, P.P, & Wang, Y.T. (2007b). Task allocation for maximizing reliability of a distributed system using hybrid particle swarm optimization. The Journal of Systems & Software, 80(5), 724-735.
73.Zhang, H., Li, X., Li, H., & Huang, F. (2005). Particle swarm optimization-based schemes for resource-constrained project scheduling. Automation in Construction, 14, 393-404.
74.Zhang, H., Li, H., & Tam, C.M. (2006). Particle swarm optimization for resource-constrained project scheduling. International Journal of Project Management, 24(1), 83-92.
75.Zhi, X.H., Xing, X.L., Wang, Q.X., Zhang, L.H., Yang, X.W., Zhou, C.G., & Liang, Y.C. (2004). A discrete PSO method for generalized TSP problem. Proceedings of 2004 International Conference on Machine Learning and Cybernetics, 4, 2378-2383.