---
# System prepended metadata

title: Compte-rendu problème d’ordonnancement Prolog

---

#### Paco Pompeani & Maylis de Talhouet 
# Compte-rendu problème d’ordonnancement Prolog

Pour cet exercice, nous étions face à un problème d'ordonnancement. Une machine effectue `n` tâches qui doivent être ordonnancées selon plusieurs contraintes.

## Modélisation

Pour écrire le prédicat `ordonnancement`, nous avons d'abord entré les données du problème afin de pouvoir les manipuler. Nous avons donc créé des variables `TacheI`, correspondant au jour I où la I-ème tâche (de 1 à 5) est exécutée, `DureeI` et `EcheanceI`.

Par la suite, nous avons pû définir nos contraintes.
La première concerne les fins des tâches. Chaque tâche doit finir au plus tard le jour de son échéance. Pour modéliser cette règle, nous avons créé la variable `FinI` et ajouté une contrainte indiquant que `FinI` doit être inférieur ou égal à `EcheanceI` : `FinI #=< EcheanceI`. 

La seconde contrainte importante concerne la succession des tâches. La machine ne peut exécuter qu'une seule tâche à la fois. 
Pour chaque tâche, il faut indiquer que sa borne `FinI` et nécessairement différente du début d'une autre tâche. Cette contrainte est exprimée sur les lignes 42 à 54.

## Méthodes de résolution

Aux lignes 64 à 79, les 3 méthodes sont implémentées. La première méthode (`fd_labeling(Taches)`), renvoie tous les ordonnancements correspondant aux contraintes énoncées si dessus.

Pour aller plus loin, nous voulons minimiser la date de fin. Il faut donc faire appel à `fd_minimize(Obj, X)`. Ce prédicat necessite deux paramètres. Le premier est un prédicat appelé plusieurs fois afin de minimiser la valeur du second paramètre. Ce prédicat utilise un algorithme branch-and-bound, à chaque appel de `Obj` réussi, le prédicat rajoute une contrainte `X #< Y` avec Y le résultat de l'appel de `Obj`. Lorsqu'un échec se produit, la dernière solution est recalculée car elle est optimale.
Nous avons donc appelé ce prédicat avec les dates de début des tâches et `FinFin`. Afin de respecter l'énoncé, nous avons ajouté des contraintes assurant que la variable `FinFin` est toujours supérieur ou égal aux dates de fin = `FinFin #>= FinI`. 

La dernière méthode implémentée renvoie un ordonnancement minimisant la somme des dates de fin. Une fois de plus, nous avons fait appel au prédicat `fd_minimize`. Cette fois-ci, nous avons minimisé une variable `Fin` correspondant à la somme des dates de fin.

On notera que dans cette occurence précise du problème, les deux dernières méthodes donnent le même résultat.