Research study of state-of-the-art algorithms for flexible job-shop scheduling problem

Paweł Wojakowski


The paper discusses various approaches used to solve flexible job-shop scheduling problem concentrating on formulations proposed in the last ten years. It mainly refers to the applied metaheuristic techniques which have been exploited in this research area. A comparison of presented approaches is attempted, some concluding insights are highlighted. Finally future research directions are suggested.

Słowa kluczowe: flexible job-shop scheduling, multi-objective optimization, review

Lazar I., Review on solving the job-shop scheduling problem: recent development and trends, Transfer Inovacii, 23/2012, 55-60.

Hsu T., Dupas R., Jolly D., Goncalves G., Evaluation of mutation heuristics for the solving of multiobjective flexible job-shop by an evolutionary algorithm, 2002 IEEE International Conference on Systems, Man and Cybernetics, Vol. 5, 2002.

Das S.K., Nagendra P., Investigations into the impact of flexibility on manufacturing performance, International Journal of Production Research, Vol. 31, No. 10, 1993, 2337-2354.

Nomden G., v.d.Zee D.J., Virtual cellular manufacturing: Configuring routing flexibility, International Journal of Production Economics, Vol. 112, 2008, 439-451.

Pattanaik L.N., Jain P.K., Mehta N.K., Cell formation in the presence of reconfigurable machines, International Journal of Advanced Manufacturing Technology, Vol. 34, 2007, 335-345.

Tsubone H., Horikawa M., A comparison between machine flexibility and routing flexibility, International Journal of Flexible Manufacturing Systems, Vol. 11, 1999, 83-101.

Landers R.G., Min B.K., Koren Y., Reconfigurable machine tools, CIRP Annals – Manufacturing Technology, Vol. 50, 2001, 269-274.

Özgüven C., Özbakir L., Yavuz Y., Mathematical models for job-shop scheduling problems with routing and process plan flexibility, Applied Mathematical Modelling, Vol. 34, 2010, 1539-1548.

Stecke K.E., Raman N., FMS planning decision, operating flexibilities and system performance, IEEE Transactions on Engineering Management, Vol. 42, 1995, 82-90.

Rossi A., Dini G., Flexible job-shop scheduling with routing flexibility and separable setup times using ant colony optimization method, Robotics and Computer-Integrated Manufacturing, Vol. 23, 2007, 503-516.

Wang X.J., Zhang C.Y., Gao L., Li P.G., A survey and future trend of study on multi-objective scheduling, ICNC IEEE International Conference on Natural Computation, 2008, 382-391.

Fattahi P., Mehrabad M S.,Jolai F., Mathematical modeling and heuristic approaches to flexible job shop scheduling problem, Journal of Intelligent Manufacturing, Vol. 18, 2007, 331-342.

Bruker P., Schile R., Job shop scheduling with multi-purpose machine, Computing, Vol. 45, 1990, 369-375.

Motaghedi-Iarijani A., Sabri-Iaghaie K. & Heydari M., Solving flexible job shop scheduling with multi objective approach, International Journal of Industry Engineering & Production Research, ISSN: 2008-4889, Vol. 21, 2010, 197-209.

Demir Y., Kürnat İgleyen S., Evaluation of mathematical models for flexible job-shop scheduling
problems, Applied Mathematical Modelling, Vol. 21, 2010, 197-209.

Loukil T., Teghem J., Fortemps P., A multi-objective production scheduling case study solved by simulated annealing, European Journal of Operational Research, Vol. 179, 2007, 709-722.

Xia W., Wu Z., An effective hybrid optimization approach for multi-objective flexible job-shop scheduling problems, Computers & Industrial Engineering, Vol. 48, 2005, 409-425.

Fattahi P., Jolai F., Arkat J., Flexible job shop scheduling with overlapping in operations, Applied Mathematical Modelling, Vol. 33, 2009, 3076-3087.

Dalfard V.M., Mohammadi G., Two meta-heuristic algorithms for solving multi-objective flexible job-shop scheduling with parallel machine and maintenance constraints, Computers and Mathematics with Applications, Vol. 64, 2012, 2111-2117.

Brandimarte P., Routing and scheduling in a flexible job-shop by tabu search, Annals of Operations Research, Vol. 41, 1993, 157-183.

Li J.Q., Pan Q., Liang Y.C., An effective hybrid tabu search algorithm for multi-objective flexible job-shop scheduling problems, Computers & Industrial Engineering, Vol. 59, 2010, 647-662.

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, Vol. 190, 2008, 398-411.

Zhang Q., Manier H., Manier M.A., A genetic algorithm with tabu search procedure for flexible job-shop scheduling with transportation constraints and bounded processing times, Computers & Operations Research, Vol. 39, 2012, 1713-1723.

Kacem I., Hammadi S., Borne P., Pareto-optimality approach for flexible job-shop scheduling problem: hybridization of evolutionary algorithms and fuzzy logic, Mathematics and Computers in Simulation, Vol. 60, 2002, 245-276.

Pezzella F., Morganti G., Ciaschetti G., A genetic algorithm for the flexible job shop scheduling problem, Computers & Operations Research, Vol. 35, 2008, 3202-3212.

Bagheri A., Zandieh M., Mahdavi I., Yazdani M., An artificial immune algorithm for the flexible job-shop scheduling problem, Future Generation Computer Systems, Vol. 26, 2010, 533-541.

Xing L.N., Chen Y.W., Wang P., Zhao S., Xiong J., A knowledge-based ant colony optimization for flexible job-shop scheduling problems, Applied Soft Computing, Vol. 10, 2010, 888-896.

Moslehi G., Mahnam M., A Pareto approach to multi-objective flexible job-shop scheduling problem using particle swarm optimization and local search, International Journal of Production Economics, Vol. 129, 2011, 14-22.

Baykasoglu A., Ozbakir L., Sonmez A.I., Using multiple objective tabu search and grammars to model and solve multi-objective flexible job-shop scheduling problems, Journal of Intelligent Manufacturing, Vol. 15(6), 2004, 777-785.