This paper addresses the problem of scheduling a set of jobs that are released over the time on a set of identical parallel machines, aiming at the minimization of the total weighted completion time. This problem, referred to as P|rj|∑wjCj, is of great importance in practice, because it models a variety of real-life applications. Despite its importance, the P|rj|∑wjCj has not received much attention in the recent literature. In this work, we fill this gap by proposing mixed integer linear programs and a tailored branch-and-price algorithm. Our branch-and-price relies on the decomposition of an arc-flow formulation and on the use of efficient exact and heuristic methods for solving the pricing subproblem. Computational experiments carried out on a set of randomly generated instances prove that the proposed methods can solve to the proven optimality instances with up to 200 jobs and 10 machines, and provide very low gaps for larger instances.

Scheduling jobs with release dates on identical parallel machines by minimizing the total weighted completion time / Kramer, A.; Dell'Amico, M.; Feillet, D.; Iori, M.. - In: COMPUTERS & OPERATIONS RESEARCH. - ISSN 0305-0548. - 123:(2020), pp. 1-16. [10.1016/j.cor.2020.105018]

Scheduling jobs with release dates on identical parallel machines by minimizing the total weighted completion time

Dell'Amico M.;
2020

Abstract

This paper addresses the problem of scheduling a set of jobs that are released over the time on a set of identical parallel machines, aiming at the minimization of the total weighted completion time. This problem, referred to as P|rj|∑wjCj, is of great importance in practice, because it models a variety of real-life applications. Despite its importance, the P|rj|∑wjCj has not received much attention in the recent literature. In this work, we fill this gap by proposing mixed integer linear programs and a tailored branch-and-price algorithm. Our branch-and-price relies on the decomposition of an arc-flow formulation and on the use of efficient exact and heuristic methods for solving the pricing subproblem. Computational experiments carried out on a set of randomly generated instances prove that the proposed methods can solve to the proven optimality instances with up to 200 jobs and 10 machines, and provide very low gaps for larger instances.
2020
9-giu-2020
123
1
16
Scheduling jobs with release dates on identical parallel machines by minimizing the total weighted completion time / Kramer, A.; Dell'Amico, M.; Feillet, D.; Iori, M.. - In: COMPUTERS & OPERATIONS RESEARCH. - ISSN 0305-0548. - 123:(2020), pp. 1-16. [10.1016/j.cor.2020.105018]
Kramer, A.; Dell'Amico, M.; Feillet, D.; Iori, M.
File in questo prodotto:
File Dimensione Formato  
KramerDellamicoFeilletIori2020.pdf

Accesso riservato

Tipologia: Versione pubblicata dall'editore
Dimensione 582.5 kB
Formato Adobe PDF
582.5 kB Adobe PDF   Visualizza/Apri   Richiedi una copia
Pubblicazioni consigliate

Licenza Creative Commons
I metadati presenti in IRIS UNIMORE sono rilasciati con licenza Creative Commons CC0 1.0 Universal, mentre i file delle pubblicazioni sono rilasciati con licenza Attribuzione 4.0 Internazionale (CC BY 4.0), salvo diversa indicazione.
In caso di violazione di copyright, contattare Supporto Iris

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11380/1208059
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 10
  • ???jsp.display-item.citation.isi??? 8
social impact