Performance guarantees of local search for minsum scheduling problems
- PDF / 506,138 Bytes
- 23 Pages / 439.37 x 666.142 pts Page_size
- 78 Downloads / 175 Views
Series A
Performance guarantees of local search for minsum scheduling problems José R. Correa1
· Felipe T. Muñoz2
Received: 5 August 2019 / Accepted: 21 September 2020 © Springer-Verlag GmbH Germany, part of Springer Nature and Mathematical Optimization Society 2020
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. Keywords Local search · Performance guarantee · Parallel machines · Total weighted completion time Mathematics Subject Classification 90B35 · 90C59 · 68M20 · 68W40
1 Introduction Machine scheduling problems have been widely studied in recent decades because of their practical relevance in production and communication systems and their theoretical interest. As these problems are typically NP-hard, designing and analyzing approximation algorithms has been a central object of study to the theoretical computer science community. However, these algorithms are often impractical so the real-world methods of choice boil down to heuristic approaches including integer programming, constraint programming and local search. In this paper, we focus on the latter method and study its worst-case performance guarantees. Local search methods are indeed
B
José R. Correa [email protected] Felipe T. Muñoz [email protected]
1
Department of Industrial Engineering, Universidad de Chile, Santiago, Chile
2
Department of Industrial Engineering, Universidad del Bío-Bío, Concepción, Chile
123
J. R. Correa, F. T. Muñoz
widely used in practice and exhibit good empirical behavior, but little is known about their worst-case performance. We refer the reader to the surveys of Angel [3] and Michiels, Aarts and Korst [29] who present a review of performance guarantees and other theoretical aspects of local search for a wide variety of combinatorial problems, including scheduling problems. Specifically, in this paper we consider the problem of minimizing the total weighted completion time on parallel machine environments, and study the worst-case performance guarantee of local optima solutions for jump and swap neighborhoods. We provide a systematic method to analyze the worst-case performance of these basic local search heuristics for scheduling with the weighted completion time objective. The method, which turns out to be quite simple, involves relating the local optimality conditions with an appropriate schedule mapping that maps a schedule into an inner product space, and allows to write the condition in terms of the inner product of the mappings of a global optimum and a local optimum [11]. 1.
Data Loading...
