Séquençage de tâches
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[1].
Présentation
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.
Formulation
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.
Pour un entier k donné, le problème de décision est le suivant :
Existe-t-il une permutation de telle que la somme des pénalités ne dépasse pas k, donc telle que
- ?
NP-complétude
Karp[1] démontre que ce problème est NP-complet, tout en notant que le problème analogue sans pénalités, et où l'on ne veut pas que plus de k tâches dépassent leur date limite, est polynomial.
Le problème du séquençage, formulé comme problème d'optimisation, demande de minimiser la somme des pénalités en agissant sur la permutation.
Notes et références
Bibliographie
- P. Lopez et F. Roubellat, Ordonnancement de la production, Hermes Science Europe,
- (en) Richard M. Karp, « Reducibility Among Combinatorial Problems », dans Raymond E. Miller et James W. Thatcher, Complexity of Computer Computations, Plenum, (ISBN 978-1-4684-2003-6, DOI 10.1007/978-1-4684-2001-2_9, lire en ligne), p. 85-103
Voir aussi
- Liste de problèmes NP-complets
- Raffinement de partition
v · m | |
---|---|
|
Portail de l'informatique théorique
Portail des mathématiques