An Improved Tabu Search Algorithm for Job Shop Scheduling Problem Trough Hybrid Solution Representations

Document Type : Research Paper

Authors

1 Alzahra University

2 Bu-Ali Sina University

Abstract

Job shop scheduling problem (JSP) is an attractive field for researchers and production managers since it is a famous problem in many industries and a complex problem for researchers. Due to NP-hardness property of this problem, many meta-heuristics are developed to solve it. Solution representation (solution seed) is an important element for any meta-heuristic algorithm. Therefore, many researchers try to present different encodings to solve this problem. Fattahi et al., and Gen & Cheng suggested two solutions for this problem that both have advantages and weaknesses in searching solution space to reach an acceptable solution. In the current paper, a cyclic algorithm based on tabu search algorithm was proposed to improve the exploration and exploitation powers of these encodings. Also, several problems of different sizes are solved by it and the obtained results were compared. Results showed the applicability and effectiveness of the proposed solution representation in comparison with the existing ones

Keywords

References

Asadzadeh, L. (2015). A local search genetic algorithm for the job shop scheduling problem with intelligent agents.Computers & Industrial Engineering, 85, 376–383.
Bagheri, A., et al. (2010). "An artificial immune algorithm for the flexible job-shop scheduling problem." Future Generation Computer Systems, 26.4, 533-541.
BlaË™zewicz J., Domschke W. & Pesch E. (1996). The job shop scheduling problem: conventional and new solution techniques. European Journal of Operational Research, 93(1):1–33.
Brandimarte P. (1993). Routing and scheduling in a flexible job shop by tabu search. Ann Oper Res, 41:157–183.
Bülbül, K. (2011). A Hybrid Shifting Bottleneck-Tabu Search Heuristic For The Job Shop Total Weighted Tardiness Problem. Computers & Operations Research, 38, 967-983.
Chang, P., Lin, K., Pai, P., Zhong, C., Lin, C., & Hung, L. (2008). Ant Colony Optimization System For A Multi-Quantitative And Qualitative Objective Job-Shop Parallel-Machine-Scheduling Problem.International Journal of Production Research, 46(20), 5719-5759.
Cheng, R., Gen, M., & Tsujimura, Y. (1996). A Tutorial Survey of Job-Shop Scheduling Problems Using Genetic Algorithms-I Representation”, Computers & Industrial Engineering, 30, 983-997.
Dauzere-Peres S  Paulli J. (1997). An integrated approach for modeling and solving the general multiprocessor job shop scheduling problem using tabu search, Ann. Operat. Res, 70, 281–306.
De Giovanni, L., & Ferdinando P. (2010). "An improved genetic algorithm for the distributed and flexible job-shop scheduling problem." European journal of operational research, 200.2, 395-408.
Elmi, A., Solimanpur, M., Topaloglu, S., & Elmi, A. (2011). "A Simulated Annealing Algorithm For The Job Shop Cell Scheduling Problem With Intercellular Moves And Re-entrant Parts", Computers & Industrial Engineering, 61, 171-178.
Fattahi P, Saidi M &  Jolai F. (2007). Mathematical modeling and heuristic approaches to flexible job shop scheduling problems. J Intell Manuf, 18:331–342
Fattahi, P., Jolai, F., & Arkat, J. (2009). Flexible Job Shop Scheduling With Overlapping In Operations. Applied Mathematical Modeling, 33, 3076-3087.
Fattahi, P., ShiraziManesh, M. &  &Roshani, A. (2012). A New Solution Seed For Job Shop Scheduling Problem. Applied Mechanics And Materials, 110-116, 3899-3905.
Gao, L., Li, X., Wen, X., Lu, C., & Wen, F. (2015). A hybrid algorithm based on a new neighbourhood structure evaluation method for job shop scheduling problem.Computers & Industrial Engineering, 88, 417–429.
Garey, M., Johnson, D., & Sethi, R. (1976). The Complexity Of Flow shop And Job Shop Scheduling. Mathematical Methods of Operations Research, 1, 117-129.
Gen, M., & Cheng, R. (1997). Genetic Algorithm and Engineering Design. John Wiley, New York.
Glover, F., & Laguna, M. (1997). Tabu Search. Kluwer Academic Publishers, Boston, Mass, USA.
Glover, F., & Mcmillan, C. (1986).The General Employee Scheduling Problem: An Integration of MS And AI. Computers And Operations Research, 13, 563–573.
Glover, F. (1989). Tabu Search - Part 1. ORSA Journal On Computing, 1 (2), 190–206.
Hurink E, Jurisch B, Thole M. (1994).  Tabu search for the job shop scheduling problem with multi-purpose machines, Operat. Res. Spekt, 15, 205–215.
Jamili, A., (2016), “Robust job shop scheduling problem: Mathematical models, exact and heuristic algorithms”, Expert Systems with Applications 55, 341-350.
Jain, A. S., & Meeran, S. (1999). A State-Of-The-Art Review Of Job-Shop Scheduling Techniques. European Journal Of Operations Research, 113, 390-434.
Ku, W. Y., Beck, J. C., (2016), “Mixed Integer Programming models for job shop scheduling: A computational analysis”, Computers & Operations Research, 73, 165-173.
Kuhpfahl, J. & Bierwirth, C. (2016). A study on local search neighbourhoods for the job shop scheduling problem with total weighted tardiness objective.Computers & Operations Research, 66, 44-57.
Kurdi, M. (2015). A new hybrid island model genetic algorithm for job shop scheduling problem.Computers & Industrial Engineering, 88, 273-283.
Liu, J., Zhong, W., & Jiao, L. (2006).A Multiagent Evolutionary Algorithm For Constraint Satisfaction Problems. IEEE Transactions On Systems, Man, And Cybernetics-Part B: Cybernetics, 36, 54-73.
Mastrololli M &  Gambardella L.M. (2002). Effective neighbourhood functions for the flexible job shop problem, J. Schedul. 3 (1) 3–20.
Mellor, P. (1966). A Review of Job Shop Scheduling. Operational Research Society, 17, 161-171.
Moslehi, Ghasem, & Mehdi Mahnam. (2011). "A Pareto approach to multi-objective flexible job-shop scheduling problem using particle swarm optimization and local search." International Journal of Production Economics, 129.1: 14-22.
Rabiee, M.,Zandieh, M., & Ramezani. P. (2012). Bi-Objective Partial Flexible Job Shop Scheduling Problem: NSGA-II, NRGA, MOGA And PAES Approaches. International Journal of Production Research, 50(24), 7327-7342.
Rossi, Andrea, & Elena Boschi. (2009). "A hybrid heuristic to solve the parallel machines job-shop scheduling problem." Advances in Engineering Software, 40.2: 118-127.
Saidi-mehrabad M &  Fattahi P (2007). Flexible job shop scheduling with tabu search algorithms. Int J Adv Manuf Technol, 32:563–570
Wang, Lei, & Dun-bing Tang. (2011). "An improved adaptive genetic algorithm based on hormone modulation mechanism for job-shop scheduling problem." Expert Systems with Applications, 38.6: 7243-7250.
Zhao, F., Zhang, J., Zhang, C., & Wang, J. (2015). An improved shuffled complex evolution algorithm with sequence mapping mechanism for job shop scheduling problems. Expert Systems with Applications, 42 (8), 3953–3966.
Journal of Quality Engineering and Production Optimization
Volume 3, Issue 1
January 2018
Pages 13-26

Files

Share

How to cite

Statistics