Direction de recherche : Alix MUNIER

Etude de cas d'un problème d'ordonnancement pour l'automobile

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.

Publications 2020-2022