Back to activities
GERAD seminar

Fixed-Parameter Tractability of Scheduling Dependent Tasks on m machines subject to Release Times and Deadlines


Sep 20, 2023   11:00 AM — 12:00 PM

Alix Munier-Kordon Université Paris 6, France

Alix Munier

Presentation on YouTube.

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 (\(r_i,d_i\)) for each job \(i\). The problem is denoted by \(P|prec,r_i,d_i|*\).

Several parameters are considered: the path width \(pw(I)\) of the interval graph associated to the time intervals (\(r_i, d_i\)), the maximum processing time of a task \(p_{\max}\) and the maximum slack of a task \(s_{\max}\). 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(p_{\max},s_{\max})\). 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,r_i,d_i| C_{\max}\) and \(P|prec,r_i\vert L_{\max}\) are then derived using a binary search.

(en collaboration avec Claire Hanen)

Djamal Rebaïne organizer


Hybrid activity at GERAD
Zoom et salle 4488
Pavillon André-Aisenstadt
Campus de l'Université de Montréal
2920, chemin de la Tour

Montréal Québec H3T 1J4