We study a prize-collecting single-machine scheduling problem with hard deadlines, where the objective is to minimize the difference between the total tardiness and the total prize of the selected jobs. This problem is motivated by industrial applications, both as a stand-alone model and as a pricing subproblem in column-generation algorithms for parallel machine scheduling problems. A preprocessing rule is devised to identify jobs that cannot belong to any optimal schedule. The resulting reduced problem is solved to optimality by a branch-and-bound algorithm and two integer linear programming formulations. The algorithm and the formulations are experimentally compared on randomly generated benchmark instances.

A branch-and-bound algorithm for the prize-collecting single-machine scheduling problem with deadlines and total tardiness minimization

Hosteins P.
;
2018-01-01

Abstract

We study a prize-collecting single-machine scheduling problem with hard deadlines, where the objective is to minimize the difference between the total tardiness and the total prize of the selected jobs. This problem is motivated by industrial applications, both as a stand-alone model and as a pricing subproblem in column-generation algorithms for parallel machine scheduling problems. A preprocessing rule is devised to identify jobs that cannot belong to any optimal schedule. The resulting reduced problem is solved to optimality by a branch-and-bound algorithm and two integer linear programming formulations. The algorithm and the formulations are experimentally compared on randomly generated benchmark instances.
2018
30
1
168
180
https://pubsonline.informs.org/doi/10.1287/ijoc.2017.0772
prize-collecting; single-machine scheduling; integer linear programming; branch and bound
Cordone R.; Hosteins P.; Righini G.
File in questo prodotto:
File Dimensione Formato  
bi_obj_TT_dl_rev2.pdf

Open Access dal 24/01/2020

Descrizione: postprint
Tipo di file: POSTPRINT (VERSIONE FINALE DELL’AUTORE)
Dimensione 414.72 kB
Formato Adobe PDF
414.72 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/1950555
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 14
  • ???jsp.display-item.citation.isi??? 12
social impact