MULTI OBJECTIVE FLEXIBLE JOB SHOP SCHEDULING PROBLEMS

Year 2013, Volume: 31 Issue: 4, 605 - 623, 01.12.2013

Serkan Kaya , Nilgün Fığlalı

Abstract

Flexible job shop scheduling problem, is an extension of the classical job shop scheduling problem. In Flexible job shop scheduling problem, there are more than one machine with the same features for the same purpose. The problem can be defined as appointing the jobs to the machines (assignment) and ordering the jobs at each machine (sequencing) to serve the desired purpose. Multi-objective flexible job shop scheduling problem is of great importance in production management and combinatorial optimization. Because of the calculation complexity, finding the optimal solution for the actual situation of medium-sized problems is very difficult with traditional optimization methods. In this study, recent works on multi-objective flexible job shop scheduling problems is examined and a comprehensive literature review is presented. Especially, the meta-heuristic methods used by researchers are rigorously investigated; and meta-heuristic methods for solving multi-objective flexible job shop scheduling problems are suggested.

Keywords

Flexible job shop scheduling, multi objective scheduling, scheduling

References

• [1] Pinedo, M.L., “Scheduling Theory, Algorithms, and Systems”, ISBN: 978-0-387-78934-7 e-ISBN: 978-0-387-78935-4, DOI: 10.1007/978-0-387-78935-4, 2008.
• [2] Fattahi, P., Mehrabad, M.S., Jolai F., “Mathematical modeling and heuristic approaches to flexible job shop scheduling problems”, J Intell Manuf, 18:331–342, DOI 10.1007/s10845-007-0026-8, 2007.
• [3] Ho, N.B., Tay, J.C., “Solving Multiple-Objective Flexible Job Shop Problems by Evolution and Local Search”, IEEE Transactions On Systems, Man, And Cybernetics—Part C: Applications And Reviews, Vol. 38, No. 5, 1094-6977, 2008.
• [4] Kacem, I., Hammadi, S., Borne, P., “Approach by Localization and Multiobjective Evolutionary Optimization for Flexible Job-Shop Scheduling Problems”, IEEE transactions on Systems,Man, and Cybernetics—Part c: Applications and Reviews, Vol. 32, No. 1, 2002.
• [5] Kacem, I., Hammadi, S., Borne, P., “Pareto-optimality approach for flexible job-shop scheduling problems: hybridization of evolutionary algorithms and fuzzy logic”, Mathematics and Computers in Simulation 60, 245–276, 2002.
• [6] Pezzella, F., Morganti, G., Ciaschetti, G., “A genetic algorithm for the Job-Shop Scheduling Problem”, Computers & Operations Research 35, 3202 – 3212, 2008.
• [7] Chiang, T.C., Lin, H.J., “A simple and effective evolutionary algorithm for multiobjective flexible job shop scheduling”, International Journal of Production Economics, http://dx.doi.org/10.1016/j.ijpe.2012.03.034, (2012).
• [8] Li, J., Pan, Q., Xie, S., “An effective shuffled frog-leaping algorithm for multi-objective flexible job shop scheduling problems”, Applied Mathematics and Computation, 218, 9353-9371, (2012).
• [9] Li, J., Pan, Q., “Chemical-reaction optimization for flexible job-shop scheduling problems with maintenance activity”, Applied Soft Computing 12, 2896–2912, http://dx.doi.org/10.1016/j.asoc.2012.04.012, (2012).
• [10] Wang, L., Zhou, G., Xu, Y., Liu, M., “An enhanced Pareto-based artificial bee colony algorithm for the multi-objective flexible job-shop scheduling”, International Journal Advanced Manufacturing Technology, 60:1111–1123, DOI 10.1007/s00170-011-3665-z, (2012).
• [11] Davarzani, Z., Akbarzadeh, M., Khairdoost, N., “Multiobjective Artificial Immune Algorithm for Flexible Job Shop Scheduling Problem”, International Journal of Hybrid Information Technology, Vol. 5, No. 3, July, (2012).
• [12] Xiong, J., Tan, X., Yang, K., Xing, L., Chen Y., “A Hybrid Multiobjective Evolutionary Approach for Flexible Job-Shop Scheduling Problems”, Hindawi Publishing Corporation, Mathematical Problems in Engineering, Volume 2012, Article ID 478981, 27 pages, doi:10.1155/2012/478981, (2012).
• [13] Moslehi, G., Mahnam, M., “A Pareto approach to multi-objective flexible job-shop scheduling problem using particle swarm optimization and local search”, Int. J. Production Economics 129, 14–22, 2011.
• [14] Li, J.Q., Pan, Q.K., Gao, K.Z., “Pareto-based discrete artificial bee colony algorithm for multi-objective flexible job shop scheduling problems”, Int J Adv Manuf Technol, DOI 10.1007/s00170-010-3140-2, 2011.
• [15] Wang, X., Gao, L., Zhang, C., Shao, X., “A multi-objective genetic algorithm based on immune and entropy principle for flexible job-shop scheduling problem”, Int J Adv Manuf Technol, 51:757–767, DOI 10.1007/s00170-010-2642-2, 2010.
• [16] Bagheri, A., Zandieh, M., Mahdavi, I., Yazdani, M., “An artificial immune algorithm for the flexible job-shop scheduling problem”, Future Generation Computer Systems 26, 533-541, (2010).
• [17] Unachak, P., “An Adaptive Representation For A Genetic Algorithm In Solving Flexible Job-Shop Scheduling And Rescheduling Problems”, Ph.D. Thesis, Michigan State University, UMI Number: 3435155, 2010.
• [18] Li, J., Pan, Q., Liang, Y.C., “An effective hybrid tabu search algorithm for multi-objective flexible job-shop scheduling problems”, Computers & Industrial Engineering 59, 647–662, 2010.
• [19] Rajkumar, M., Asokan, P., Vamsikrishna, V., “A GRASP algorithm for flexible job-shop scheduling with maintenance constraints”, International Journal of Production Research, 48: 22, 6821-6836, 2010.
• [20] Wang, S., Yu, J., “An effective heuristic for flexible job-shop scheduling problem with maintenance activities”, Computers & Industrial Engineering 59, 436–447, 2010.
• [21] Zhang, G., Shao, X., Li, P., Gao, L., “An effective hybrid particle swarm optimization algorithm for multi-objective flexible job-shop scheduling problem”, Computers & Industrial Engineering 56, 1309–1318, 2009.
• [22] Xing, L.N., Chen, Y.W., Yang, K.W., “Multi-objective flexible job shop Schedule: Design and evaluation by simulation modeling”, Applied Soft Computing, 9, 362–376, 2009.
• [23] Xing, L.N., Chen, Y.W., Yang, K.W., “An efficient search method for multi-objective flexible job shop scheduling problems”, J Intell Manuf 20, 283–293, 2009.
• [24] Xing, L.N., Chen, Y.W., Yang, K.W., “Double Layer ACO Algorithm for the Multi-Objective FJSSP”, New Generation Computing, Ohmsha, Ltd. and Springer, 26, 313-327, 2008.
• [25] Gao, J., Sun, L., Gen, M., “A hybrid genetic and variable neighborhood descent algorithm for flexible job shop scheduling problems”, Computers & Operations Research 35, 2892 – 2907, 2008.
• [26] Shi-Jin, W., Bing-Hai, Z., Li-Feng, X., “A filtered-beam-search-based heuristic algorithm for flexible job-shop scheduling problem”, International Journal of Production Research, 46: 11, 3027- 3058, 2008.
• [27] Jia, Z., Chen, H., Tang, J., “An Improved Particle Swarm Optimization for Multi-objective Flexible Job-shop Scheduling Problem”, IEEE International Conference on Grey Systems and Intelligent Services, 1-4244-1294-3, 2007.
• [28] Gao, J., Gen, M., Sun, L., Zhao, X., “A hybrid of genetic algorithm and bottleneck shifting for multiobjective flexible job shop scheduling problems”, Computers & Industrial Engineering 53, 149–162, 2007.
• [29] Xia, W., Wu, Z., “An effective hybrid optimization approach for multi-objective flexible job-shop scheduling problems”, Computers & Industrial Engineering 48, 409–425, 2005.
• [30] Zhang, H., & Gen, M. “Multistage-based genetic algorithm for flexible job-shop scheduling problem” Journal of Complexity International, 11, 223–232, 2005.
• [31] Vilcot, G., Billaut, J.C., “A tabu search and a genetic algorithm for solving a bicriteria general job shop scheduling problem”, European Journal of Operational Research 190, 398– 411, 2008.
• [32] Tamaki, H., Ono, T., Murao, H., Kitamura, S. “Modeling and genetic solution of a class of flexible job shop scheduling problems” IEEE International Conference, 0-7803- 7241-7/01, 2001.
• [33] Baykasoglu, A., Özbakır, L., Sönmez, A.İ., “Using multiple objective tabu search and grammars to model and solve multi-objective flexible job shop scheduling problems”, Journal of Intelligent Manufacturing, 15,777-785, 2004.
• [34] Fattahi, P., “A Hybrid Multi Objective Algorithm For Flexible Job Shop Scheduling”, Proceedings Of World Academy Of Science, Engineering And Technology Volume 38, Issn: 2070-3740, 2009.
• [35] Gholami, M., Zandieh, M., “Integrating simulation and genetic algorithm to schedule a dynamic flexible job shop”, Journal of Intelligent Manufacturing, 20:481–498, DOI 10.1007/s10845-008-0150-0, 2009.
• [36] Grobler, J., Engelbrecht, A.P., Kok, S., Yadavalli, S., “Metaheuristics for the multi-objective FJSP with sequence-dependent set-up times, auxiliary resources and machine down time”, Ann Oper Res, 180: 165–196, DOI 10.1007/s10479-008-0501-4, 2010.
• [37] Jian-jun, Y., Xu-jun, X., Fei, Y., “Study on Multi-objective Flexible Production Scheduling Based on Improved Immune Algorithm”, IEEE, 15th International Conference on Management Science & Engineering, September 10-12, 1-4244-2388-0/08, USA, 2008.
• [38] Lin, L., Jia-Zhen, H., “Multi-Objective Flexible Job-Shop Scheduling Problem in Steel Tubes Production”, Systems Engineering — Theory & Practice, Volume 29, Issue 8, 2009.
• [39] Liu, H., Abraham, A., Wang, Z., “A Multi-swarm Approach to Multi-objective Flexible Job-shop Scheduling Problems”, Fundamenta Informaticae, 95, 465–489, 2009.
• [40] Liu, H., Abraham, A., Grosan, C., “A Novel Variable Neighborhood Particle Swarm Optimization for Multi-objective Flexible Job-shop Scheduling Problems”, IEEE., 1-4244- 1476-8, 2007.
• [41] Frutos, M., Olivera, A.C., Tohme, F., “A memetic algorithm based on a NSGAII scheme for the flexible job-shop scheduling problem”, Ann Oper Res, 181: 745–765 DOI 10.1007/s10479-010-0751-9, 2010.
• [42] Rabiee, M., Zandieh, M., Ramezani, P., “Bi-objective partial flexible job shop scheduling problem: NSGA-II, NRGA, MOGA and PAES approaches”, International Journal of Production Research, 50:24, 7327-7342, DOI:10.1080/00207543.2011.648280, 2012.
• [43] Wu, Z., “Multi-Agent Workload Control and Flexible Job Shop Scheduling”, Ph. D. Thesis, Department of Industrial and Management Systems Engineering College of Engineering, University of South Florida, UMI Number: 3188440, 2005.
• [44] Prakash, A., Chan, F.T.S., Deshmukh, S.G., “FMS Scheduling with knowledge based genetic algorithm approach”, Expert Systems with Applications, 38, 3161–3171, 2011.
• [45] Tanev, I.T., Uozumi, T., Morotome, Y., “Hybrid evolutionary algorithm-based real-world flexible job shop scheduling problem: application service provider approach”, Applied Soft Computing 5, 87–100, 2004.
• [46] Chan, F. T. S., Wong, T. C., Chan, L. Y., “Flexible job-shop scheduling problem under resource constraints”, International Journal of Production Research, 44: 11, 2071—2089, 2006.
• [47] Rahımı-Vahed, A.R., Mırghorbanı S.M., Rabbanı, M., “A hybrid multi-objective particle swarm algorithm for a mixed-model assembly line sequencing problem”, Engineering Optimization, Vol. 39, No. 8, 877–898, 2007.
• [48] Brandimarte, P., “Routing and Scheduling in a Flexible Job-Shop by Tabu Search”, Annals of Operations Research, vol. 2, pp. 158-183, 1993.
• [49] Hurink, E., Jurisch, B., Thole, M., “Tabu search for the job shop scheduling problem with multi-purpose machine”, Operations Research Spektrum 15, 205_215, 1994.
• [50] Dauzere-Peres S, Paulli J., ‘An integrated approach for modeling and solving the general multiprocessor job-shop scheduling problem using tabu search’. Annals of Operation Research, 70(3):281–306, 1997.