Solving multi-objective production scheduling problems with Tabu Search

Most of multiple criteria scheduling problems are NP-hard, so that exact pr ocedures can only solve small problems and with two criteria. The complexit y and the diversity of multiple criteria scheduling problems resulted in ma ny alternative approaches to solve them. Exact and approximate procedures p roposed in the literature are mainly dedicated to the problem to be solved and their performance depends on the problem data, on the criteria optimize d, and are generally difficult to implement. We propose in this paper a Tab u Search approach to multiple criteria scheduling problems. The proposed pr ocedure is a general flexible method, able to solve hard multiple criteria scheduling problems, easy to implement, and providing a set of potential ef ficient schedules. The criteria are any combination chosen from (C-max,T-ma x, (L) over bar, N-T and (F) over bar).