Vol.35, No.1, 2023, pp.1119-1134, doi:10.32604/iasc.2023.028604
Minimizing Total Tardiness in a Two-Machine Flowshop Scheduling Problem with Availability Constraints
  • Mohamed Ali Rakrouki1,2,*, Abeer Aljohani1, Nawaf Alharbe1, Abdelaziz Berrais2, Talel Ladhari2
1 Applied College, Taibah University, Saudi Arabia
2 University of Tunis, Tunis, Tunisia
* Corresponding Author: Mohamed Ali Rakrouki. Email:
Received 13 February 2022; Accepted 24 March 2022; Issue published 06 June 2022
In this paper, we consider the problem of minimizing the total tardiness in a deterministic two-machine permutation flowshop scheduling problem subject to release dates of jobs and known unavailability periods of machines. The theoretical and practical importance of minimizing tardiness in flowshop scheduling environment has motivated us to investigate and solve this interested two-machine scheduling problem. Methods that solve this important optimality criterion in flowshop environment are mainly heuristics. In fact, despite the -hardness in the strong sense of the studied problem, to the best of our knowledge there are no approximate algorithms (constructive heuristics or metaheuristics) or an algorithm with worst case behavior bounds proposed to solve this problem. Thus, the design of new promising algorithms is desirable. We develop five metaheuristics for the problem under consideration. These metaheuristics are: the Particle Swarm Optimization (PSO), the Differential Evolution (DE), the Genetic Algorithm (GA), the Ant Colony Optimization (ACO) and the Imperialist Competitive Algorithm (ICA). All the proposed metaheuristics are population-based approaches. These metaheuristics have been improved by integrating different local search procedures in order to provide more satisfactory, especially in term of quality solutions. Computational experiments carried out on a large set of randomly generated instances provide evidence that the Imperialist Competitive Algorithm (ICA) records the best performances.
Optimization; machine scheduling; flowshop; evolutionary algorithms
Cite This Article
M. Ali Rakrouki, A. Aljohani, N. Alharbe, A. Berrais and T. Ladhari, "Minimizing total tardiness in a two-machine flowshop scheduling problem with availability constraints," Intelligent Automation & Soft Computing, vol. 35, no.1, pp. 1119–1134, 2023.
This work is licensed under a Creative Commons Attribution 4.0 International License , which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.