Thesis--Massachusetts Institute of Technology. / Cover title. Bibliography: p. 181-184.

No description available.

by Poon Wai-hung, Patrick, Chan Mei-ying, Spencer. / Abstract also in Chinese / Bibliography: leaf 91 / Thesis (M.B.A.) -- Chinese University of Hong Kong, 1983

Le Problème de la Somme Coloration Minimum (MSCP) d'un graphe est un problème d'optimisation combinatoire dont l'objectif est de déterminer une coloration valide minimisant la somme des poids associés aux couleurs utilisées. Le nombre minimum de couleurs dans une solution optimale de MSCP est appelé la force du graphe, et la somme des poids des couleurs utilisées est appelée la somme chromatique du graphe. L'objectif de cette thèse a été d'étudier MSCP afin de proposer de nouvelles approches permettant sa résolution. La contribution de cette thèse est double. Premièrement, nous avons introduit deux nouvelles bornes supérieures de la force d'un graphe et une nouvelle borne inférieure de la somme chromatique, basées sur la notion de motif que nous avons adapté de la littérature. L'intérêt majeur de ces travaux est la réduction de l'espace des solutions de MSCP. Deuxièmement, nous avons proposé plusieurs approches de résolution exacte de MSCP. La première méthode consiste en une modélisation de MSCP en un formalisme MaxSAT partiel pondéré ou MinSAT partiel pondéré afin d'utiliser les solveurs MaxSAT/MinSAT de l'état de l'art pour résoudre MSCP. Nous avons montré que notre borne de la force du graphe permet de réduire grandement la taille des instances MaxSAT/MinSAT obtenues et de rendre les solveurs MaxSAT compétitifs pour résoudre MSCP. Les deux autres méthodes de résolution proposées sont des approches de type Branch-and-Bound appelées BBMSCP et 3LMSCP. La différence entre BBMSCP et 3LMSCP est que 3LMSCP exploite la partition du graphe en stables afin de ne pas considérer les colorations symétriques / The Minimum Sum Coloring Problem (MSCP) of a graph is an optimization problem whose the aim is to find a valid coloring such that the sum of weights associated to the used color is minimum. The minimum number of colors needed in an optimal solution is called the strength of the graph, and the sum of weights of the colors used in an optimal solution is called the chromatic sum of the graph. The aim of this thesis was to study the MSCP in order to propose new approaches for its resolution. The contribution of the thesis is twofold. First, we have introduced two upper bounds of the strength and one lower bound of the chromatic sum of a graph, based on a notion called motif adapted from the literature. These bounds allow to reduce significantly the search space of the MSCP. Second, we have proposed several exact resolution methods for the MSCP. The first method consists in modelling the MSCP to a weighted partial MaxSAT or a weighted partial MinSAT and solves the MSCP using state-of-the-art MaxSAT/MinSAT solvers. We have showed that our upper bound of the strength allows to improve substantially the MaxSAT/MinSAT encodings, and consequently, the MaxSAT solvers are competitive to solve the MSCP. The two other resolution methods are based on the Branch-and-Bound scheme and are called BBMSCP and 3LMSCP respectively. The difference between BBMSCP and 3LMSCP is that BBMSCP explores many symmetric colorings but 3LMSCP exploits the partitions of the graph into stables to avoid symmetric colorings

Le travail de ce mémoire apporte une brique fonctionnelle et théorique dans l'élaboration d'un outil informatique générique pour la planification automatisée et optimisée d'une équipe d'employés polyvalents avec une première application dans le domaine de la grande distribution. En pratique, il fournit la formalisation mathématique d'une problématique métier riche où les règles de planification (début, durée, fin, quantité, etc.) à respecter s’appliquent sur différentes granularité temporelle (quart d’heure, plage horaire, horaire journalier, semaine, mois, année). Différentes techniques issues de la Recherche Opérationnelle ont été adaptées et testées tout d’abord pour une version du problème restreint à une semaine, puis pour la version complète à l’année. Ces méthodes correspondent à des heuristiques basées sur la méthode de génération de colonnes où le problème de pricing est résolu par un algorithme dédié de programmation dynamique imbriquée. Les expérimentations ont été réalisées avec des instances issues de cas réels et des instances générées s’inspirant des cas réels comptant jusqu’à une soixantaine d’employés à planifier sur un horizon de planification allant d’une semaine à un an (divisé par périodes de 15 minutes). Les tests réalisés montrent que les méthodes implémentées permettent l’obtention de plannings d'équipe de grande qualité tout en préservant les caractéristiques individuelles de chaque employé (compétences, disponibilité, temps de travail, etc.), le tout utilisable avec un ordinateur de gamme moyenne (simple cœur, moins 4 GB de RAM) avec des temps de calcul raisonnables (quelques secondes à plusieurs heures selon l’instance et méthode). / The thesis provides a practical and theoretical brick for developing a generic software tool for producing automated and optimized schedules of a multi-skill employees team with a first application in retail. We provide a mathematical formulation of a rich staff scheduling problem in which planning rules (start, duration, end, amount, etc.) that must be respected are applied on different time granularity (15 minutes period, timeslot, day-shift, week, month, year). Two variants of the problem with different planning horizons have been considered: the first one with one week and the second one with one year planning horizon. Several methods from Operations Research have been adapted to solve the problem. We propose heuristics based on the column generation approach where the pricing problem is solved using a dedicated nested dynamic programming algorithm. The experiments were performed both on real-life instances and on random instances derived from real cases. Instances have up to sixty employees and a planning horizon from one week to one year (divided by 15 minutes periods). The tests show that the proposed methods are able to find high-quality team schedules while taking into account the individual characteristics of each employee (skills, availability, working time, etc.) and run with a standard PC (single core, less than 4 GB of RAM) with a reasonable computation time (from several seconds to one hour depending on the instance and the used method).

Thesis (M.S.)--University of Missouri-Columbia, 2006. / The entire dissertation/thesis text is included in the research.pdf file; the official abstract appears in the short.pdf file (which also appears in the research.pdf); a non-technical general description, or public abstract, appears in the public.pdf file. Title from title screen of research.pdf file viewed on (February 6, 2007) Includes bibliographical references.

Thesis--Rutgers.

Thesis (M. Phil.)--Hong Kong University of Science and Technology, 2003. / Includes bibliographical references (leaves 51-52). Also available in electronic version. Access restricted to campus users.

No description available.

No description available.