Scheduling with tails and deadlines

Scheduling with tails and deadlines

0.00 Avg rating0 Votes
Article ID: iaor20021713
Country: United Kingdom
Volume: 4
Issue: 2
Start Page Number: 105
End Page Number: 121
Publication Date: Mar 2001
Journal: Journal of Scheduling
Authors: ,
Abstract:

This paper discusses scheduling problems that combine tails and deadlines or, equivalently, due dates and deadlines. This approach is illustrated to be of practical interest to strengthen some lower bounds in shop scheduling problems. We show that both deadlines and tails can efficiently be modelled via a non-decreasing cost function of the completion time so that we can use the O(n2 ) algorithm due to Baker, Lawler, Lenstra and Rinnooy Kan for the 1|pmtn,prec,rj,|fmax problem to solve 1|pmtn,prec,rj,dj,qj|Cmax. For this problem, we present an algorithm with improved complexity of O(e + n log n) where e is the number of precedence constraints and we present some extensions of this algorithm to solve two parallel machine problems with unit execution time operations.

Reviews

Required fields are marked *. Your email address will not be published.