Contraintes et objectifs de l’ordonnancement

Les contraintes expriment des restrictions sur les valeurs que peuvent prendre simultanément les variables de décision. On distingue :

* des contraintes temporelles
- Les contraintes de temps alloué, issues généralement d'impératifs de gestion et relatives aux dates limites des tâches (délais de livraisons, disponibilité des approvisionnements) ou à la durée totale d'un projet ;
- Les contraintes de cohérence technologique, ou contraintes de gammes, qui décrivent des relations d'ordre relatif entre les différentes tâches ;

* des contraintes de ressources
- Les contraintes d'utilisation de ressources qui expriment la nature et la quantité des moyens utilisés par les tâches, ainsi que les caractéristiques d'utilisation de ces moyens ;
- Les contraintes de disponibilité des ressources qui précisent la nature et la quantité des moyens disponibles au cours du temps. Toutes ces contraintes peuvent être formalisées sur la base des distances entre débuts de tâches ­ ou potentiels.

Dans la résolution d'un problème d'ordonnancement, on peut choisir entre deux grands types de stratégies, visant respectivement à l'optimalité des solutions, ou plus simplement à leur admissibilité.

L'approche par optimisation suppose que les solutions candidates à un problème puissent être ordonnées de manière rationnelle selon un ou plusieurs critères d'évaluation numériques, construits sur la base d'indicateurs de performances. On cherchera donc à minimiser ou maximiser de tels critères. On note par exemple ceux

* liés au temps :
- Le temps total d'exécution ou le temps moyen d'achèvement d'un ensemble de tâches
- Le stock d'en-cours de traitement
- Différents retards (maximum, moyen, somme, nombre, etc.) ou avances par rapport aux dates limites fixées ;

* liés aux ressources :
- La quantité ­ totale ou pondérée ­ de ressources nécessaires pour réaliser un ensemble de tâches
- La charge de chaque ressource ;
- Liés à une énergie ou un débit ;
- Liés aux coûts de lancement, de production, de transport, etc., mais aussi aux revenus, aux retours d'investissements.

* Réseau PERT
* Problème d'ordonnancement d'atelier
          o Job-shop
          o Flow-shop
          o Open-shop
* Problème d'ordonnancement dans les systèmes d'exploitation