Performance guarantees of local search for minsum scheduling problems

• 成果类型: Article
• 署名作者: Correa, Jose R.; Munoz, Felipe T.
• 署名单位: Universidad de Chile; Universidad del Bio-Bio
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-020-01571-5
• 发表日期: 2022
• 页码: 847-869
• 关键词: weighted completion-time; Approximation algorithms; parallel; neighborhoods

摘要

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.