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.

2020-2022 Publications

• 2022
  • N. Tang : “Etude de cas d’un problème d’ordonnancement pour l’automobile”, thesis, phd defence 11/28/2022, supervision Munier, Alix (2022)
  • A. Munier‑Kordon, N. Tang : “A fixed-parameter algorithm for a unit-execution-time unit-communication-time tasks scheduling problem with a limited number of identical processors”, RAIRO - Operations Research, vol. 56 (5), pp. 3777-3788, (EDP Sciences) (2022)
• 2021
  • N. Tang, A. Kordon : “A Fixed-Parameter Algorithm for Scheduling Unit dependent Tasks with Unit Communication Delays”, Euro-Par 2021 - 27^th International European Conference on Parallel and Distributed Computing, vol. 12820, Lecture Notes in Computer Science, Lisbon, Portugal, pp. 105-119, (Springer, Cham) (2021)
• 2020
  • A. Kordon, N. Tang : “Evaluation of the Age Latency of a Real-Time Communicating System using the LET paradigm”, ECRTS 2020, vol. 165, Leibniz International Proceedings in Informatics (LIPIcs), Modena, Italy, (Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik) (2020)