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.
University of MontrealCenter for Research on Transportation (CRT)/CIRRELT
P.O. Box 6128, Station Centre-ville
Montreal, Quebec Canada H3C 3J7
- Publication Date: 1995
- Pagination: 19 p.
- TRT Terms: Heuristic methods; Optimization; Scheduling; Sequencing
- Old TRIS Terms: Scheduling management; Searching
- Subject Areas: Highways; Planning and Forecasting;
- Accession Number: 00719128
- Record Type: Publication
- Files: TRIS
- Created Date: Mar 16 1996 12:00AM