A Branch-and-Bound Algorithm for the Prize-Collecting Single-Machine Scheduling Problem with Deadlines and Total Tardiness Minimization
Roberto Cordone (),
Pierre Hosteins () and
Giovanni Righini ()
Additional contact information
Roberto Cordone: Dipartimento di Informatica, Università degli Studi di Milano, 26013 Crema, Italy
Pierre Hosteins: Computer Science Department, University of Turin, I-10149 Torino, Italy
Giovanni Righini: Dipartimento di Informatica, Università degli Studi di Milano, 26013 Crema, Italy
INFORMS Journal on Computing, 2018, vol. 30, issue 1, 168-180
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.
Keywords: prize-collecting; single-machine scheduling; integer linear programming; branch and bound (search for similar items in EconPapers)
Date: 2018
References: View references in EconPapers View complete reference list from CitEc
Citations:
Downloads: (external link)
https://doi.org/10.1287/ijoc.2017.0772 (application/pdf)
Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.
Export reference: BibTeX
RIS (EndNote, ProCite, RefMan)
HTML/Text
Persistent link: https://EconPapers.repec.org/RePEc:inm:orijoc:v:30:y:2018:i:1:p:168-180
Access Statistics for this article
More articles in INFORMS Journal on Computing from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().