Developing New Bounds for the Performance Guarantee of the Jump Neighborhood for Scheduling Jobs on Uniformly Related Machines

Felipe T. Muñoz (), Guillermo Latorre-Núñez and Mario Ramos-Maldonado
Additional contact information
Felipe T. Muñoz: Departamento de Ingeniería Industrial, Facultad de Ingeniería, Universidad del Bío-Bío, Concepción 4051381, Chile
Guillermo Latorre-Núñez: Departamento de Ingeniería Industrial, Facultad de Ingeniería, Universidad del Bío-Bío, Concepción 4051381, Chile
Mario Ramos-Maldonado: Departamento de Ingeniería en Maderas, Facultad de Ingeniería, Universidad del Bío-Bío, Concepción 4051381, Chile

Mathematics, 2023, vol. 12, issue 1, 1-16

Abstract: This study investigates the worst-case performance guarantee of locally optimal solutions to minimize the total weighted completion time on uniformly related parallel machines. The investigated neighborhood structure is Jump, also called insertion or move. This research focused on establishing the local optimality condition expressed as an inequality and mapping that maps a schedule into an inner product space so that the norm of the mapping is closely related to the total weighted completion time of the schedule. We determine two new upper bounds for the performance guarantee, which take the form of an expression based on parameters that describe the family of instances: the speed of the fastest machine, the speed of the slowest machine, and the number of machines. These new bounds outperform the parametric upper bound previously established in the existing literature and enable a better understanding of the performance of the solutions obtained for the Jump neighborhood in this scheduling problem, according to parameters that describe the family of instances.

Keywords: parallel machines; total weighted completion time; local search; jump neighborhood; performance guarantee (search for similar items in EconPapers)
JEL-codes: C (search for similar items in EconPapers)
Date: 2023
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
https://www.mdpi.com/2227-7390/12/1/6/pdf (application/pdf)
https://www.mdpi.com/2227-7390/12/1/6/ (text/html)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:gam:jmathe:v:12:y:2023:i:1:p:6-:d:1303246

Access Statistics for this article

Mathematics is currently edited by Ms. Emma He

More articles in Mathematics from MDPI
Bibliographic data for series maintained by MDPI Indexing Manager ().