Fixed-Parameter Tractability of Scheduling Dependent Tasks on m machines subject to Release Times and Deadlines
Alix Munier-Kordon – Université Paris 6, France
Scheduling problems involving a set of dependent tasks with release dates and deadlines on a limited number of resources have been intensively studied. However, few parameterized complexity results exist for these problems.
The problem considered in this talk is the existence of a feasible schedule on m
identical machines with precedence constraints and time intervals (ri,di
) for each job i
. The problem is denoted by P|prec,ri,di|∗
.
Several parameters are considered: the path width pw(I)
of the interval graph associated to the time intervals (ri,di
), the maximum processing time of a task pmax
and the maximum slack of a task smax
. We established that the problem is para-NP-complete with respect to any of these parameters. We then provide a fixed-parameter algorithm for the problem parameterized by both
parameters pw(I)
and min(pmax,smax)
. It is based on a dynamic programming approach that builds a levelled
graph which longest paths represent all the feasible solutions. Fixed-parameter algorithms for the problems P|prec,ri,di|Cmax
and P|prec,ri|Lmax
are then derived using a binary search.
(en collaboration avec Claire Hanen)

Location
Pavillon André-Aisenstadt
Campus de l'Université de Montréal
2920, chemin de la Tour
Montréal Québec H3T 1J4
Canada