TANG Ning

Dottore di ricerca
Gruppo di ricerca : ALSOC
Data di partenza : 11/30/2022
https://lip6.fr/Ning.Tang

Relatore : 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.

Difesa : 11/28/2022

Data di partenza : 11/30/2022

Pubblicazioni 2020-2022

Mentions légales
Mappa del sito