Paper Info
Title
Stochastic local search for multiprocessor scheduling for minimum total tardiness
Abstract
The multi-processor total tardiness problem (MPTTP)is an NP-hard scheduling problem, in which the the goal is to minimise the tardness of a set of jobs that are processed on a number of processors. Exact algorithms like branch and bound have proven to be impractical for the MPTTP, leaving stochastic local search (SLS) algorithms as the main alternative to find high-quality schedules. Among the available SLS techniques, iterated local search (ILS) has been shown to be an effective algorithm for the single processor case. Therefore, here we extend this technique to the multi-processor case, but our computational results indicate that ILS performance is not fully satisfying. To enhance ILS performance, we consider the use of population-based ILS extensions. Our final experimental results show that the usage of a population of search trajectories yields a more robust algorithm capable of finding best known solutions to difficult instances more reliably and in less computation time than a single ILS trajectory.
Year
DOI
Venue
2003
10.1007/3-540-44886-1_10
Canadian Conference on AI
Keywords
Field
DocType
search trajectories yield,iterated local search,single ils trajectory,multiprocessor scheduling,minimum total tardiness,np-hard scheduling problem,ils performance,population-based ils extension,exact algorithm,available sls technique,stochastic local search,effective algorithm,branch and bound,satisfiability,scheduling problem
Memetic algorithm,Mathematical optimization,Branch and bound,Multiprocessor scheduling,Job shop scheduling,Search algorithm,Tardiness,Computer science,Algorithm,Local search (optimization),Iterated local search
Conference
Volume
ISSN
ISBN
2671
0302-9743
3-540-40300-0
Citations 
PageRank 
References 
0
0.34
11
Authors
3
Name
Order
Citations
PageRank
Michael Pavlin100.34
Holger H. Hoos25327308.70
thomas stutzle35684352.15