This paper deals with the single-machine, parallel batching, total weighted completion time scheduling problem. A new graph-based formulation of the problem is proposed, where such graph has an exponential number of nodes and arcs. The problem is modeled as an integer linear program on this graph, combining features of a minimum cost flow problem and features of a set-partition problem as well. The continuous relaxation of this integer problem is solved via column generation, providing a very tight lower bound. Two different flavors of column generation are tested, leading to two models with identical performances in terms of bound tightness but in practice very different in terms of running time. A simple and effective rounding strategy applied to the faster model allows to generate heuristic solutions with values within a few percentage points from the optimum. Two different variants of the heuristic rounding procedure are tested; one allows to certify the optimality gap, while the other trades the ability to certify the gap with a greater computational speed.

Column generation and rounding heuristics for minimizing the total weighted completion time on a single batching machine

Druetto A.;Grosso A.
2022-01-01

Abstract

This paper deals with the single-machine, parallel batching, total weighted completion time scheduling problem. A new graph-based formulation of the problem is proposed, where such graph has an exponential number of nodes and arcs. The problem is modeled as an integer linear program on this graph, combining features of a minimum cost flow problem and features of a set-partition problem as well. The continuous relaxation of this integer problem is solved via column generation, providing a very tight lower bound. Two different flavors of column generation are tested, leading to two models with identical performances in terms of bound tightness but in practice very different in terms of running time. A simple and effective rounding strategy applied to the faster model allows to generate heuristic solutions with values within a few percentage points from the optimum. Two different variants of the heuristic rounding procedure are tested; one allows to certify the optimality gap, while the other trades the ability to certify the gap with a greater computational speed.
2022
139
1
10
https://www.sciencedirect.com/science/article/pii/S0305054821003476
Column generation; Parallel batch scheduling; Weighted completion time
Druetto A.; Grosso A.
File in questo prodotto:
File Dimensione Formato  
Column generation and rounding heuristics for minimizing the total weighted completion time on a single batching machine.pdf

Accesso riservato

Descrizione: PDF EDITORIALE
Tipo di file: PDF EDITORIALE
Dimensione 683.44 kB
Formato Adobe PDF
683.44 kB Adobe PDF   Visualizza/Apri   Richiedi una copia
postprint.pdf

Open Access dal 02/12/2024

Descrizione: POSTPRINT
Tipo di file: POSTPRINT (VERSIONE FINALE DELL’AUTORE)
Dimensione 623.81 kB
Formato Adobe PDF
623.81 kB Adobe PDF Visualizza/Apri

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

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