<  Back to the Polytechnique Montréal portal

Méthodes d'optimisation pour un problème stochastique d'horaire d'audiences judiciaires

Vincent Martin-Gauthier

Masters thesis (2013)

[img]
Preview
Download (664kB)
Cite this document: Martin-Gauthier, V. (2013). Méthodes d'optimisation pour un problème stochastique d'horaire d'audiences judiciaires (Masters thesis, Polytechnique Montréal). Retrieved from https://publications.polymtl.ca/1104/
Show abstract Hide abstract

Abstract

RÉSUMÉ : Ce mémoire s'intéresse à la problématique de l'élaboration des rôles dans un palais de justice de grande taille. Ce contexte est défini sous la forme du problème stochastique d'horaire d'audience judiciaires, qui se rattache à la famille des problèmes d'horaire. Cette formulation se distingue par la présence d'évènements (les procès) présentant une incerti-tude sur leur durée, ce qui permet des stratégies de surplanification pour favoriser la mini-misation des délais juridiques et une bonne utilisation des capacités. Les objectifs de la recherche rapportée sont de présenter un modèle mathématique en lien avec la littérature scientifique et les contraintes particulières du domaine judiciaire. La résolution proposée doit réussir à incorporer des éléments stochastiques pour rendre compte de l'incertitude sur la durée des procès. Cette dernière est expérimentée sur des jeux de données élaborés en collaboration avec le service des rôles du palais de justice de Montréal. Inspirée des problèmes d'horaire, deux formulations sont proposées en vue de per-mettre la minimisation des délais juridiques tout en imposant une tolérance maximale sur la probabilité d'encombrement du rôle. Un seuil limite le nombre de causes pouvant avoir une probabilité non nulle de procéder dans une période et un type de salle donné. Les solutions entières obtenues par énumération implicite avec ce seuil subissent une évaluation stochastique pour déterminer la probabilité que le nombre de procès ayant lieu surpasse le nombre de salles disponibles. Des coupes sont ajoutées en cours de résolution lorsqu'une solution présente des périodes pour lesquelles la probabilité d'encombrement dépasse la tolérance de risque désirée. Les résultats obtenus démontrent que l'utilisation de différentes méthodes d'évalua-tion des probabilités selon la taille des ensembles de procès permet de résoudre plus rapi-dement le problème d'optimisation posé que le recours à une seule méthode. Il est égale-ment établi qu'une résolution alliant un calcul exact des probabilités, une simulation de Monte-Carlo et une approximation par la loi normale parvient à produire des horaires de meilleure qualité et comportant moins de risque qu'une assignation séquentielle des causes proche de la pratique actuelle de faire dans le domaine judiciaire. Le problème stochastique d'horaire d'audiences judiciaires qui est proposé est l'un des rares problèmes d'horaire considérant l'incertitude sur la durée des évènements. Sa résolution présente également l'intérêt de linéariser des contraintes aléatoires par l'intégration dynamique de plans coupants amenant l'obtention de solutions réalisables. Les résul-tats obtenus suggèrent que l'administration québécoise de la justice pourrait bénéficier de l'élaboration mathématique des rôles pour optimiser l'utilisation de ses ressources et réaliser des gains de temps pour les justiciables.----------ABSTRACT : This master's thesis tackles the issue of roll making in a high-sized courthouse. This context is formalised as the judiciary hearing stochastic timetabling problem, subtype of the general timetabling problem class. This problem features events of uncertain duration, pav-ing way to overbooking strategies seeking to minimise justice lead time and an appropriate use of ressources. The main objective of the research shown is to present a mathematical model taking into account context-specific constraints while keeping in line with the state-of-the-art in timetabling. The solving proccess reported aims to use stochastic means to achieve a proper consideration of the uncertainty on trial length. Experimentation has been conducted using data obtained from the management of rolls of the Montréal courthouse. Based on timetabling problems, two models are presented for optimising justice lead time while enforcing a maximum risk tolerance on the overcrowded roll probability. First, for any given period and courtroom type, the number of trial taking place with an actual probability is capped. Integer solutions founded by an branch-and-bound algorithm subject to this cap are tested by a stochastic method asserting the probability of having a greater number of trials than corresponding courtrooms for any given period. Cuts are added during the solving process when a integer solution exceeds the tolerated risk probability on one period (or more) for any courtroom type. Testing results indicates that multiple probability evaluation methods in the same solving process can lead to lower computation times than a singe-method solving. Further-more, while using exact probability computation, Monte-Carlo simulation and approximation by the normal law, solving the judiciary hearing stochastic timetabling problem produces better solutions implying lower risk and justice lead times than sequential assignment methods close to the actual roll management procedure. The proposed judiciary hearing stochastic timetabling problem is one of the few timetabling problem dealing with events of uncertain duration. The solving process pre-sented achieve linearisation of chance constraints by dynamically adding cutting planes leading to feasible solutions. Results also support the idea that Québec justice administration would benefit implementing a mathematical roll-making process by less lead times and a more consistent use of ressources.

Open Access document in PolyPublie
Department: Département de mathématiques et de génie industriel
Dissertation/thesis director: Guy Desaulniers, Alain Hertz and Richard Labib
Date Deposited: 16 Jul 2013 16:26
Last Modified: 24 Oct 2018 16:11
PolyPublie URL: https://publications.polymtl.ca/1104/

Statistics

Total downloads

Downloads per month in the last year

Origin of downloads

Repository Staff Only