Ordonnancement de production: algorithmes et complexité

点击翻译按钮获取中文摘要

La problématique de la théorie de l'ordonnancement concerne les problèmes d'allocation, dans le temps, d'un ensemble limité de ressources (machines) par un ensemble de tâches. Sa popularité vient du fait qu'une multitude de situations, rencontrées dans la pratique des entreprises et organisations, peuvent être ramenées à cette problématique. Cela est dû, en grande partie, à la richesse de l'interprétation que peuvent avoir les termes ressources et tâches. Nous pouvons citer, entre autres, des applications dans l'industrie (réalisation de produits sur des machines), l'administration (confection d'horaires), la santé (consultations de patients), la construction (réalisation de projets), l'informatique (exécution de processus). Ce présent programme de recherche est une continuation du précédent programme de recherche. Nous nous intéressons en fait à l'ordonnancement de n tâches sur m machines dans un environnement d'atelier. Il est utile de signaler qu'il existe trois modèles de base pour décrire ces problèmes, à savoir les modèles à cheminement libre (open shop), à cheminement unique (flow shop) et à cheminement multiple (job shop). Remarquons qu'il existe également un autre modèle à machines parallèles: chaque tâche ne requiert qu'une seule des machines pour son exécution. Les modèles d'ordonnancement d'ateliers étudiés dans la littérature ne reflètent pas toujours les problèmes rencontrés dans la pratique. Dans ce présent programme de recherche, pour rendre les différents modèles cités ci-dessus plus proches de la réalité et en proposer des solutions efficaces, nous continuons à mener des investigations sur l'effet induit par les temps de latence des tâches générés entre-autres par leurs déplacements à travers les ressources, des relations de précédence entre les tâches (dans ce cas, le début d'exécution d'une tâche est conditionné par la fin d'exécution de ses prédécesseurs) et de la multiplication de certaines machines mises en parallèle dans le but d'éviter les goulots d'étranglement dans l'atelier.