Les centres d’appels téléphoniques occupent une place indéniable dans notre société autant pour obtenir du support que faire des achats ou des ventes à distance. Suivant l’évolution de la technologie, l’opération de ces centres s’est complexifiée: plusieurs types d’appels entrants et/ou sortants, la polyvalence des agents à servir plusieurs types d’appels et des politiques de routage par compétence. Avec l’essor de l’ère des services, les opportunités de percée dans ce domaine présentent un intérêt croissant pour l’industrie.
Dans ce mémoire, nous avons développé des méthodes heuristiques d’optimisation stochastique pour minimiser le coût d’affectation des agents pour une période, soit une simplification au problème de conception d’horaires. À la différence des problèmes présentés dans la littérature, nous nous intéressons au cas où un gestionnaire ne peut pas modifier les politiques de routage et doit assurer un seuil minimal de qualité de service pour chaque type d’appel ainsi que pour tout le centre.
La méthode d’optimisation par coupes linéaires et simulations repose sur la géné- ration de sous-gradients calculés à l’aide d’un simulateur. Partant d’une solution irréalisable, des coupes sont ajoutées jusqu’à l’obtention d’une solution réalisable. Les instances du problème linéaire sont résolues grâce à des solutionneurs externes.
La recherche randomisée par voisinage est une méthode de descente par des mouvements aléatoires dans le domaine des solutions réalisables. Vu le nombre élevé d’évaluations des voisins, nous avons conçu un modèle d’approximation analytique de perte et délai basé sur les formules de chaînes de Markov en temps continu.
Selon nos comparaisons empiriques avec différents exemples, la performance de nos algorithmes était compétitive. Nous présentons également des analyses de sensibilité par rapport à différents paramètres de chaque méthode, ainsi que quelques variations de nos algorithmes.
Mots clés: méthodes heuristiques, programmation linéaire, recherche randomisée par voisinage.