Journal of Industrial Engineering and Management Studies

A hybrid algorithm to minimize total tardiness in cyclic flexible job shop scheduling with assembly stage and sequence-dependent setup time

Document Type : Original Article

Authors

N. Bagheri Rad
Javad Behnamian

Department of Industrial Engineering, Faculty of Engineering, Bu-Ali Sina University, Hamedan, Iran.

10.22116/jiems.2026.392651.1512
Abstract
This paper studies a cyclic flexible job shop scheduling problem with assembly operations and sequence-dependent setup time, with the objective of minimizing total tardiness. In this production system, in the first stage, parts are produced in a flexible job shop system, and in the second stage, they are assembled into finished products. In this problem, products must be delivered in predetermined batch sizes within a definite time window. To solve the problem, a mixed-integer linear model is developed. Since the problem is NP-hard, a hybrid genetic algorithm and a parallel variable neighborhood search algorithm are proposed to solve medium- and large-sized instances. The hybrid approach leverages the global search capabilities of the genetic algorithm and the robust local refinement of the parallel variable neighborhood search, ensuring better escape from local optima and improved convergence rates. After fine-tuning the hybrid algorithm using the Taguchi method, the obtained results are compared with those obtained from GAMS and a conventional genetic algorithm on various instances. The computational results show that the proposed hybrid algorithm not only reduces total tardiness more effectively but also offers significant computational efficiency improvements, thereby demonstrating its practical applicability in complex manufacturing scenarios characterized by stringent delivery requirements.

Keywords

Assembly sequence planning
Cyclic scheduling
Flexible job shop
Setup time
Flexible manufacturing
T. Borreguero-Sanchidrián, R. Pulido, Á. García-Sánchez and M. Ortega-Mier, 2018. Flexible job shop scheduling with operators in aeronautical manufacturing: A case study. IEEE Access, 6: 224-233.
 Lee, C.Y., Cheng, T.C.E., Lin, B.M.T. 1993. Minimizing the makespan in the 3- machine assembly-type flow shop scheduling problem. Management Science, 39(5): 616-625.
Sculli, D. 1979. Priority Dispatching Rules in Job Shops with Assembly Operations and Random Delays. OMEG, 8(2): 227-234.
Cheng, T.C.E. 1990. Analysis of material flow in a job shop with assembly operations. International Journal of Production Research, 28(7): 1369-1383.
Zhang, R.A. 2011. Simulation-based Genetic Algorithm for Job Shop Scheduling with Assembly Operations. International Journal of Advancements in Computing Technology, 3(10):132
Dimyati, T. 2007. Minimizing production flow time in a process and assembly job shop. Proceedings of the International Seminar on Industrial engineering and Management, Jakarta, 68- 73.
Rossi, A. 2014. Flexible job shop scheduling with sequence-dependent setup and transportation times by ant colony with reinforced pheromone relationships. International Journal of Production Economics, 153: 253-267.
Shen, L., Dauzère-Pérès, S., Neufeld, J.S. 2018. Solving the flexible job shop scheduling problem with sequence-dependent setup times. European Journal of Operational Research, 256(2):503-516.
Azzouz, A., Ennigrou, M., Said, L.B. 2017. A self-adaptive evolutionary algorithm for solving flexible job-shop problem with sequence-dependent setup time and learning effects. 2017 IEEE Congress on Evolutionary Computation (CEC).
RamezaniEmai, P., Rabiee, M., Jolai, F. 2015. No-wait flexible flowshop with uniform parallel machines and sequence-dependent setup time: a hybrid meta-heuristic approach. Journal of Intelligent Manufacturing, 26(4): 731-744.
Mousakhani, M. 2013. Sequence-dependent setup time flexible job shop scheduling problem to minimise total tardiness. International Journal of Production Research, 51(12): 3476-3487.
Cuninghame-Green, RA. 1960. Process synchronisation in a steelworks- a problem of feasibility, Proceedings of the 2nd international conference on operational research, 323-328.
Cuninghame-Green, RA. 1962. Describing industrial processes with interference and approximating their steady-state behavior, Operational Research Society, 13(1): 95-100.
Hanen, C., & Munier, A. 1997. Cyclic scheduling on parallel processors: An overview. In P. Chretienne, E. G. Coffman, J. K. Lenstra, Z. Liu (Eds.), Scheduling theory and its applications. New York: Wiley.
Brucker, P., & Kampmeyer, T. 2008a. A general model for cyclic machine scheduling problems. Discrete Applied Mathematics, 156(13): 2561–2572.
Brucker, P., & Kampmeyer, T. 2008b. Cyclic job shop scheduling problem with blocking. Journal of Intelligent Manufacturing, 159(1): 161–181.
Romanova, A. A., & Servakh, V. V. 2009. Optimization of processing identical jobs by means of cyclic schedules. Journal of Intelligent Manufacturing, 3(4), 496–504.
Ouenniche, J., & Bertrand, J. W. M. 2001. The finite horizon economic lot sizing problem in job shops: The multiple cycle approach. International Journal of Production Economics, 74, 1: 49–61.
Bożejko, W., Gnatowski, A., Pempera, J., Wodecki, M. 2017. Parallel tabu search for the cyclic job shop scheduling problem, Computers & Industrial Engineering,113:512-524.
Jalilvand-Nejad.A., Fattahi, P. 2015. A mathematical model and genetic algorithm to cyclic flexible job shop scheduling problem. Journal of Intelligent Manufacturing, 26(6): 1085-1098.
Quinton, F., Hamaz, I., Houssin, L 2018. Algorithms for the flexible cyclic job shop problem, 14th International Conference on Automation Science and Engineering (CASE), Munich, Germany.
Elmi, A, Thiruvady, DR, Ernst, AT. Blocking Cyclic Job-Shop Scheduling Problems. Algorithms. 2022; 15(10):375.
Fattahi, P., Bagheri Rad, N., Daneshamooz, F. and Ahmadi, S. 2020. A new hybrid particle swarm optimization and parallel variable neighborhood search algorithm for flexible job shop scheduling with assembly process", Assembly Automation.
 Garey M.R, Johnson D. S, Sethi R. The complexity of flow shop and job shop scheduling. Mathematics of Operations Research 1976; 1(2): 117–29.
 Mladenovic, N. and Hansen, P. 1997.Variable neighborhood search", Computers and Operations Research, 24(11), pp. 1097-1100.
Yazdani, M., Amiri, M., & Zandieh, M. 2010. Flexible job shop scheduling with parallel variable neighborhood search algorithm. Expert system with applications, 37(1): 678-687.
Pezzella, F., Morganti, G., Ciaschetti, G. 2008. A genetic algorithm for the Flexible Job-shop Scheduling Problem. Computers & Operations Research, 35(10):3202-3212.
Cui, Z., Chang, Y., Zhang, J., Cai, X., & Zhang, W. 2019. Improved NSGA-III with selection-and-elimination operator, Swarm and Evolutionary Computation, 49: 23-33.
Koohestani, B. 2020. A crossover operator for improving the efficiency of permutation-based genetic algorithms, Expert Systems with Applications, 151: 113381.
Cazacu, R. 2017. Comparative Study between the Improved Implementation of 3 Classic Mutation Operators for Genetic Algorithms, Procedia Engineering, 181: 634-640.
Komijan, R.A., Tavakkoli-Moghaddam, R., Dalil, S. 2020. A mathematical model for an integrated airline fleet assignment and crew scheduling problem solved by vibration damping optimization. Scientia Iranica.
Journal of Industrial Engineering and Management Studies
Volume 13, Issue 1
July 2026
Pages 97-108

Home

Guide for Authors

Publication Ethics

Submit Manuscript

Reviewers

Contact Us