Fixed-Parameter Tractability of Scheduling Dependent Tasks on m Machines Subject to Release Times and Deadlines

Explore the fixed-parameter tractability of scheduling dependent tasks on multiple machines with release times and deadlines in this 50-minute seminar from GERAD Research Center. Delve into the parameterized complexity of scheduling problems involving dependent tasks with time constraints on limited resources. Examine the P|prec,ri,di|∗ problem, which focuses on finding feasible schedules for m identical machines with precedence constraints and time intervals. Analyze various parameters including path width of the interval graph, maximum processing time, and maximum slack of tasks. Discover why the problem is para-NP-complete for individual parameters and learn about a fixed-parameter algorithm that utilizes both path width and minimum of maximum processing time or slack. Understand the dynamic programming approach that constructs a levelled graph to represent feasible solutions. Gain insights into derived fixed-parameter algorithms for related problems P|prec,ri,di|Cmax and P|prec,ri|Lmax using binary search techniques.