No description available.

No description available.

This thesis gives a comprehensive view of the scope of formulations and<br />related solution approaches for the cutting stock problem (CSP) and its<br />variants. The focus is on branch-and-price approaches. Specialized<br />algorithms are developed for knapsack subproblems that arise in the<br />course of the algorithm. Thorough numerical tests are used to identify good strategies<br />for initialization, stabilization, branching, and producing<br />primal solutions. Industrial variants of the <br />problem are shown to be tractable for a branch-and-price approach.<br /><br /><br />The models studied are the following: the standard cutting stock and<br />bin packing problems, a variant in which the production levels lie in<br />a prescribed interval of tolerance, the multiple width cutting stock<br />problem in which stock pieces are of different size, a variant with<br />additional technical constraints that arise typically in industrial<br />applications, and a variant where the number of distinct cutting<br />patterns used is minimized given a waste threshold. <br /><br /><br />First, we consider various formulation of the Cutting Stock Problem<br />(CSP): different models of the knapsack subproblem can be exploited to<br />reformulate the CSP. Moreover, we introduce different ways of<br />modeling local exchanges in the solution (primal exchanges imply dual<br />constraints that stabilize the column generation procedure). Some<br />models are shown to be valid integer programming (IP) reformulations while others define<br />relaxations. The dual bounds defined by their LP solution are compared<br />theoretically.<br /><br />Then, we study the variants of the knapsack subproblem that arise<br />in a column generation approach to the CSP. The branching constraints<br />used in the branch-and-price algorithm can result in class bound and<br />setup cost or the need for a binary decomposition in the subproblem. <br />We show how standard knapsack solvers (dynamic programming approach and specialized<br />branch-and-bound algorithm) can be extended to these variants of the<br />knapsack problem.<br /><br />Next, we discuss some branch-and-price implementation strategies. We compare <br />different modes of initialization of the column generation procedure, we present our numerical study of various stabilization<br />strategies to accelerate convergence of the procedure. We compare in particular the impact of the various ways of introducing<br />local exchanges in our primal model and other stabilization techniques<br />such as dual solution smoothing techniques or penalization from a<br />stability center that prevent the fluctuation of the dual variables. <br />To generate the columns we study different strategies based on the use of heuristic columns or on a multiple generation of columns.<br />We also consider the use of heuristics based on column generation to find a primal bound. These are compared to a classic constructive heuristic. Then, we compare the different branching rules that are used in the branch-and-price procedure. <br /><br />Finally, we present numerical results on two industrial applications that<br />correspond to the variant with technical restrictions for which we<br />minimize first the waste and then the number of setups.

La classification automatique de textes était jusqu'à présent employée pour l'indexation documentaire. À travers quatre exemples, nous présentons quelques caractéristiques de nouveaux contextes applicatifs ainsi que leurs conséquences pour les algorithmes existants. Nous mettons en évidence le fait que Rocchio, d'ordinaire peu performant, est particulièrement adapté aux corpus bruités et à une utilisation semi-automatique mais très désavantagé avec des classes définies par plusieurs thèmes. Nous proposons une extension de Rocchio, Rocchio Multi-Prototypes, pour gérer les classes multi-thématiques en adaptant la complexité de son modèle d'apprentissage. RMP utilise un algorithme de classification faiblement supervisée qui détecte des sous-classes et sélectionne les plus utiles pour la catégorisation. Nous proposons aussi un algorithme de détection de changements de concepts dans des corpus à flux temporel à partir du calcul du taux d'activité des sous-classes.

Un pulsar est une étoile à neutrons en rotation rapide et dotée d'un fort champ magnétique qui peut se manifester en émettant sur tout le spectre électromagnétique. Dans cette thèse, je m'intéresse au rayonnement radio produit par l'étoile. Je commence ainsi par décrire l'instrumentation de dédispersion cohérente à base de GPUs installée au Radiotélescope de Nançay avec deux autres modes d'observation que j'ai développés : un mode pour la recherche de nouveaux pulsar et un mode spectromètre. Une autre partie de ce travail détaille le retraitement en cours du sondage Foster fait à la fin des années 90 à Nançay ainsi que de nouvelles observations ciblées, sur des candidats HESS notamment. Je présente ensuite les résultats obtenus sur les pulsars relativistes J0737-3039A et J1906+0746 avec respectivement des tests de la Relativité Générale et la mesure de la précession géodétique. Des données de polarimétrie ont ainsi permis de déterminer la géométrie du système de PSR J1906+0746. Enfin, je termine par l'analyse des temps d'arrivées de 20 pulsars millisecondes observés à Nançay dans le cadre de l'EPTA, une collaboration européenne pour un réseau de chronométrage pulsar avec pour objectif la détection d'un fond d'ondes gravitationnelles, possible d'ici 5 à 10 ans.

Speziell zur Sicherung der Versorgung mit Elektroenergie wird in diesem Einhefter eine Expertendiskussion des 28. ZEIT FORUM DER WISSENSCHAFT vom 18.12.2007 aufgegriffen. Die Experten vertreten dabei unterschiedliche Interessen. Ziel der Materialien ist es, Schülerinnen und Schüler ab Klasse 9 anzuregen, sich mit einem politischen Konflikt auseinanderzusetzen und begründet Stellung zu beziehen. Des weiteren finden sich in der Zusammenstellung die Lösungsansätze der effizienten Produktion und Nutzung elektrischer Energie, der Nutzung regenerativer Energiequellen sowie der Nutzung eines Energiemix. Dabei werden die verschiedenen Unterrichtsmethoden der Pro- und Contra-Diskussion, des Gruppenpuzzles, der Zukunftskonferenz und der Szenariotechnik angesprochen.

Ce mémoire repose sur la notion que l'industrie pharmaceutique mondiale traverse une sévère « crise » de productivité (Wood Mackenzie, 2003 ; Van Arnum, 2003; Banerjee et al., 2001 ; Bolten et DeGregorio, 2002; Graves et Langowitz, 1996). Depuis les dernières années, l'industrie a peu innové en nouveaux médicaments commercialisés annuellement. Pourtant, les investissements n'ont cessé de croître, passant de 1,3 milliard de dollars U.S. en 1977, à 32,1 milliards de dollars U.S. en 2002 (PhRMA, 2004). La diminution du nombre d'approbations de nouveaux médicaments, combinée à l'augmentation croissante des dépenses en R-D, ont eu pour effet d'augmenter substantiellement le coût moyen de production estimé d'un nouveau médicament. Les données disponibles montrent l'émergence d'une nouvelle structure de coûts. Celle-ci semble avoir provoqué un changement dans la perception des grandes firmes au sujet de la taille minimale efficace (TME) permettant de conserver un avantage concurrentiel; puisque dès le début des années 1990, d'importantes vagues de fusions et d'acquisitions furent constatées dans ce secteur. Malgré la consolidation de l'industrie, les données disponibles montrent que la productivité continue de décroître. Face à cette situation, plusieurs universitaires et acteurs de l'industrie se sont penchés sur les causes possibles de cette « crise » de productivité (James, 1994; Drews et Ryser, 1996; Christensen, 1997). Cependant, aucun chercheur ne s'est intéressé à l'apport d'une modélisation structurelle par rétroaction de ces difficultés. De la revue de la littérature semble émerger un cercle vicieux stratégique (nommé « paradoxe stratégique ») qui permet de montrer que les stratégies déployées par les grandes firmes de l'industrie pourraient ne pas produire les résultats escomptés à moyen et long terme. Appuyée par une collecte de données exhaustive, cette recherche propose une modélisation par la dynamique des systèmes du « pipeline » d'études cliniques, de fabrication et de commercialisation des 14 meneurs de l'industrie mondiale. L'objectif de la recherche consiste à analyser et à comprendre les diverses influences et rétroactions entre les variables et leurs impacts sur l'état de ce système. L'analyse des comportements du modèle a permis d'illustrer, par la simulation, le « choc global » du paradoxe stratégique sur la productivité. Sommairement, le modèle montre que les stratégies mises en place pour contrer la crise de productivité auraient des répercussions inattendues sur l'état du système. Les stratégies déployées contribueraient, de fait, à entretenir les difficultés associées à la productivité et ainsi à accentuer la « crise » actuelle. La simulation de divers scénarios permet d'évaluer et d'exposer de manière systémique les causes possibles de ce paradoxe. ______________________________________________________________________________ MOTS-CLÉS DE L’AUTEUR : Industrie de la recherche pharmaceutique, Dynamique des systèmes, Modélisation, Crise de productivité, Paradoxe stratégique, Fusions et acquisitions (F-A).

Parce que les pratiques de changement actuellement mises en œuvre dans les organisations n'atteignent pas les résultats escomptés et contribuent, par le fait même, à la toxicité du milieu du travail, nous avons exploré d'autres avenues en matière de changement organisationnel. Ancrés dans une épistémologie de la complexité et animés par des valeurs humanistes, nous avons accompagné un processus de changement de type non linéaire au sein d'une entreprise de la ville de Québec, dont le design a été réalisé de concert avec les dirigeants et les employés. Guidé par la typologie du changement de Bateson, par la théorie en U de Scharmer et par les concepts de lieu et d'accompagnement, le processus de changement a mis à contribution des pratiques de nature participative de manière à mobiliser les personnes autour des enjeux qui se trouvaient au cœur de l'organisation, d'où ont émergé plusieurs idées novatrices. Réalisé sous le mode de la recherche-intervention, le processus de changement mis en œuvre avait un objectif double: celui de favoriser le changement au sein du milieu, et celui d'enrichir les connaissances en matière de changement organisationnel en cernant les conditions, tant contextuelles, organisationnelles que d'accompagnement, qui favorisent la traversée de la courbe en U de Scharmer. Pour ce faire, durant un peu plus de six mois, nous avons recueilli des données sur le processus de changement grâce à l'observation et à l'utilisation d'un journal de bord, à la distribution d'un questionnaire en ligne et à un outil de mémoire, le 3e œil. En plus de favoriser le changement au sein du milieu, le processus aura permis de cerner seize conditions facilitant l'émergence du changement. Finalement, les pistes de réflexion qui se dégagent de l'étude pointent vers l'importance, dans le cadre de recherches et d'interventions futures, d'explorer plus en profondeur ce qui favoriserait l'incarnation des pratiques de mobilisation dans la gestion quotidienne des organisations. ______________________________________________________________________________ MOTS-CLÉS DE L’AUTEUR : Changement organisationnel, non linéarité, émergence, recherche-intervention, communication, complexité, 3e œil.

La planification de chemin est un domaine de l'intelligence artificielle permettant à un personnage, un objet, une unité de se déplacer automatiquement, dans un environnement, en évitant les obstacles et sans intervention humaine. Ce déplacement s'effectue entre une configuration de départ et une configuration d'arrivée. Lors de ce déplacement, à aucun moment le personnage ne doit se retrouver dans une configuration invalide. Dans le contexte des jeux vidéo commerciaux actuels, cette technique est malheureusement encore peu utilisée correctement. De plus, peu de publications concernent la planification de chemin lorsqu'effectuée dans un environnement triangularisé. Lorsqu'utilisé dans un jeu vidéo, il est nécessaire que le calcul du chemin soit effectué très rapidement afin de fournir un temps de réaction presque immédiat au joueur. La solution calculée n'est alors pas forcément optimale mais propose un bon compromis si l'on souhaite mettre l'accent sur la vitesse de réponse. Nous expliquons d'abord le principe de la planification de chemin en détail et ensuite certaines des techniques les plus connues tels que Dijkstra, A*, Breadth First Search, Depth First Search, etc. Nous détaillons les avantages et inconvénients des environnements triangularisés par rapport aux autres techniques de maillage. Nous exposons aussi dans ce mémoire le fruit de nos recherches et expérimentations sur l'environnement de recherche Mammoth en comparant l'évolution de la planification de chemin dans ce contexte précis. Nous utilisons également les techniques existantes pour parcourir les cartes du jeu et discutons des problèmes rencontrés et des évolutions possibles. De nos jours, lorsque la planification de chemin est effectuée dans un environnement triangularisé, on parle souvent de A* pour la sélection des triangles et ensuite de parcours par les milieux des côtés des triangles ou bien par leur centre. Or, cela est loin d'être optimal et bien que rapide, propose un déplacement nettement plus long dans ce cas. Pour répondre à cette problématique, nous utilisons en particulier trois algorithmes spécifiques : Triangulation A* et Triangulation Reduction A* afin de sélectionner les triangles par lesquels le personnage va passer et l'algorithme funnel modifié pour le déplacement à l'intérieur de ces triangles. Pour conclure, nous comparons ces différentes techniques de planification de chemin dans ce contexte en comparant la vitesse d' exécution, le nombre de nœuds explorés et la distance parcourue notamment afin d'en déduire la technique la plus appropriée pour Mammoth. ______________________________________________________________________________ MOTS-CLÉS DE L’AUTEUR : Planification de chemin, pathfinding, triangulation, algorithmes, A*, funnel, TA*, TRA*

Tout système de recherche d'information développe une méthodologie formelle ou opérationnelle pour affirmer si les termes de chaque document correspondent à ceux de la requête. La plupart de ces systèmes s'appuie sur l'hypothèse que les termes extraits des documents ont été parfaitement reconnus ou identifiés, et de fait leur fonction de correspondance repose sur une capacité à disposer d'une relation d'égalité entre terme du document et terme de la requête. <br />Notre travail se positionne dans le cas où les données ne s'avèrent pas parfaitement reconnues et donc qualifiées d'incertaines. Dans ce contexte, l'égalité entre termes du document et termes de la requête est remise en cause pour laisser place à la notion de ‘presque égalité'. Nous proposons un système de recherche d'informations adapté aux données incertaines et basé sur le modèle de langue. Nous introduisons la notion d'appariement qui mesure la ‘presque égalité' entre deux termes par le biais de la concordance et de l'intersection. L'appariement s'intègre à la fonction de correspondance. De plus, la valeur de certitude d'extraction des termes fournie par un système d'interprétation s'insère dans la fonction de pondération. Préalablement à la mise en place d'un tel modèle, nous vérifions l'applicabilité des hypothèses de base de la recherche d'information, à savoir la loi de Zipf et la conjecture de Luhn, à des données issues de l'oral, exemple de données incertaines.<br />Le modèle proposé est validé expérimentalement et comparé à des systèmes n'intégrant pas la notion d'incertitude. Enfin, nous présentons une application possible utilisant un système de recherche adapté aux données incertaines : un outil d'aide à la réunion téléphonique.