Calendrier

Séminaire du GERAD : Fixed-Parameter Tractability of Scheduling Dependent Tasks on m machines subject to Release Times and Deadlines

Séminaire du GERAD : Fixed-Parameter Tractability of Scheduling Dependent Tasks on m machines subject to Release Times and Deadlines
Séminaire du GERAD

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

20 sept. 2023   11h00 — 12h00

Alix Munier-Kordon Université Paris 6, France

Séminaire en format hybride au local 4488 du GERAD ou Zoom.

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)

Date

Wednesday September 20, 2023
Starts at 11:00

Price

gratuit

Contact

Place

Séminaire hybride au 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
Canada

Categories