This work deals with the single-machine scheduling problem of minimizing the total weighted completion time in a parallel-batching environment. A very large, graph-based linear programming model is proposed in order to solve a tight relaxation of such problem by means of column generation and dynamic programming techniques. Both a path-based variant and an arc-based variant of the model are developed, in order to obtain two lower bounds of equally good quality. These outclasses the previously known state-of-the-art lower bound. Using the most time efficient of the two variants, the arc-based lower bound, two simple and effective rounding strategies are built, exploiting the information gathered from the relaxation. Combining the strict lower bounds and the effective heuristics allows to generate good feasible solutions with values within a few percentage points from the optimum.

Column generation bounds on a network flow model to minimize the total weighted completion time for a single parallel batching machine

Alessandro Druetto;Andrea Cesare Grosso
2021

Abstract

This work deals with the single-machine scheduling problem of minimizing the total weighted completion time in a parallel-batching environment. A very large, graph-based linear programming model is proposed in order to solve a tight relaxation of such problem by means of column generation and dynamic programming techniques. Both a path-based variant and an arc-based variant of the model are developed, in order to obtain two lower bounds of equally good quality. These outclasses the previously known state-of-the-art lower bound. Using the most time efficient of the two variants, the arc-based lower bound, two simple and effective rounding strategies are built, exploiting the information gathered from the relaxation. Combining the strict lower bounds and the effective heuristics allows to generate good feasible solutions with values within a few percentage points from the optimum.
31st European Conference on Operational Research
Atene
11/07/2021 - 14/07/2021
31st European Conference on Operational Research
Rudolf Vetschera
294
294
https://www.euro-online.org/media_site/reports/EURO31_AB.pdf
Scheduling, Graphs and Networks, Column Generation
Alessandro Druetto, Andrea Cesare Grosso
File in questo prodotto:
File Dimensione Formato  
EURO31_AB.pdf

Accesso aperto

Descrizione: Book of Abstracts
Tipo di file: MATERIALE NON BIBLIOGRAFICO
Dimensione 2.92 MB
Formato Adobe PDF
2.92 MB 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: http://hdl.handle.net/2318/1795394
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus ND
  • ???jsp.display-item.citation.isi??? ND
social impact