Résumé | Le problème de routage et d’affectation de longueurs d’onde est étudié dans un contexte de collaboration où des outils communs sont utilisés simultanément sur un réseau à fibres optiques. Les versions en ligne et hors ligne sont abordées, en prenant ou non le temps comme paramètre d’ordonnancement, et en incluant le cas où le réseau est utilisé pour un trafic multiplexé dans le temps. En outre, on étudie le problème du réordonnancement d’une demande bloquée. Plusieurs solutions fondées sur des programmes linéaires en nombres entiers (ILP) mixtes et sur l’heuristique sont proposées et mises en œuvre, et leurs rendements sont comparés. Le cas hors ligne est résolu au moyen de deux types de programmes linéaires en nombres entiers : des formulations de liens et de trajet. Les programmes linéaires en nombres entiers sont aussi proposés pour résoudre le problème en ligne en plus des algorithmes heuristiques. Bien que les formulations des liens fournissent des solutions optimales, leur résolution exige beaucoup de temps et elles peuvent être utilisées seulement pour de petits problèmes. Les formulations de trajet et heuristiques présentent de meilleurs rendements, mais aux dépens de l’optimalité. La méthode en ligne est recommandée lorsque la taille du problème interdit le recours à une méthode hors ligne. |
---|