The Prize-Collecting Single Machine Problem with Deadlines

Session : SS3-2 / SS3 : Planification de la Production et Lot-Sizing
Mercredi 10 février 15:00 - 16:00 Salle : RP7
Roberto Cordone, Pierre Hosteins et Giovanni Righini

We present the problem of the Prize-collecting Single-Machine scheduling with hard deadlines. A Branch and Bound is developed to deal with the problem, which will be compared to linear models solved by a commercial solver. The problem can be of relevance to problems where not all jobs can be done and a profit is associated with the processing of each job, such as specific situations in the steel industry or in pricing problems of column generation formulations for multi-machine scheduling problems.

Mots clés : prize-collecting, single-machine scheduling, hard deadlines, branch and bound, total tardiness