PhD graduated
Team : ALSOC
Departure date : 11/30/2022

Supervision : Alix MUNIER

Fixed parameter tractibility of UET-UCT scheduling problems

This problem considers the minimization of the makespan and the maximum lateness for a set of dependent tasks with unit duration, unit communication delays release times and due dates. Each task requires one processor for its execution and duplication is not allowed. Algorithms are given for scheduling on limited and unlimited number of processors. Time windows of tasks are built from upper bounds of the makespan and the minimum maximum lateness respectively. A fixed-parameter algorithm based on a dynamic programming approach is developed to solve this optimization problem. The parameter considered is the pathwidth of the associated interval graph. They are, as far as we know, the first fixed-parameter algorithms for a scheduling problem with communication delays and a limited number of processors.

Defence : 11/28/2022

Departure date : 11/30/2022

2020-2022 Publications