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 modifier

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 modifier

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 $T_{1},T_{2},\dots T_{p}$ ;
Chaque tâche a une date limite ; ce sont respectivement $D_{1},D_{2},\dots D_{p}$ ;
Des pénalités sont infligées en cas de dépassement ; ce sont $P_{1},P_{2},\dots P_{p}$

Un séquençage de tâches est une permutation $Q=\{q_{1},q_{2},\dots q_{p}\}$ de $\{1,2,\dots p\}$ ; 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

T^{(n)}=\sum _{i=1}^{n}T_{q_{i}}

.

Il y a application de la pénalité pour dépassement si, quand la tâche $q_{n}$ dans cette permutation est achevée, la date limite $D_{q_{n}}$ est dépassée :

P^{(n)}=P_{q_{n}}

si

T^{(n)}>D_{q_{n}}

, et 0 sinon.

Pour un entier k donné, le problème de décision est le suivant :

Existe-t-il une permutation $Q=\{q_{1},q_{2},\dots q_{p}\}$ de $\{1,2,\dots p\}$ telle que la somme des pénalités ne dépasse pas k, donc telle que

\sum _{n=1}^{p}P^{(n)}\leq k

?

NP-complétude modifier

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 modifier

↑ ^{a et b} Karp 1972.

Bibliographie modifier

P. Lopez et F. Roubellat, Ordonnancement de la production, Hermes Science Europe, 2001
(en) Richard M. Karp, « Reducibility Among Combinatorial Problems », dans Raymond E. Miller et James W. Thatcher, Complexity of Computer Computations, Plenum, 1972 (ISBN 978-1-4684-2003-6, DOI 10.1007/978-1-4684-2001-2_9, lire en ligne), p. 85-103

Voir aussi modifier

[karp72-1] {a et b} Karp 1972.

[1]