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.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.