Publicación: PERFORMANCE GUARANTEES OF LOCAL SEARCH FOR MINSUM SCHEDULING PROBLEMS
Fecha
2020
Autores
Título de la revista
ISSN de la revista
Título del volumen
Editor
MATHEMATICAL PROGRAMMING
Resumen
WE STUDY THE WORST-CASE PERFORMANCE GUARANTEE OF LOCALLY OPTIMAL SOLUTIONS FOR THE PROBLEM OF MINIMIZING THE TOTAL WEIGHTED AND UNWEIGHTED COMPLETION TIME ON PARALLEL MACHINE ENVIRONMENTS. OUR METHOD MAKES USE OF A MAPPING THAT MAPS A SCHEDULE INTO AN INNER PRODUCT SPACE SO THAT THE NORM OF THE MAPPING IS CLOSELY RELATED TO THE COST OF THE SCHEDULE. WE APPLY THE METHOD TO STUDY THE MOST BASIC LOCAL SEARCH HEURISTICS FOR SCHEDULING, NAMELY JUMP AND SWAP, AND ESTABLISH THEIR WORST-CASE PERFORMANCE IN THE CASE OF UNRELATED, RESTRICTED RELATED AND RESTRICTED IDENTICAL MACHINES.
