Performance guarantees of local search for minsum scheduling problems
Author
dc.contributor.author
Correa Haeussler, José
Author
dc.contributor.author
Muñoz, Felipe T.
Admission date
dc.date.accessioned
2021-03-22T21:23:43Z
Available date
dc.date.available
2021-03-22T21:23:43Z
Publication date
dc.date.issued
2020
Cita de ítem
dc.identifier.citation
Mathematical Programming (2020)
es_ES
Identifier
dc.identifier.other
10.1007/s10107-020-01571-5
Identifier
dc.identifier.uri
https://repositorio.uchile.cl/handle/2250/178751
Abstract
dc.description.abstract
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.