


Walsh \cite{walsh_stochastic_2002} propose une extension de la programmation par constaintes en ajoutant des variables stochastiques au modèle en plus des variables de décision. Il spécifie une procédure qui permet de résoudre un problème de satisfiabilité en une ou plusieurs étapes, suivant l'ordre séquentiel des évènements ou une séquence de dépendances. On remarquera que cette approche est utilisée avec deux étapes dans les deux autres articles revisés, mais sans nécessairement utiliser des contraintes stochastiques. Le concept de décision (policy) est défini comme un arbre contenant un support pour les variables de domaine au haut de l'arbre et toutes les valeurs possibles des variables stochastiques, avec leur probabilité de réalisation, au bas de l'arbre. Une valeur binaire définissant si cette branche satisfait toutes les contraintes est associée à chaque feuille. On définit la mesure de satisfiabilité comme étant la somme des valeurs des feuilles, multipliée par leur probabilité. et la valeur espérée comme étant le produit de l'évaluation d'une fonction objectif pour chaque branche, multipliée par la probabilité de réalisation. Enfin, un algorithme de retour arrière et de vérification anticipée est proposé, incluant une méthode pour filtrer les variables stochastiques. Cet article constitue les fondements d'une approche qui ne semble pas avoir été tant reprise telle quelle par la suite, dans les problèmes de conception d'horaires de travail que nous explorons, probablement pour sa complexité. Parmi plusieurs extensions proposées, on peut noter l'ajout de dépendance entre les variables stochastiques, de nouveaux types de fonctions d'optimisation et l'ajout de contraintes facultatives ou dont la présence dans le problème est aléatoire.

%%% Local Variables:
%%% mode: latex
%%% TeX-master: "revue_litterature"
%%% End:
