Publicación: PERFORMANCE GUARANTEE OF THE JUMP NEIGHBORHOOD FOR SCHEDULING JOBS ON UNIFORMLY RELATED MACHINES
Fecha
2022
Autores
Título de la revista
ISSN de la revista
Título del volumen
Editor
RAIRO-OPERATIONS RESEARCH
Resumen
WE STUDY THE WORST CASE PERFORMANCE GUARANTEE OF LOCALLY OPTIMAL SOLUTIONS FOR THE PROBLEM OF SCHEDULING JOBS ON UNIFORMLY RELATED PARALLEL MACHINES WITH THE OBJECTIVE OF MINIMIZING THE TOTAL WEIGHTED COMPLETION TIME. THE QUALITY OF LOCALLY OPTIMAL SOLUTIONS UNDER THE JUMP NEIGHBORHOOD IS
ANALYZED, WHICH CONSISTS OF ITERATIVELY MOVING A SINGLE JOB FROM ONE MACHINE TO ANOTHER, IMPROVING THE TOTAL WEIGHTED COMPLETION TIME IN EACH ITERATION AND STOPPING ONCE IMPROVEMENT IS NO LONGER POSSIBLE. WE PROPOSE AN UPPER BOUND FOR THE TOTAL WEIGHTED COMPLETION TIME FOR THE SOLUTIONS OBTAINED BY THIS
LOCAL SEARCH, AND UPPER AND LOWER BOUNDS FOR THE PERFORMANCE GUARANTEE OF THE OBTAINED LOCALLY OPTIMAL SOLUTIONS. ADDITIONALLY, THE CASE OF IDENTICAL PARALLEL MACHINES IS ANALYZED.
