Open Access

ARTICLE

Minimizing Total Tardiness in a Two-Machine Flowshop Scheduling Problem with Availability Constraints

by Mohamed Ali Rakrouki^1,2,*, Abeer Aljohani¹, Nawaf Alharbe¹, Abdelaziz Berrais², Talel Ladhari²

1 Applied College, Taibah University, Saudi Arabia
2 University of Tunis, Tunis, Tunisia

* Corresponding Author: Mohamed Ali Rakrouki. Email:

Intelligent Automation & Soft Computing 2023, 35(1), 1119-1134. https://doi.org/10.32604/iasc.2023.028604

Received 13 February 2022; Accepted 24 March 2022; Issue published 06 June 2022

Abstract

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.

---

Keywords

---