Problème de planification et d’ordonnancement
La planification et l’ordonnancement automatisés concernent la réalisation de stratégies ou de séquences d’actions. La planification moderne, même au sein de l’IA, reflète de plus en plus l’intégration de la théorie et des techniques algorithmiques haute performance de la recherche opérationnelle depuis au moins les années 1950.
Introduction aux problèmes de planification
La planification est l’organisation de la réalisation d’objectifs dans un domaine précis, avec différents moyens, et sur une durée/hiérarchie. Le résultat de ce problème est un « plan » répondant de façon détaillée sur les questions du type QQOQCC : qui, quoi, où, quand, comment et combien.
Le problème de planification permet, selon les conditions et les informations, de répondre aux questions suivantes :
- Comment gérer l’enchaînement logique des tâches et les répartir dans le temps ?
- Comment analyser les charges de travail demandées aux ressources ou moyens s’ils sont limités ?
- Comment exprimer un besoin en ressources ou moyens s’ils ne sont pas limités ?
- Comment prendre en compte des contraintes extérieures au projet (commande client, livraison fournisseur, etc.) ?
- Comment analyser les conséquences d’un écart entre évènements réels et prévus ?
- Comment identifier des dates de début au plus tard, ou de fin au plus tôt, des activités ?
- Comment simuler des hypothèses optimistes, pessimistes, ou la plus probable ?
- Comment analyser l’impact d’un aléa ou d’un risque s’il se transformait en problème ?
- Comment prioriser les tâches ?
Le problème d’affectation est lié à de nombreux autres problèmes de la recherche opérationnelle (réduction de problèmes dans les 21 problèmes de Karp par exemple). Nous verrons ici deux sous-problèmes fréquemment rencontrés dans les problèmes d’affectation.
Sous-problème : l’ordonnancement
Le problème d’ordonnancement est un problème de planification de tâche dans lequel il s’agit de décider de l’ordre dans lequel les tâches doivent être exécutées. Ce problème est Np-difficile compte tenu de la variété et la complexité de ses contraintes.
Les différentes méthodes présentées dans ce cours permettent de faire apparaître clairement et rapidement les données liées à la réalisation d’un plan, telles que :
- les temps, les délais
- les moyens, ou ressources
- les coûts.
Le problème d’ordonnancement classique est le suivant :
Sous-problème : l’affectation
Ce problème consiste à attribuer au mieux des tâches à des agents. Chaque agent peut réaliser une unique tâche pour un coût donné et chaque tâche doit être réalisée par un unique agent. Les affectations (c’est-à-dire les couples agent-tâche) ont toutes un coût défini, le but étant de minimiser le coût total des affectations afin de réaliser toutes les tâches. Ce problème se résout en temps polynomiale.
Sous-problème : le transport
A l’instar des deux précédents problèmes, le problème de transport est une maximisation. Le problème de transport est l’une des sous-classes de problèmes de programmation linéaire où l’objectif est de transporter diverses quantités d’un seul produit homogène qui sont initialement stockées à diverses origines, vers des destinations différentes de telle sorte que le transport total soit minimal.
Soit ai la quantité de la marchandise disponible à l’origine i; bj soit la quantité de produit nécessaire à la destination j; cij le coût de transport d’une unité d’une marchandise de l’origine i à la destination j; et xij est la quantité transportée de l’origine i à la destination j.
Le problème est le suivant :
Si la somme des sources est égale à la somme des demandes, le problème est dit équilibré, dans ce cas les contraintes deviennent des égalités. Dans le cas contraire, on crée un point de demande virtuelle (dummy en anglais) correspondant à l’offre excédentaire et avec un coût de transport nul.
Le problème de transport est souvent représenté comme un graphe biparti avec un problème de flot (couplage). Nous montrerons ici d’autres variantes permettant de résoudre ce problème.
