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

This study considers the problem of scheduling n jobs on m identical parallel processors, with the objective of minimizing the total execution time. The authors propose a new three-phase heuristic for solving this problem. An initial phase constructs a starting solution which is improved in a second phase by a tabu search method. A post-optimization phase follows, attempting a further improvement in the current solution. To determine whether the proposed method outperforms a previous heuristic, the authors performed numerical tests on a series of randomly generated problems. They also compared the quality of the solutions obtained, taking into account the running times, with the solutions obtained using an exact procedure.

  • Corporate Authors:

    University of Montreal

    Center for Research on Transportation (CRT)/CIRRELT
    P.O. Box 6128, Station Centre-ville
    Montreal, Quebec  Canada  H3C 3J7
  • Publication Date: 1995

Language

  • English

Media Info

  • Pagination: 19 p.

Subject/Index Terms

Filing Info

  • Accession Number: 00719128
  • Record Type: Publication
  • Files: TRIS
  • Created Date: Mar 16 1996 12:00AM