We study a prize-collecting single machine scheduling problem with hard deadlines, where the objective is to minimise the difference between the total tardiness and the total prize of selected jobs. This problem is motivated by industrial applications, both as a standalone model and as a pricing problem for column generation approaches to parallel machine scheduling problems. It is handled through the use of exact approaches, in the form of a Branch and Bound (B&B) algorithm and an Integer Linear Programming (ILP) formulation. The B&B and ILP formulation are compared in their efficiency on randomly generated benchmark instances.
The Prize-collecting Scheduling Problem with Deadlines / P. Hosteins, R. Cordone, G. Righini. - In: ELECTRONIC NOTES IN DISCRETE MATHEMATICS. - ISSN 1571-0653. - 55:(2016 Nov), pp. 57-60. [10.1016/j.endm.2016.10.015]
The Prize-collecting Scheduling Problem with Deadlines
R. CordoneSecondo
;G. RighiniUltimo
2016
Abstract
We study a prize-collecting single machine scheduling problem with hard deadlines, where the objective is to minimise the difference between the total tardiness and the total prize of selected jobs. This problem is motivated by industrial applications, both as a standalone model and as a pricing problem for column generation approaches to parallel machine scheduling problems. It is handled through the use of exact approaches, in the form of a Branch and Bound (B&B) algorithm and an Integer Linear Programming (ILP) formulation. The B&B and ILP formulation are compared in their efficiency on randomly generated benchmark instances.
| File | Dimensione | Formato | |
|---|---|---|---|
|
ElectronicNotesDiscreteMathematic_PrizeCollectingScheduling_2016.pdf
accesso riservato
Tipologia:
Publisher's version/PDF
Dimensione
156.99 kB
Formato
Adobe PDF
|
156.99 kB | Adobe PDF | Visualizza/Apri Richiedi una copia |
Pubblicazioni consigliate
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
