Planification des tâches de calcul et de communication par lots : base théorique et conception d’algorithmes

Dans cette thèse, nous formulons et analysons une classe de problèmes fondamentaux d'ordonnancement de tâches découlant d'une variété de systèmes informatiques et de communication émergents: les tâches sont divisées en groupes; ceux d'un groupe peuvent être regroupés et exécutés simultanément; le but de l'ordonnanceur est de concevoir des algorithmes d'ordonnancement maximisant l'utilité globale du système. Sous le parapluie générique ci-dessus, nous étudions différentes classes de problèmes de planification de tâches de traitement par lots, établissant le cadre théorique correspondant, concevant des algorithmes de planification à la fois hors ligne et en ligne et illustrant leur application dans la planification des tâches de communication et de calcul. Nous commençons par le scénario de base de la planification des tâches de traitement par lots. Il existe un ensemble de tâches à exécuter sur un certain nombre de machines. Certaines tâches peuvent être exécutées simultanément sur une seule machine, tandis que d'autres nécessitent l'utilisation exclusive d'une machine entière. Nous recherchons une politique de planification optimale pour maximiser l'utilité globale du système. Nous développons un cadre algorithmique pour le problème d'ordonnancement ci-dessus sous la forme générique qui peut atteindre 1/2-optimalité, surpassant le meilleur résultat connu. Le cœur technique de notre conception est un mécanisme de relaxation LP adapté et une approche d'arrondi et de coloration qui transforme la solution de la relaxation LP en une politique d'ordonnancement réalisable 1/2-optimale. Nous démontrons ensuite l'application de notre cadre algorithmique pour résoudre le problème généralisé de diffusion proportionnelle en développant un algorithme d'approximation déterministe produisant une politique d'ordonnancement optimale l_min / (2 (l_min + 1)), alors qu'il n'existe que des algorithmes aléatoires dans la littérature. Nous formulons et analysons ensuite un problème fondamental d'ordonnancement de transmission en liaison descendante dans les systèmes de communication sans fil, composés d'une station de base et d'un ensemble d'utilisateurs, chacun demandant qu'un paquet soit servi dans une fenêtre temporelle. Certains paquets sont demandés par plusieurs utilisateurs et peuvent être servis simultanément en raison de la nature de diffusion du support sans fil. Par rapport au modèle de base, il existe deux particularités. Premièrement, chaque demande peut être servie par un sous-ensemble de stratégies de transmission. Deuxièmement, les demandes doivent être servies selon la méthode FIFO. Nous recherchons un algorithme de planification de transmission de liaison descendante maximisant l'utilité globale du système. Nous développons un cadre algorithmique du problème de planification de transmission de données de liaison descendante formulé dans les paramètres hors ligne et en ligne. Nous établissons d'abord sa dureté, puis développons des algorithmes d'approximation avec une garantie de performance mathématiquement prouvée en termes d'approximation et de ratios compétitifs pour les paramètres hors ligne et en ligne, respectivement. La troisième contribution de cette thèse concerne l'ordonnancement des tâches de batching de ressources contiguës. Un ensemble de tâches doit être exécuté sur un pool de ressources continues, chacune nécessitant un certain temps et une ressource contiguë; certaines tâches peuvent être exécutées simultanément par lots en partageant la ressource, tandis que d'autres nécessitent une utilisation exclusive de la ressource; les tâches sont servies à la manière FIFO. Nous recherchons une allocation optimale des ressources et la politique de planification associée maximisant l'utilité globale du système. Nous fournissons une analyse algorithmique complète du problème en établissant sa dureté et en développant des algorithmes de planification d'approximation pour les paramètres hors ligne et en ligne.In this thesis we formulate and analyze a class of fundamental task scheduling problems arising from a variety of emerging computing and communication systems: tasks are partitioned into groups; those in a group can be batched and executed simultaneously; the goal faced by the scheduler is to design scheduling algorithms maximizing the overall system utility. Under the above generic umbrella, we investigate different classes of batching task scheduling problems, establishing the corresponding theoretical framework, designing both offline and online scheduling algorithms, and illustrating their application in scheduling communication and computing tasks. We start by the baseline scenario of batching task scheduling. There is a set of tasks to be executed on a number of machines. Some tasks can be executed simultaneously on a single machine, while others require exclusive use of an entire machine. We seek an optimal scheduling policy to maximize the overall system utility. We develop an algorithmic framework for the above scheduling problem in the generic form that can achieve 1/2-optimality, outperforming the best known result. The core technicality in our design is an adapted LP relaxation mechanism and a rounding and coloring approach that turns the solution of the LP relaxation to a 1/2-optimal feasible scheduling policy. We then demonstrate the application of our algorithmic framework to solve the generalized proportional broadcast problem by developing a deterministic approximation algorithm outputting an l_min/(2(l_min+1))-optimal scheduling policy, while there exist only randomized algorithms in the literature. We then formulate and analyze a fundamental downlink transmission scheduling problem in wireless communication systems, composed of a base station and a set of users, each requesting a packet to be served within a time window. Some packets are requested by several users and can be served simultaneously due to the broadcast nature of the wireless medium. Compared to the baseline model, there are two particularities. First, each request can be served by a subset of transmission strategies. Second, requests need to be served in the FIFO manner. We seek a downlink transmission scheduling algorithm maximizing the overall system utility. We develop an algorithmic framework of the formulated downlink data transmission scheduling problem in both offline and online settings. We first establish its hardness, and then develop approximation algorithms with mathematically proven performance guarantee in terms of approximation and competitive ratios for the offline and online settings, respectively. The third contribution of this thesis concerns the contiguous-resource batching task scheduling. A set of tasks need to be executed on a pool of continuous resource, each requiring a certain amount of time and contiguous resource; some tasks can be executed simultaneously in batch by sharing the resource, while others requiring exclusive use of the resource; tasks are served in the FIFO manner. We seek an optimal resource allocation and the related scheduling policy maximizing the overall system utility. We deliver a comprehensive algorithmic analysis on the problem by establishing its hardness and developing approximation scheduling algorithms for both offline and online settings