Solving multi-objective production scheduling problems with Tabu Search

Most of multiple criteria scheduling problems are NP-hard, so that exact procedures can only solve small problems and with two criteria. The complexity and the diversity of multiple to solve them. Exact and approximate procedures proposed in the literature are mainly dedicated to the problem to be solved and their performance depends on the problem data, on the criteria optimized, and are generally difficult to implement. We propose in this paper a Tabu Search approach to multiple criteria scheduling problems. The proposed procedure is a general flexible method, able to solve hard multiple criteria scheduling problems, easy to implement, and providing a set of potential efficient schedules. The criteria are any combination chosen from (Cmax, Tmax, L̄, NT and F̄).