Ordonnancement avec sélection et coûts de setup: les problèmes de base.

Jie Meng-Gérard (LIP6, Paris)


Nous étudions des problèmes d'ordonnancements classiques avec des jobs $J_i$
(1 machine ou $m$ machines parallèles, avec fenêtres de temps $[r_i,d_i]$,
durées $p_i$ unitaires ou quelconques, précédences, etc..)
sauf que nous y ajoutons de la sélection et des coûts de setup.

	La sélection consiste à dire qu'on ne va pas exécuter tous les jobs
mais seulement ceux qui nous intéressent au sens d'un gain.
Plus formellement, la sélection revient à décider pour chaque job $J_i$
s'il va être exécuté ou non et à quel moment sachant que l'exécution d'un job $J_i$
génère un gain $g_i$ ou $g_{it}$ si ce gain dépend aussi de la date d'exécution $t$.

	Les coûts de setup sont des coûts associés à un slot de temps précis
sur une ligne de temps discrétisée, souvent des coûts de préparation,
de chargement, de lancement ou de location associés à un jour ou une heure.
Plus formellement, le coût de setup est un coût $K_t$ qu'il faut payer si
au moins une machine est utilisée entre $t-1$ et $t$.
A noter qu'on paie le même coût de setup, une seule fois,
que ce soit pour l'utilisation d'une machine ou de $m$ machines. 

	Dans ce type d'ordonnancement, le critère à optimiser n'est plus lié au temps
comme le makespan ou la somme des retards mais plus directement lié à un gain ou un coût,
généralement en argent. Par exemple le gain d'un ordonnancement peut être la somme des gains
moins la somme des coûts de setup (pour les jobs exécutés et les slots utilisés).

	Nous présenterons quelques problèmes basiques d'ordonnancement
pour lesquels nous avons introduit de la sélection et/ou des coûts de setup.
Nous verrons ainsi les problèmes concrets que cela permet de modéliser.
Nous traitons des cas polynomiaux et identifions certains cas NP-Difficiles.