L'utilisation de la programmation mathématique pour la résolution d'un problème « car-sequencing »

1.3 2.2 La notion de tâche :

Une tâche i est une entité élémentaire localisée dans le temps par une date de début et une date de fin, dont la réalisation nécessite une durée opératoire p_i, et qui consomme un moyen selon une certaine intensité.

Selon le problème, les tâches peuvent êtres exécutées par morceaux on parle alors de problèmes préemptifs et dans ce cas la durée p_i d'une tâche ne peut être déterminée qu'une fois l'ordonnancement est construit ;ou doivent être exécutées sans interruption on parle alors de problèmes non préemptifs.

Lorsque les tâches ne sont soumises à aucune contrainte de cohérence, elles sont dites indépendantes.

1.4 2.3 La notion de ressource :

La ressource est un moyen technique ou humain destiné à être utilisé pour la réalisation d'une tâche et disponible en quantité limitée.

Dans ce contexte on peut distinguer plusieurs types de ressources à savoir :

Une ressource est renouvelable si après avoir été allouée à une ou plusieurs tâches elle est à nouveau disponible en même quantité (les hommes, les machines, l'équipement en général) ; la quantité de ressource utilisable à chaque instant est limitée.

Dans le cas contraire, elle est consommable (matières premières, budget) ; la consommation globale (ou cumul) au cours du temps est limitée.

Une ressource est doublement contrainte lorsque son utilisation instantanée et sa consommation globale sont limitées (l'argent est un bon exemple).

Quelle que soit renouvelable ou consommable, la disponibilité d'une ressource peut varier au cours du temps. Sa courbe de disponibilité est en général connue a priori sauf dans les cas où elle dépend du placement de certaines tâches génératrices.

On distingue par ailleurs  principalement dans le cas des ressources renouvelables  les ressources disjonctives qui ne peuvent exécuter qu'une tâche à la fois (machine-outil, robot manipulateur) et les ressources cumulatives qui peuvent être utilisées par plusieurs tâches simultanément  mais en nombre limité  (équipe d'ouvriers, poste de travail).

1.52.4 Typologie des contraintes :

La notion générique de contrainte est relative à un ensemble de variables de décision, elle exprime une restriction sur les domaines de valeur de variables ; on peut distinguer trois types de contraintes à savoir :

§ Contraintes de type potentiel ;

§ Contraintes de type cumulatif ;

§ Contraintes de type disjonctif ;

1.5.1 Contraintes de type potentiel :

Nous regroupons sous ce vocable les contraintes temporelles qui sont de deux sortes :

ü Contraintes de localisation temporelle : exprime la localisation des tâches dans le temps.

Une tâche i ne peut être débutée avant une date fixée l ; par exemple ; une livraison ou une décision administrative.

t_i = l

ou une tâche i doit être terminée avant une date fixée l ; par exemple ; un engagement commerciale.

t_i = l

ou enfin, une tâche i doit être impérativement terminée à une date fixée l sans avance ni retard .Cette contrainte est la combinaison des deux contraintes précédentes.

t_i = l

t_i = l

ce qui implique : t_i=l

ü Contraintes de succession temporelle :

Elles expriment la relation d'antériorité entre les tâches, une telle tâche ne peut commencer avant la fin d'une autre ; par exemple ; on ne coule pas des fondations si le terrassement n'est pas fini.

Considérons deux tâches i et j dont les époques de début sont respectivement

t_i et t_j .Dire qu'il existe une contrainte de succession entre les tâches i et j consiste à limiter soit inférieurement soit supérieurement l'intervalle de temps qui peut s'écouler entre t_i et t_j, l'intervalle de temps qui sépare t_i et t_j va être donc borné inférieurement par une quantité que nous noterons a, a pour indice i et j pour monter qu'elle est liée au couple ij pris dans cet ordre.

t_j -t_i = a_ij

Les contraintes de type « potentiel » que nous avons définies sont importantes car elles interviennent dans tout problème d'ordonnancement.