L'échantillonnage équilibré par la méthode du cube et la méthode rejective

Au cours de ces dernières années, les techniques d’échantillonnage équilibré ont connu un regain d’intérêt. En effet, ces techniques permettent de reproduire la structure de la population dans des échantillons afin d’améliorer l’efficacité des estimations. La reproduction de cette structure est effectuée par l’introduction des contraintes aux plans de sondage. Encore récemment, des nouvelles procédures d’échantillonnage équilibré ont été proposées. Il s’agit notamment de la méthode du cube présentée par Deville et Tillé (2004) et de l’algorithme réjectif de Fuller (2009). Alors que la première est une méthode exacte de sélection, la seconde est une approche approximative qui admet une certaine tolérance dans la sélection. Alors, après une brève présentation de ces deux méthodes dans le cadre d’un inventaire de pêcheurs, nous comparons à l’aide de simulations Monte Carlo, les plans de sondage produits par ces deux méthodes. Aussi, cela a été l’occasion pour nous de vérifier si ces méthodes modifient les probabilités de sélection des unités.

Efficient algorithms to solve scheduling problems with a variety of optimization criteria

La programmation par contraintes est une technique puissante pour résoudre, entre autres, des problèmes d’ordonnancement de grande envergure. L’ordonnancement vise à allouer dans le temps des tâches à des ressources. Lors de son exécution, une tâche consomme une ressource à un taux constant. Généralement, on cherche à optimiser une fonction objectif telle la durée totale d’un ordonnancement. Résoudre un problème d’ordonnancement signifie trouver quand chaque tâche doit débuter et quelle ressource doit l’exécuter. La plupart des problèmes d’ordonnancement sont NP-Difficiles. Conséquemment, il n’existe aucun algorithme connu capable de les résoudre en temps polynomial. Cependant, il existe des spécialisations aux problèmes d’ordonnancement qui ne sont pas NP-Complet. Ces problèmes peuvent être résolus en temps polynomial en utilisant des algorithmes qui leur sont propres. Notre objectif est d’explorer ces algorithmes d’ordonnancement dans plusieurs contextes variés. Les techniques de filtrage ont beaucoup évolué dans les dernières années en ordonnancement basé sur les contraintes. La proéminence des algorithmes de filtrage repose sur leur habilité à réduire l’arbre de recherche en excluant les valeurs des domaines qui ne participent pas à des solutions au problème. Nous proposons des améliorations et présentons des algorithmes de filtrage plus efficaces pour résoudre des problèmes classiques d’ordonnancement. De plus, nous présentons des adaptations de techniques de filtrage pour le cas où les tâches peuvent être retardées. Nous considérons aussi différentes propriétés de problèmes industriels et résolvons plus efficacement des problèmes où le critère d’optimisation n’est pas nécessairement le moment où la dernière tâche se termine. Par exemple, nous présentons des algorithmes à temps polynomial pour le cas où la quantité de ressources fluctue dans le temps, ou quand le coût d’exécuter une tâche au temps t dépend de t.