Séquençage de tâches

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

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

${\displaystyle 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 ${\displaystyle q_{n}}$ dans cette permutation est achevée, la date limite ${\displaystyle D_{q_{n}}}$ est dépassée :

${\displaystyle P^{(n)}=P_{q_{n}}}$ si ${\displaystyle 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 ${\displaystyle Q=\{q_{1},q_{2},\dots q_{p}\}}$ de ${\displaystyle \{1,2,\dots p\}}$ telle que la somme des pénalités ne dépasse pas k, donc telle que

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

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.

• 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

• Liste de problèmes NP-complets
• Raffinement de partition

• Portail de l'informatique théorique
• Portail des mathématiques