A TABU SEARCH HEURISTIC FOR THE MULTIPROCESSOR SCHEDULING PROBLEM WITH SEQUENCE-DEPENDENT SETUP TIMES

This article deals with the problem of scheduling n jobs on m identica l parallel processors with the objective of minimizing the total execu tion time (makespan). A new three-phase heuristic s proposed for solvi ng this problem. An initial phase constructs a starting solution which is improved, in a second phase, by means of a tabu search method. A f inal phase follows attempting a further improvement in the current sol ution. Numerical rests in a series of randomly generated problems indi cate that the proposed method outperforms a previous heuristic, Compar isons with an exact procedure attest that our method produces good-qua lity solutions in reasonable running times.