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

In this paper,we consider the problem of minimizing the total tardiness in a deterministic two-machine permutationflowshop scheduling problem subject to release dates of jobs and known unavailability periods of machines.The theoretical and practical importance of minimizing tardiness inflowshop scheduling environment has motivated us to investigate and solve this interested two-machine scheduling problem.Methods that solve this important optimality criterion inflowshop environment are mainly heuristics.In fact,despite the N P-hardnessin 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 developfive 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.