Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?
Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur Graph Search.
Concept
Séquençage de tâches
Résumé
Le séquençage de tâches (en anglais job sequencing) est un des nombreux modèles d'ordonnancement d'atelier de production. En informatique théorique, et notamment en complexité des algorithmes, c'est la formulation d'un problème particulier d'ordonnancement considéré par Richard Karp dans sa célèbre description des 21 problèmes NP-complets.
Les modèles d'ordonnancement font intervenir des tâches fractionnables ou non, chacune ayant une certaine durée d'exécution, des ressources qui sont des machines travaillant en séquence ou en parallèle, des contraintes qui peuvent être d'antériorité (une tâche doit s'exécuter avant une autre) ou des contraintes de ressources.
Une classification très répandue des ateliers, du point de vue ordonnancement, est basée sur les différentes configurations des machines. Les modèles les plus connus sont ceux d’une machine unique, de machines parallèles, d’un atelier à cheminement unique (flow-shop) ou d’un atelier à cheminement multiple (job-shop).
Le séquençage de tâches considéré ici est le plus simple, d'une machine unique, mais avec des contraintes sur les temps d'exécution : on veut exécuter les tâches dans un certain ordre pour minimiser des pénalités de dépassement qui sont infligées chaque fois qu'après l'exécution d'une tâche, une date limite est dépassée.
On peut formuler le problème comme un problème de décision, ou comme un problème d'optimisation.
Dans la formulation comme problème de décision, il s'énonce comme suit : On se donne p tâches, numérotées de 1 à p , avec les caractéristiques suivantes
Les tâches ont des durées d'exécution des tâches, données respectivement par des entiers ;
Chaque tâche a une date limite ; ce sont respectivement ;
Des pénalités sont infligées en cas de dépassement ; ce sont
Un séquençage de tâches est une permutation de ; les tâches sont exécutées dans cet ordre ; le moment où la n-ième tâche de la séquence est terminée est
Il y a application de la pénalité pour dépassement si, quand la tâche dans cette permutation est achevée, la date limite est dépassée :
si , et 0 sinon.
Source officielle
À propos de ce résultat
Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.