A hybrid genetic tabu search algorithm for solving job shop scheduling problems: a case study

详细信息    查看全文

• 作者：S. Meeran (1) s.meeran@bath.ac.uk
  M. S. Morshed (2) m.s.morshed@bath.ac.uk
• 关键词：Genetic algorithms &#8211 ; Tabu search &#8211 ; Job shop &#8211 ; Scheduling &#8211 ; Hybrid systems
• 刊名：Journal of Intelligent Manufacturing
• 出版年：2012
• 出版时间：August 2012
• 年：2012
• 卷：23
• 期：4
• 页码：1063-1078
• 全文大小：1.2 MB
• 参考文献：1. Adams J., Balas E., Zawack D. (1988) The shifting bottleneck procedure for job-shop scheduling. Management Science 34(3): 391–401
  2. Aydin M. E., Fogarty T. C. (2004) A simulated annealing algorithm for multi-agent systems: A job-shop scheduling application. Journal of Intelligent Manufacturing 15(6): 805–814
  3. Barnes J. W., Chambers J. B. (1995) Solving the job shop scheduling problem using tabu search. IIE Transactions 27: 257–263
  4. Blazewicz, J., et al. (1996). Job shop scheduling, scheduling computer and manufacturing processes (pp. 16–20 and 265–317). Germany: Springer.
  5. Chen L., Bostel N., Dejax P., Cai J., xi L. (2007) A tabu search algorithm for the integrated scheduling problem of container handling systems in a maritime terminal. European Journal of Operational Research 181(1): 40–58
  6. Chen C. L., Chen C. L. (2009) Bottleneck-based heuristics to minimize total tardiness for the flexible flow line with unrelated parallel machines. Computers and Industrial Engineering 56(4): 1393–1401
  7. Cheng R., Gen M., Tsujimura Y. (1996) A tutorial survey of job-shop scheduling problems using genetic algorithms-I. Representation, Computers & Industrial Engineering 30(4): 983–997
  8. Chiang T.C., Fu L.C. (2007) Using dispatching rules for job shop scheduling with due-date based objectives. International Journal of Production Research 45(14): 3245–3262
  9. Chiu H. P., Hsieh, K. L., Tang, Y. T., & Wang C. Y. (2007). A tabu genetic algorithm with search adaptation for the job shop scheduling problem. In Proceedings of the 6th WSEAS international conference on artificial intelligence, knowledge engineering, data bases, Greece, February 16–19.
  10. Davis, L. (1985). Job-shop scheduling with genetic algorithm. In Proceedings of the 1st international conference on genetic algorithms and their applications, Pittsburgh, PA (pp. 136–140).
  11. Dell’Amico M., Trubian M. (1993) Applying tabu search to the job-shop scheduling problem. Annals of Operations Research 41: 231–252
  12. Della Croce F., Tadei R., Volta G. (1995) A genetic algorithm for the job shop problem. Computers and Operations Research 22(1): 15–24
  13. Demirkol E., Mehta S., Uzsoy R. (1997) A computational study of shifting bottleneck procedures for shop scheduling problems. Journal of Heuristics 3(2): 111–137
  14. Dorndorf U., Pesch E. (1995) Evolution based learning in a job-shop scheduling environment. Computers and Operations Research 22(1): 25–40
  15. Eswarmurthy V., Tmilarasi A. (2009) Hybridizing tabu search with ant colony optimization for solving job shop scheduling problem. The international Journal of Advanced Manufacturing Technology 40: 1004–1015
  16. Fattahi P., Mehrabad M.S., Jolai F. (2007) Mathematical modeling and heuristic approaches to flexible job shop scheduling problems. Journal of Intelligent Manufacturing 18(3): 331–342
  17. Gao J., Gen M., Sun L. (2006) Scheduling jobs and maintenances in flexible job shop with a hybrid genetic algorithm. Journal of Intelligent Manufacturing 17(4): 493–507
  18. Gen M., Gao J., Lin L. (2009) Multistage-based genetic algorithm for flexible job-shop scheduling problem. Intelligent and Evolutionary Systems, Studies in Computational Intelligence 187: 183–196
  19. Gen, M., Tsujimura, Y., & Kubota, E. (1994). Solving job-shop scheduling problems by genetic algorithm. In Proceeding of 1994 IEEE international conference on systems, man, and cybernetics (Vol. 2, pp. 1577–1582).
  20. Gholami M., Zandieh M. (2009) Integrating simulation and genetic algorithm to schedule a dynamic flexible job shop. Journal of Intelligent Manufacturing 20(4): 481–498
  21. Glover F. (1989) Tabu search—Part I. ORSA Journal on Computing 1: 190–206
  22. Goncalves J. F., Mendes J. D., Resende M. G. C. (2005) A hybrid genetic algorithm for the job shop scheduling problem. European Journal of Operational Research 167: 77–95
  23. Gonz谩lez, M. A., Vela, C. R., & Varela, R. (2009). Genetic algorithm combined with tabu search for the job shop scheduling problem with setup times’ methods and models in artificial and natural computation. A homage to professor Mira’s scientific legacy. Lecture Notes in Computer Science, 5601/2009, 265–274. doi:10.1007/978-3-642-02264-7_28.
  24. Jain A. S., Meeran S. (1998a) Job-Shop Scheduling using neural networks. Internation Journal of Production Research 36(5): 1249–1272
  25. Jain, A. S., & Meeran, S. (1998b). A state-of-the-art review of job-shop scheduling techniques. Technical Report, University of Dundee, UK.
  26. Jain A. S., Meeran S. (2002) A multi-level hybrid framework applied to the general flow-shop scheduling problem. Computers and Operations Research 29: 1873–1901
  27. Jones A., Rabelo L.C. (1998) Survey of job shop scheduling techniques. National Institute of Standards and Technology (NISTIR), Gaithersburg, MD
  28. Mascis A., Pacciarelli D. (2002) Job shop scheduling with blockings and no-wait constraints. European Journal of Operational Research 143: 498–517
  29. Mattfeld D. C. (1996) Evolutionary search and the job shop: Investigations on genetic algorithms for production scheduling. Physica-Verlag, Heidelberg, Germany
  30. Meeran, S. & Morshed, M. S. (2007, December). A hybrid configuration for solving job shop scheduling problems. In 8th Asia Pacific industrial engineering and mangement science Conference, Kaohsiung, Taiwan.
  31. Morshed, M. S. (2006). A hybrid model for job shop scheduling. PhD Thesis, University of Birmingham, UK.
  32. Nowicki E., Smutnicki C. (1996) A fast taboo search algorithm for the job-shop problem. Management Science 42(6): 797–813
  33. Panwalkar S. S., Iskander W. (1977) A survey of scheduling rules. Operations Research 25(1): 45–61
  34. Park B. J., Choi H. R., Kim H. S. (2003) A hybrid genetic algorithm for the job shop scheduling problems. Computers & Industrial Engineering 45: 597–613
  35. P茅rez, E., Posada, M., & Herrera, F. (2010). Analysis of new niching genetic algorithms for finding multiple solutions in the job shop scheduling. Journal of Intelligent Manufacturing, Online Firsttrademark, March 10, 2010.
  36. Pezzella F., Merelli E. (2000) A tabu search method guided by shifting bottleneck for the job shop scheduling problem. European Journal of Operation Research 120: 297–310
  37. Pezzella F., Morganti G., Ciaschetti G. (2008) A genetic algorithm for the flexible job-shop scheduling problem. Computers and Operations Research 35: 3202–3212
  38. Pinedo M., Chao X. (1999) Operations scheduling with applications in manufacturing and services. McGraw Hill, Singapore
  39. Rossi A., Boschi E. (2009) A hybrid heuristic to solve the parallel machines job-shop scheduling problem. Advances in Engineering Software 40(2): 118–127
  40. Roy, B., & Sussmann, B. (1964). Les Problemes d’Ordonnancement avec Contraintes Disjonctives. Note D.S. no. 9 bis, SEMA, Paris, France, December 1964.
  41. Satake T., Morikawa K., Takahashi K., Nakamura N. (1999) Simulated annealing approach for minimizing the make-span of the general job shop. International Journal of Production Economics 60(61): 515–522
  42. 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
  43. Tamilselvan, R., & Balasubramanie, P. (2009). Integrating genetic algorithm, tabu search approach for job shop scheduling. International Journal of Computer Science and Information Security, 2(1).
  44. Tan, Y., Liu, S.,& Wang, D. (2010). A constraint programming-based branch and bound algorithm for job shop problems. In Control and decision conference (CCDC), 2010 China, May 26–28, 2010 (pp. 173–178).
  45. Tay J. C., Ho N. B. (2008) Evolving dispatching rules using genetic programming for solving multi-objective flexible job-shop problems. Computers & Industrial Engineering 54(3): 453–473
  46. Thomsen, S. (1997). Meta-heuristics combined with branch & bound. Technical Report. Copenhagen Business School, Copenhagen, Denmark.
  47. Wang L., Zheng D. Z. (2001) An effective hybrid optimisation strategy for job shop scheduling problems. Computers and Operations Research 28: 585–596
  48. Weckman G. R., Ganduri C. V., Koonce D. A. (2008) A neural network job-shop scheduler. Journal of Intelligent Manufacturing 19(2): 191–201
  49. Yamada, T. & Nakano, R. (1996). Scheduling by genetic local search with multi-step crossover. In PPSN’IV 4th international conference on parallel problem solving from nature, Berlin, Germany (pp. 960–969).
  50. Yu H., Liang W. (2001) Neural network and genetic algorithm-based hybrid approach to expanded job shop scheduling. Computers and Industrial Engineers 39: 337–356
  51. Zhang, G., Gao, L., & Shi, Y. (2010). A genetic algorithm and tabu search for multi objective flexible job shop scheduling problems (CCIE). In 2010 International conference on computing, control and industrial engineering, June 5–6 (pp. 251–254).
  52. Zhang H., Gen M. (2009) A parallel hybrid ant colony optimisation approach for job-shop scheduling problem. International Journal of Manufacturing Technology and Management 16(1–2): 22–41
  53. Zhang R., Wu C. (2008) A hybrid approach to large-scale job shop scheduling. Applied Intelligence 32(1): 47–59
  54. Zhou R., Nee A. Y. C., Lee H. P. (2009) Performance of an ant colony optimisation algorithm in dynamic job shop scheduling problems. International Journal of Production Research 47: 2903–2920
• 作者单位：1. School of Management, University of Bath, Bath, BA2 7AY UK2. Birmingham, UK
• ISSN：1572-8145

文摘

In recent decades many attempts have been made at the solution of Job Shop Scheduling Problem using a varied range of tools and techniques such as Branch and Bound at one end of the spectrum and Heuristics at the other end. However, the literature reviews suggest that none of these techniques are sufficient on their own to solve this stubborn NP-hard problem. Hence, it is postulated that a suitable solution method will have to exploit the key features of several strategies. We present here one such solution method incorporating Genetic Algorithm and Tabu Search. The rationale behind using such a hybrid method as in the case of other systems which use GA and TS is to combine the diversified global search and intensified local search capabilities of GA and TS respectively. The hybrid model proposed here surpasses most similar systems in solving many more traditional benchmark problems and real-life problems. This, the system achieves by the combined impact of several small but important features such as powerful chromosome representation, effective genetic operators, restricted neighbourhood strategies and efficient search strategies along with innovative initial solutions. These features combined with the hybrid strategy employed enabled the system to solve several benchmark problems optimally, which has been discussed elsewhere in Meeran and Morshed (8th Asia Pacific industrial engineering and management science conference, Kaohsiung, Taiwan, 2007). In this paper we bring out the system’s practical usage aspect and demonstrate that the system is equally capable of solving real life Job Shop problems.