A TABU SEARCH ALGORITHM FOR SOLVING A BICRITERIA FLEXIBLE JOB SHOP SCHEDULING PROBLEM

We consider in this paper a scheduling problem issued from an industrial context. This problem can be seen as a flexible job shop scheduling problem. Solutions are evaluated using two criteria: the makespan and the maximum lateness. We propose a Tabu search algorithm that finds a solution with minimum makespan, respecting a given bound for the maximum lateness. This approach is called the epsilon-constraint approach in multicriteria literature and it can be used for finding the whole set of dominant criteria vectors. The Tabu search algorithm is tested on benchmark instances of the literature and results are discussed.