A Scheduling Model for the Re-entrant Manufacturing System and Its Optimization by NSGA-II

Document Type: Research Paper


1 Department of Industrial Engineering, College of Engineering, University of Tehran, Tehran, Iran

2 Department of Industrial Engineering, Amir Kabir University, Tehran, Iran


In this study, a two-objective mixed-integer linear programming model (MILP) for multi-product re-entrant flow shop scheduling problem has been designed. As a result, two objectives are considered. One of them is maximization of the production rate and the other is the minimization of processing time. The system has m stations and can process several products in a moment. The re-entrant flow shop scheduling problem is well known as NP-hard problem and its complexity has been discussed by several researchers. Given that NSGA-II algorithm is one of the strongest and most applicable algorithm in solving multi-objective optimization problems, it is used to solve this problem. To increase algorithm performance, Taguchi technique is used to design experiments for algorithm’s parameters. Numerical experiments are proposed to show the efficiency and effectiveness of the model. Finally, the results of NSGA-II are compared with SPEA2 algorithm (Strength Pareto Evolutionary Algorithm 2). The experimental results show that the proposed algorithm performs significantly better than the SPEA2.


Main Subjects

Belkaid, F., Yalaoui, F., & Sari, Z. (2016). An Efficient Approach for the Re-entrant Parallel Machines Scheduling Problem under Consumable Resources Constraints. International journal of Information Systems and Supply Chain Management, Vol. 9 (3), July, pp. 1-25.

Chen, J-S., Pan, J.C-H., & Wu, C-K. (2008). Hybrid tabu search for re-entrant permutation flow-shop scheduling problem. Expert Systems with Applications, Vol. 34, pp. 1924–1930.

Choi, S-W., & Kim, Y-D. (2008). Minimizing makespan on an m-machine re-entrant flowshop. Computers & Operations Research, Vol. 35, pp. 1684 – 1696.

Choi, S-W., & Kim, Y-D. (2009). Minimizing total tardiness on a two-machine re-entrant flowshop. European Journal of Operational Research, Vol. 199, pp. 375–384.

Choi, J-Y., & KO, S-S. (2009). Simulation-based two-phase genetic algorithm for the capacitated re-entrant line scheduling problem. Computers & Industrial Engineering, Vol. 57, pp. 660–666.

Dong, M., He, F. (2012). A new continuous model for multiple re-entrant manufacturing systems. European Journal of Operational Research, Vol. 223, pp. 659–668.

Deb, K., Pratap, A., Agarwal, S., & Meyarivan, T. (2002). A fast and elitist multiobjective genetic algorithm: NSGA- . IEEE Trans. Evol. Comput, Vol. 6 (2), pp. 182–197.

Fattahi, P., Tavakoli, N.B., Jalilvand-Nejad, A., & Jolai, F. (2010). A hybrid algorithm to solve the problem of re-entrant manufacturing system scheduling. CIRP Journal of manufacturing Science and Technology, Vol. 3, pp. 268-278.

Cavory, G., Dupas, R., & Goncalves, G. (2005). A Genetic Approach to Solving the Problem of Cyclic Job Shop Scheduling with Linear Constraints. European Journal of Operational Research, Vol. 161, pp. 73–85.

Hinze, R. (2015). A Lot Streaming Model for a Re-entrant Flow Shop Scheduling Problem with Missing Operations. Logistics Management, pp. 149-158.

Hsu, T., Korbaa, O., Dupas, D., & Goncalves, G. (2008). Cyclic Scheduling for F.M.S.: Modeling and Evolutionary Solving Approach. European Journal of Operational Research, Vol. 191, pp. 464–484.

Hwang, H., & Sun, J.U. (1998). Production sequencing problem with re-entrant work flows and sequence dependent setup times. Int. J. Prod. Res., Vol. 36, pp. 2435–2450.

Jeong, B., & Kim, Y-D. (2014). Minimizing total tardiness in a two-machine re-entrant flowshop with sequence-dependent setup times. Accepted Manuscript to appear in: Computers & Operations Research.

Jing, C., Tang, G., & Qian, X. (2008). Heuristic algorithms for two machine re-entrant flow shop. Theoretical Computer Science, Vol. 400, pp. 137–143.

Jing, C., Huang, W., & Tang, G. (2011). Minimizing total completion time for re-entrant flow shop scheduling problems. Theoretical Computer Science, Vol. 412, pp. 6712-6719.

Kia, H., Ghodsypour, S.H., & Davoudpour, H. (2017). New scheduling rules for a dynamic flexible flow line problem with sequence-dependent setup times. Journal of Industrial Engineering International, Vol. 13(1), pp. 1–10.

Kim, S., Park, Y., & Jun, C-H. (2006). Performance evaluation of re-entrant manufacturing system with production loss using mean value analysis. Computers & Operations Research, Vol. 33, pp. 1308–1325.

Kubale, M., & Nadolski, A. (2005). Chromatic Scheduling in a Cyclic Open Shop. European Journal of Operational Research, Vol. 164, pp. 585–591.

Kumar, V.M., Murthy, A., & Chandrashekara, K. (2012). A hybrid algorithm optimization approach for machine loading problem in flexible manufacturing system. Journal of Industrial Engineering International, Vol. 8(1), pp. 3-15.

Lee, C.K.M., & Lin, D. (2010). Hybrid genetic algorithm for bi-objective flow shop scheduling problems with re-entrant jobs. IEEE International Conference on Industrial Engineering and Engineering Management, IEEE Computer Society, Macao, China, pp. 1240–1245.

Lin D., Lee, C.K.M., & Ho, W. (2013). Multi-level genetic algorithm for the resource-constrained re-entrant scheduling problem in the flow shop. Engineering Applications of Artificial Intelligence, Vol. 26, pp. 1282-1290.

Mirabi, M., Fatemi Ghomi, S.M.T., & Jolai, F. (2014). A novel hybrid genetic algorithm to solve the make-to-order sequence-dependent flow-shop scheduling problem. Journal of Industrial Engineering International,  Vol. 10(2), pp. 57-69.

Rau, H., & Cho, K.H. (2009). Genetic algorithm modeling for the inspection allocation in re-entrant production systems. Expert Syst. Appl.,  Vol.  36, pp. 11287–11295.

Teruo, M. (1990). The New Experimental Design, Taguchi’s Approach to Quality Engineering. ASI Press, First Editon, Printed In The United States Of American.

Xu, J., Lin W-C., Wu, J., Cheng, S-R., & Wu, C-C. (2016).Heuristic based genetic algorithms for the re-entrant total completion time flowshop scheduling with learning consideration. International Journal of Computational Intelligence Systems,  Vol.  9, pp. 1082-1100.

Xu, J., Yin, Y., Cheng, T.C.E., Wu, C-C., & Gu, S. (2014). A memetic algorithm for the re-entrant permutation flowshop scheduling problem to minimize the makespan. Applied Soft Computing,  Vol.  24, pp. 277-283.

Zitzler, E., Laumanns, M., & Thiele, L. (2001). SPEA2: Improving the strength Pareto evolutionary algorithm. Technical Report 103, Computer Engineering and Networks Laboratory (TIK), ETH Zurich, Zurich, Switzerland.