臺灣博碩士論文加值系統

The job-shop scheduling problem is one of the most NP-Hard problems and has attracted many researchers to develop new algorithm based on heuristic or meta-heuristic approach. Many algorithms based on Genetic Algorithm, Particle Swarm Optimization, Ant Colony Optimization have been proposed to solve it, respectively but the results are still not yet satisfactory. In this paper we proposed a new algorithm based on bees algorithm which is very good for discrete optimization problem; furthermore, the results are optimized with the famous tabu search for local search to improve the results. The robustness, efficiency, and effectiveness of this algorithm are examined using a set of benchmark instances and compared with existing algorithms. The results show that the proposed algorithm could obtain competitive results within reasonable computing times.

The job-shop scheduling problem is one of the most NP-Hard problems and has attracted many researchers to develop new algorithm based on heuristic or meta-heuristic approach. Many algorithms based on Genetic Algorithm, Particle Swarm Optimization, Ant Colony Optimization have been proposed to solve it, respectively but the results are still not yet satisfactory. In this paper we proposed a new algorithm based on bees algorithm which is very good for discrete optimization problem; furthermore, the results are optimized with the famous tabu search for local search to improve the results. The robustness, efficiency, and effectiveness of this algorithm are examined using a set of benchmark instances and compared with existing algorithms. The results show that the proposed algorithm could obtain competitive results within reasonable computing times.

ABSTRACT i
ACKNOWLEDGMENTS ii
CONTENTS iii
LIST OF ALGORITHMS iv
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. Job shop scheduling problem 4
2.2. Bees algorithm 7
2.2.1. The idea of bees algorithm 7
2.2.2 Bees algorithm 8
Chapter 3. PROPOSED ALGORITHMS 10
3.1. Representation of bees 10
3.2. Neighborhood structure 11
3.3. Critical path based crossover 12
3.4. Local search 16
3.5. The HBTS algorithm 16
Chapter 4. EXPERIMENTAL RESULTS 23
4.1. Computational results 23
4.2. User interface 26
Chapter 5. CONCLUSIONS 27
5.1. Conclusions 27
5.2. Future studies 27
REFERENCES 28

[1]Ge, H. W., Sun, L., Liang, Y. C., & Qian, F. (2008). An effective PSO and AIS-based hybrid intelligent algorithm for job-shop scheduling. IEEE Transactions on Systems, Man and Cybernetics, Part A, 38, 358–368.
[2]Lian, Z., Gu, X., & Jiao, B. (2006). A dual similar particle swarm optimization algorithm for job-shop scheduling with penalty. In Proceedings of the sixth world congress on intelligent control and automation (Vol. 2, pp. 7312–7316).
[3]Ge, H., Du, W., & Qian, F. (2007). A hybrid algorithm based on particle swarm optimization and simulated annealing for job shop scheduling. In Proceedings of the third international conference on natural computation (Vol. 3, pp. 715–719).
[4]Tsung-Lieh Lin, Shi-Jinn Horng, Tzong-Wann Kao, Yuan-Hsin Chen, Ray-Shine Run, Rong-Jian Chen, Jui-Lin Lai, I-Hong Kuo, An efficient job-shop scheduling algorithm based on particle swarm optimization, Expert Systems with Applications, Volume 37, Issue 3, 15 March 2010, Pages 2629-2636
[5]Nowicki E, Smutnicki C. A fast tabu search algorithm for the job shop problem. Management Science 1996;42:797–813.
[6]Nowicki, E., & Smutnicki, C. (2005). An advanced tabu search algorithm for the job shop problem. Journal of Scheduling, 8, 145–159.
[7]Ponnambalam, S. G., Aravindan, P., & Rajesh, S. V. (2000). A tabu search algorithm for job shop scheduling. The International Journal of Advanced Manufacturing Technology, 16, 765–771.
[8]Goncalves, J. F., Mendes, J. J. D. M., & Resende, M. G. C. (2005). A hybrid genetic algorithm for the job shop scheduling problem. European Journal of Operational Research, 167, 77–95.
[9]Watanabe, M., Ida, K., & Gen, M. (2005). A genetic algorithm with modified crossover operator and search area adaptation for the job-shop scheduling problem. Computers and Industrial Engineering, 48, 743–752.
[10]Park, B. J., Choi, H. R., & Kim, H. S. (2003). A hybrid genetic algorithm for the job shop scheduling problems. Computers and Industrial Engineering, 45, 597–613.
[11]Wang, L., & Zheng, D. Z. (2001). An effective hybrid optimization strategy for jobshop scheduling problems. Computers and Operations Research, 28, 585–596.
[12]Van Laarhoven, P. J. M., Aarts, E. H. L., & Lenstra, J. K. (1992). Job shop scheduling by simulated annealing. Operaons Research, 40(1), 113–125.
[13]Suresh, R. K., & Mohanasundaram, K. M. (2005). Pareto archived simulated annealing for job shop scheduling with multiple objectives. The International Journal of Advanced Manufacturing Technology, 29, 184–196.
[14]Udomsakdigool, A., & Kachitvichyanukul, V. (2008). Multiple colony ant algorithm for job-shop scheduling problem. International Journal of Production Research, 46, 4155–4175.
[15]Zhou, P., Li, X. P., & Zhang, H. F. (2004). An ant colony algorithm for job shop scheduling problem. In Proceedings of the fifth world congress on intelligent control and automation (Vol. 4, pp. 2899–2903).
[16]Pinedo, M. (2008). Scheduling: Theory, Algorithm, and System. Third Ed., Englewood Cliffs, NJ: Prentice-Hall.
[17]Xin-She Yang, (2008). Nature-Inspired Metaheuristic Algorithms. First Ed., Frome, UK: Luniver Press.
[18]D. T. Pham, Ghanbarzadeh A., Koc E., Otri S., Rahim S., and M.Zaidi "The Bees Algorithm - A Novel Tool for Complex Optimisation Problems"", Proceedings of IPROMS 2006 Conference, pp.454-461
[19]Kuo, I. H., Horng, S. J., Kao, T. W., Lin, T. L., Lee, C. L., Terano, T., et al. (2009). An efficient flow-shop scheduling algorithm based on a hybrid particle swarm optimization model. Expert Systems with Applications, 36, 7027–7032.
[20]Liao, C. J., Tseng, C. T., & Luarn, P. (2007). A discrete version of particle swarm optimization for flowshop scheduling problems. Computers and Operations Research, 34, 3099–3111.
[21]Van Laarhoven, P.J.M., E.H.L. Aarts, and J.K. Lenstra. (1988). “Job Shop Scheduling by Simulated Annealing.” Report OS-R8809, Centrum voor Wiskunde en Informatica, Amsterdam.
[22]Van Laarhooven, P.J.M., E.H.L. Aarts, and J.K. Lenstra. (1992). “Job Shop Scheduling by Simulated Annealing.” Operations Research 40(1), 113–125.
[23]Jain, A. S., Rangaswamy, B., and Meeran, S. 2000. New and “Stronger” Job-Shop Neighbourhoods: A Focus on the Method of Nowicki and Smutnicki (1996). Journal of Heuristics 6, 4 (Sep. 2000), 457-480.
[24]Glover F. Tabu search (Part I). ORSA Journal on Computing 1989; 1:190–206.
[25]Glover F. Tabu search (Part II). ORSA Journal on Computing 1990; 2:4–32.
[26]Lawrence S. Resource constrained project scheduling: an experimental investigation of heuristic scheduling techniques (Supplement). Pittsburgh, PA: Graduate School of Industrial Administration, Carnegie Mellon University; 1984.
[27]A Eswaramurthy V. P., A Tamilarasi A. (2009). Hybridization of Ant Colony Optimization Strategies in Tabu Search for Solving Job Shop Scheduling Problems. International Journal of Information and Management Sciences 20 (2009), 173-189
[28]C. Zhang, Y. Rao, P. Li. (2008). An effective hybrid genetic algorithm for the job shop scheduling problem. The International Journal of Advanced Manufacturing Technology, 9, 965-974.
[29]V. P. Eswaramurthy, A. Tamilarasi. (2009) Hybridizing tabu search with ant colony optimization for solving job shop scheduling problems. The International Journal of Advanced Manufacturing Technology, 9, 1004-1015.
[30]Fisher H, Thompson GL. Probabilistic learning combinations of local job-shop scheduling rules. In: Muth JM, Thompson GL, editors. Industrial scheduling. Englewood Cliffs, NJ, Chichester, UK: Prentice-Hill; 1963.
[31]Lawrence S. Resource constrained project scheduling: an experimental investigation of heuristic scheduling techniques (Supplement). Pittsburgh, PA: Graduate School of Industrial Administration, Carnegie Mellon University; 1984.
[32]Adams, J., Balas, E. and Zawack., D. (1988). The shifting bottleneck procedure for job shop scheduling, Management Science, Vol. 34, pp. 391-401.
[33]Applegate D, Cook W. A computational study of the job-shop scheduling problem. ORSA Journal on Computing 1991;3:149–56.
[34]T. Yamada, R. Nakano, A genetic algorithm applicable to large-scale job shop problems, in: R. Manner, B. Manderick (Eds.), Parallel Problem Solving from Nature 2, North-Holland, Amsterdam, 1992, 281–290
[35]Hajri S, Liouane N, Hammadi S, Borne P., A controlled genetic algorithm by fuzzy logic and belief functions for job-shop scheduling, IEEE Trans Syst Man Cybern B Cybern. 2000;30(5):812-8.