We consider the problem of scheduling a set of jobs on a set of identical parallel machines, with the aim of minimizing the total weighted completion time. The problem has been solved in the literature with a number of mathematical formulations, some of which require the implementation of tailored branch-and-price methods. In our work, we solve the problem instead by means of new arc-flow formulations, by first representing it on a capacitated network and then invoking a mixed integer linear model with a pseudo-polynomial number of variables and constraints. According to our computational tests, existing formulations from the literature can solve to proven optimality benchmark instances with up to 100 jobs, whereas our most performing arc-flow formulation solves all instances with up to 400 jobs and provides very low gap for larger instances with up to 1000 jobs.

Enhanced arc-flow formulations to minimize weighted completion time on identical parallel machines / DE LUCENA KRAMER, ARTHUR HARRY FREDERICO; Dell'Amico, Mauro; Iori, Manuel. - In: EUROPEAN JOURNAL OF OPERATIONAL RESEARCH. - ISSN 0377-2217. - 275:1(2019), pp. 67-79. [10.1016/j.ejor.2018.11.039]

Enhanced arc-flow formulations to minimize weighted completion time on identical parallel machines

DE LUCENA KRAMER, ARTHUR HARRY FREDERICO
;
Dell'Amico, Mauro;Iori, Manuel
2019

Abstract

We consider the problem of scheduling a set of jobs on a set of identical parallel machines, with the aim of minimizing the total weighted completion time. The problem has been solved in the literature with a number of mathematical formulations, some of which require the implementation of tailored branch-and-price methods. In our work, we solve the problem instead by means of new arc-flow formulations, by first representing it on a capacitated network and then invoking a mixed integer linear model with a pseudo-polynomial number of variables and constraints. According to our computational tests, existing formulations from the literature can solve to proven optimality benchmark instances with up to 100 jobs, whereas our most performing arc-flow formulation solves all instances with up to 400 jobs and provides very low gap for larger instances with up to 1000 jobs.
2019
275
1
67
79
Enhanced arc-flow formulations to minimize weighted completion time on identical parallel machines / DE LUCENA KRAMER, ARTHUR HARRY FREDERICO; Dell'Amico, Mauro; Iori, Manuel. - In: EUROPEAN JOURNAL OF OPERATIONAL RESEARCH. - ISSN 0377-2217. - 275:1(2019), pp. 67-79. [10.1016/j.ejor.2018.11.039]
DE LUCENA KRAMER, ARTHUR HARRY FREDERICO; Dell'Amico, Mauro; Iori, Manuel
File in questo prodotto:
File Dimensione Formato  
1808.10661.pdf

Open access

Descrizione: Versione pre print
Tipologia: Versione originale dell'autore proposta per la pubblicazione
Dimensione 527.56 kB
Formato Adobe PDF
527.56 kB Adobe PDF Visualizza/Apri
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/1174503
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 24
  • ???jsp.display-item.citation.isi??? 20
social impact