Volume 56, Number 2, March-April 2022
|1079 - 1088
|14 April 2022
Performance guarantee of the jump neighborhood for scheduling jobs on uniformly related machines
Department of Industrial Engineering, Universidad del Bío-Bío, Concepción, Chile
2 Faculty of Forestry Sciences, Universidad de Concepción, Concepción, Chile
* Corresponding author: email@example.com
Accepted: 18 March 2022
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.
Mathematics Subject Classification: 90B35 / 90C59 / 68M20 / 68W40
Key words: Parallel machines / total weighted completion time / local search / performance guarantee
© The authors. Published by EDP Sciences, ROADEF, SMAI 2022
This is an Open Access article distributed under the terms of the Creative Commons Attribution License (https://creativecommons.org/licenses/by/4.0), which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.
Current usage metrics show cumulative count of Article Views (full-text article views including HTML views, PDF and ePub downloads, according to the available data) and Abstracts Views on Vision4Press platform.
Data correspond to usage on the plateform after 2015. The current usage metrics is available 48-96 hours after online publication and is updated daily on week days.
Initial download of the metrics may take a while.