Ce travail de doctorat aborde trois thématiques: (i) l’ordonnancement des systèmes de production à cheminements multiples et plus particulièrement le Job-shop soumis à un seuil de consommation énergétique ; (ii) la résolution d’un problème d’ordonnancement et d’affectation dans le contexte d’un système flexible de production sous la forme d’un Job-shop Flexible ; (iii) les méthodes de couplage entre la simulation et l’optimisation dans le cadre des problèmes de Job-shop avec incertitude. Différentes approches de résolutions sont appliquées pour chaque problème : une formalisation mathématique est proposée ainsi que plusieurs métaheuristiques (GRASP×ELS, VNS, MA, NSGA-II hybride et GRASP×ELS itéré) pour le Job-shop avec contrainte énergétique. Une extension du GRASP×ELS, notée GRASP-mELS, est ensuite proposée pour résoudre un problème de Job-shop Flexible ; différents systèmes de voisinages utilisés lors des phases de diversification et d’intensification des solutions sont également présentés. Les résultats montrent que les performances du GRASP-mELS sont comparables à celles de la littérature à la fois en terme de qualité et de temps de calcul. La dernière thématique concerne les méthodes de couplage entre optimisation et simulation avec deux problèmes étudiés : 1) un Job-shop Stochastique et 2) un Job-shop Flexible Réactif. Les méthodes de résolution reposent sur des métaheuristiques et sur le langage de simulation SIMAN intégré dans l’environnement ARENA. Les résultats montrent que les deux approches permettent de mieux prendre en compte les aspects aléatoires liés à la réalité des systèmes de production. / This doctoral work addresses three themes: (i) the scheduling of multi-path production systems and more specifically the Job-shop subjected to a power threshold; (ii) the resolution of a scheduling and assignment problem in the context of a flexible production system modelled as a Flexible Job-shop; (iii) the coupling methods between simulation and optimisation in the context of Job-shop problems with uncertainty. Different resolution approaches are applied for each problem: a mathematical formalisation is proposed as well as several metaheuristics (GRASP×ELS, VNS, MA, hybrid NSGA-II and iterated GRASP×ELS) for the Job-shop with power requirements. An extension of the GRASP×ELS, denoted GRASP-mELS, is then proposed to solve a Flexible Job-shop problem; different neighbourhood systems used during the diversification and intensification phases of solutions are also presented. The results show that the performances of the GRASP-mELS are comparable to the methods presented in the literature both in terms of quality of solutions and computation time. The last topic concerns the coupling methods between optimisation and simulation with two problems: 1) a Stochastic Job-shop and 2) a Reactive Flexible Job-shop. The resolution methods are based on metaheuristics and the SIMAN simulation language integrated in the ARENA environment. The results show that both approaches allow to better take into account the random aspects related to the reality of production systems.

La thèse porte sur l’étude de problèmes réels de transport et de distribution par voie routière. Il s’agit plus précisément de deux problèmes distincts d’optimisation des tournées de véhicules ; la distribution de produits pétroliers et le transfert des conteneurs. La résolution du premier problème, identifié comme le problème de tournées de véhicules avec compartiments multiples et fenêtres de temps ou MCVRP-TW (Multi-Compartment Vehicle Routing Problem with Time Windows), est basée sur une méthode de recherche tabou. Une adaptation de la méthode de résolution a été appliquée à deux autres problématiques annexes, la première intègre des contraintes supplémentaires liées à l’opération de chargement des produits pétroliers dans les compartiments, et la seconde inclut le concept d’ajustement des quantités demandées. Par ailleurs, dans l’optique d’une transition énergétique, nous nous sommes intéressés au problème de transfert des conteneurs par camions électriques dans la zone industrialo-portuaire du Havre. L’optimisation se situe à deux niveaux, un niveau stratégique pour le dimensionnement de l’infrastructure électrique et un niveau opérationnel pour la construction des tournées de véhicules. Seul le niveau stratégique a été abordé dans le cadre d’un projet de recherche grâce à un couplage de l’optimisation et la simulation. / The thesis focuses on the study of real road transportation and distribution pro-blems. The question concerns in particular the optimization of two different vehicle routing problems arising in the distribution of petroleum products and the transfer of containers. The first problem, modelled as an application of the multi-compartment vehicle routing problem with time windows (MCVRPTW), is solved by using a tabu search method. The same method is then applied to two other variants. One introduces additional constraints related to loading operations for petroleum products on the compartments, while the other one includes the ad-justment concept in quantities applied for. Moreover, in the context of an energy transition, we addressed the container transfer problem using a fleet of electric trucks in the industrial port zone of Le Havre. The optimization involves two levels : the strategic level for dimensioning electrical infrastructures and the operational level for constructing the vehicle routes. Only the strategic level is tackled with a research project thanks to a coupling of optimization and simulation.

Traditional network design problems only consider the long-term stationary travel patterns (e.g., fixed OD demand) and short-term variations of human mobility are ignored. This study aims to integrate human mobility characteristics and travel patterns into network design problems using a space-time network structure. Emerging technologies such as location-based social network platforms provide a unique opportunity for understanding human mobility patterns that can lead to advanced modeling techniques. To reach our goal, at first multimodal network design problems are investigated by considering safety and flow interactions between different modes of transport. We develop a network reconstruction method to expand a single-modal transportation network to a multi-modal network where flow interactions between different modes can be quantified. Then, in our second task, we investigate the trajectory of moving objects to see how they can reveal detailed information about human travel characteristics and presence probability with high-resolution detail. A time geography-based methodology is proposed to not only estimate an individual’s space-time trajectory based on his/her limited space-time sample points but also to quantify the accuracy of this estimation in a robust manner. A series of measures including activity bandwidth and normalized activity bandwidth are proposed to quantify the accuracy of trajectory estimation, and cutoff points are suggested for screening data records for mobility analysis. Finally, a space-time network-based modeling framework is proposed to integrate human mobility into network design problems. We construct a probabilistic network structure to quantify human’s presence probability at different locations and time. Then, a Mixed Integer Nonlinear Programming (MINLP) model is proposed to maximize the spatial and temporal coverage of individual targets. To achieve near optimal solutions for large-scale problems, greedy heuristic, Lagrangian relaxation and simulated annealing algorithms are implemented to solve the problem. The proposed algorithms are implemented on hypothetical and real world numerical examples to demonstrate the performance and effectiveness of the methodology on different network sizes and promising results have been obtained.

The tuning of optimization software is of key interest to researchers solving mixed integer programming (MIP) problems. The efficiency of the optimization software can be greatly impacted by the solver’s parameter settings and the structure of the MIP. A designed experiment approach is used to fit a statistical model that would suggest settings of the parameters that provided the largest reduction in the primal integral metric. Tuning exemplars of six and 59 factors (parameters) of optimization software, experimentation takes place on three classes of MIPs: survivable fixed telecommunication network design, a formulation of the support vector machine with the ramp loss and L1-norm regularization, and node packing for coding theory graphs. This research presents and demonstrates a framework for tuning a portfolio of MIP instances to not only obtain good parameter settings used for future instances of the same class of MIPs, but to also gain insights into which parameters and interactions of parameters are significant for that class of MIPs. The framework is used for benchmarking of solvers with tuned parameters on a portfolio of instances. A group screening method provides a way to reduce the number of factors in a design and reduces the time it takes to perform the tuning process. Portfolio benchmarking provides performance information of optimization solvers on a class with instances of a similar structure.

Operational research is a complex of different disciplines which, due to the appliance of mathematical methods, seek for optimal solutions of complicated problems. The basics of particular disciplines or the whole subject are commonly being taught at universities in the Czech republic. The operational research curriculum was omitted from secondary education twenty years ago. This thesis deals with topics such as why and how the subject of operational research could once again be presented to secondary school students. This thesis discusses theoretical background as well as purely practical questions. That is why this thesis includes the parts of didactics and methodology of the subject. The result offers a complex perspective of a possible reimplementation of the operational research subject to secondary schools and to their students' awareness.

Orientador: Antonio Carlos Moretti, Margarida Pinheiro Mello / Tese (doutorado) - Universidade Estadual de Campinas, Instituto de Matemática, Estatística e Computação Científica / Made available in DSpace on 2018-08-18T11:43:39Z (GMT). No. of bitstreams: 1 Oliveira_WashingtonAlvesde_D.pdf: 1534705 bytes, checksum: 351c92a12c85da49389a18880da92ee7 (MD5) Previous issue date: 2011 / Resumo: Existem na literatura diversos conceitos e definições que caracterizam e dão condições de otimalidade para as soluções de um problema de programação multiobjetivo. A mais importante é a condição necessária de primeira ordem, que generaliza a condição clássica do tipo Karush-Kuhn-Tucker em otimização não linear. Esta condição garante a existência de uma vizinhança arbitrária onde uma solução ótima está contida. No entanto, para se obter condições suficientes de otimalidade, tanto local como global, é necessário impor hipóteses adicionais sobre as funções objetivo e o conjunto de restrições, como convexidade ou as suas generalizações. Em determinados problemas tais hipóteses podem ser muito restritivas. Neste trabalho, introduzimos um conceito alternativo para identificar a vizinhança de uma solução ótima local em problemas de programação multiobjetivo. Em uma primeira etapa, usando este conceito, obtemos condições necessárias e suficientes de otimalidade para as soluções de um problema particular, onde cada função objetivo é constituída de um quociente de funções quadráticas e o conjunto de restrições é formado por desigualdades lineares. Então, mostramos como calcular o maior raio da região esférica centrada em uma solução ótima local na qual esta solução é ótima. Nesse processo, podemos concluir que esta solução também é globalmente ótima. Em uma segunda etapa, usando o gradiente e a Hessiana de cada função quadrática, caracterizamos as soluções ótimas locais. Em uma terceira etapa, obtemos condições suficientes de otimalidade global impondo algumas hipóteses adicionais, porém essas hipóteses não caracterizam nenhum tipo de convexidade generalizada sobre as funções objetivo. Finalizamos com alguns resultados de dualidade. Este problema particular, envolvendo otimização fracional, surge frequentemente em aplicações nos processos de tomada de decisão em Ciência da Gestão, por exemplo, quando se deseja otimizar razões como desempenho/custo, lucro/investimento, custo/tempo, etc. Por isso, também propomos ao longo do texto vários métodos computacionais derivados dos nossos resultados que podem ser usados na obtenção de soluções para esses tipos de aplicações / Abstract: In the literature there are several concepts and definitions that characterize and give optimality conditions for solutions of a multiobjective programming problem. The most important is the necessary first-order optimality condition that generalizes the Karush-Kuhn-Tucker conditions. This condition ensures the existence of an arbitrary neighborhood that contains an optimal solution. However, in order to obtain optimality sufficient conditions, both local and global, it is necessary to impose additional assumptions on the objective functions and on the feasible set such as convexity and its generalizations. Sometimes, in some problems, such assumptions are too restrictive. In this work, we introduce an alternative concept to identify the local optimal solution neighborhood in multiobjective programming problems. In a first step, using this concept, we obtain necessary and sufficient optimality conditions for the solutions of a particular problem, where each objective function consists of a ratio quadratic functions and the feasible set is defined by linear inequalities. Then we show how to calculate the largest radius of the spherical region centered on a local optimal solution in which the local solution is optimal. In this process we may conclude that the solution is also globally optimal. In a second step, using the gradient and the Hessian of each quadratic function, we characterize the local optimal solutions. In a third step, we obtain global optimality sufficient conditions by imposing some additional assumptions but these assumptions do not characterize any kind of generalized convexity on the objective functions. We conclude this work with some results of the duality. This particular problem, involving fractional optimization, arises frequently in the decision making of the management science applications, for example, if you want to otimize the performance/cost ratio, or profit/investment, or cost/time, etc.. Therefore, we also propose throughout the text various computational methods derived from our results. These methods can be used to obtain solutions to these types of applications / Doutorado / Matematica Aplicada / Doutor em Matemática Aplicada

Orientadores: Sergio Nascimento Bordalo, Denis Jose Schiozer / Dissertação (mestrado) - Universidade Estadual de Campinas, Faculdade de Engenharia Mecanica / Made available in DSpace on 2018-07-24T03:21:33Z (GMT). No. of bitstreams: 1 Paiva_RonaldoOliveirade_M.pdf: 5372317 bytes, checksum: 87a623d365c62b997b5436706619b759 (MD5) Previous issue date: 1997 / Resumo: Os custos envolvidos em intervenções de sonda e a perda de receita nos poços aguardando intervenções são elevados. Este trabalho propõe métodos para analisar profundamente a priorização dos poços em que a sonda deverá intervir. Para determinar a seqüência de intervenção nos poços, é necessário comparar o gasto de sonda com as perdas dos poços. Para calcular as perdas dos poços, é necessário analisar a influência monetária do fechamento dos poços nas curvas de produção dos reservatórios. Neste trabalho, esta análise é feita utilizando-se um simulador numérico de reservatórios. São apresentadas, também, simplificações possíveis para um cálculo expedito. A priorização dos poços é baseada na redução do custo total do caminho, que se constitui da soma das perdas devidas à espera da intervenção, somadas aos custos das sondas. Para determinar o itinerário ideal das sondas, existem muitos algoritmos. Neste trabalho, são implementados e comparados alguns algoritmos considerados intuitivos e de simples implementação. Recomenda-se o algoritmo da Têmpera Simulada para priorizar os poços. Este algoritmo foi implementado para rotear sondas terrestres em uma região petrolífera brasileira. Otimizando as seqüências de intervenção realizadas no ano de 1996, nesta região, identificou-se uma economia potencial de 15%nas perdas de produção, equivalente a 4.000 metros cúbicos/anode petróleo (25.000 bbl/ano) / Abstract: The costs of workover and the loss of revenue in wells waiting workover rigs are very high. This work proposes methods to prioritize these wells in order to minimize the total cost. To determine the workover sequence it is necessary to compare the rig expense with the wells'losses. To ca1culatethe wells' losses, it is necessary to analyze the monetary influence of the well shutdown in the production curves. In this work, this analysis is made by using a numerical reservo ir simulator. Simplified ca1culation procedures are also presented. The priority of the wells is based on the reduction of the total cost, which consists of the rig costs plus the revenue losses due to workover waiting. There are many algorithms able to determine the ideal rig path. In this work, simple and intuitive algorithms, are implemented and ,)mpared. The Simulated Annealing algorithm is recommended. This algorithm was implemented to optimize workover rig routes in a brazilian production region. Otimization of the workover sequence carried out in that region in 1996 identified a potential economy of 15% in the production losses, equivalent to 4.000 'm POT. 3¿/year ofoil (25.000 bbl/year) / Mestrado / Mestre em Engenharia de Petróleo

Low-and-middle-income countries (LMICs) have a higher mortality-to-incidence ratio for breast cancer compared to high-income countries (HICs) because of late-stage diagnosis. Mammography screening is recommended for early diagnosis, however, current screening guidelines are only generalized by economic disparities, and are based on extrapolation of data from randomized controlled trials in HICs, which have different disease burdens and all-cause mortality compared to LMICs. Moreover, the infrastructure capacity in LMICs is far below that needed for adopting current screening guidelines. This study analyzes the impact of disease burden, infrastructure availability, and other cause mortality on optimal mammography screening schedules for LMICs. Further, these key features are analyzed under the context of overdiagnosis, epidemiologic/clinical uncertainty in pathways of the initial stage of cancer, and variability in technological availability for diagnosis and treatment. It uses a Markov decision process (MDP) model to estimate optimal schedules under varying assumptions of resource availability, applying it to six LMICs. Results suggest that screening schedules should change with disease burden and life-expectancy. For countries with similar life-expectancy but different disease burden, the model suggests to screen age groups with higher incidence rates. For countries with similar incidence rate and different life expectancy, the model suggests to screen younger age groups for countries with lower life-expectancy. Overdiagnosis and differences in screening technology had minimal impact on optimal schedules. Optimality of screening schedules were sensitive to epidemiologic/clinical uncertainty. Results from this study suggest that, instead of generalized screening schedules, those tailored to disease burden and infrastructure capacity could help optimize resources. Results from this study can help inform current screening guidelines and future health investment plans.

The Course Timetabling Problem is a widely studied optimization problem where a number of sections are scheduled in concert with the assignment of students to sections in order to maximize the desirability of the resulting schedule for all stakeholders. This problem is commonly solved as a linear program with variables for each student or group of students with identical schedules. In this paper we explore an alternative formulation that aggregates binary student variables into integer variables denoting the number of students enrolled in a course. Our solution method assumes decomposition of the general schedule into time blocks, and applies a unique set theory based, integer linear programming formulation that seeks to maximize the total number of students enrolled in their desired sections across the time blocks. Once the problem has been solved, the simpler problem of disaggregating the solution is resolved. This approach can be used to find exact solutions, given sufficient computing power, or simplified to quickly find solutions within calculable bounds of optimality. Case studies with a local elementary school and a local high school show that the new formulation is significantly faster and can be made to be reasonably accurate.

The increased demand on distribution centers to provide quicker turnarounds from receiving to shipping while maintaining precise inventory accuracies is spurring the acquisition of a warehouse management system (WMS) to improve operations and increase efficiency. With the rapid expansion of WMS technology, it seems inevitable that warehouses will outgrow inefficient operational processes and switch to a system that can accommodate rapid development. Research has explained the financial burdens and benefits of acquiring a WMS, but there’s been minimal research describing the impacts of the actual implementation. This study took place within a 600,000 sq. ft. fulfillment center and focused on the day-to-day activities of its 300+ employees. A qualitative methodology was used while observing daily processes within the inbound, inventory control, outbound, and shipping departments throughout the implementation process to determine the impacts on operational procedures and the people involved. The results describe the adaptations necessary within each department to transform the former manually based processes into automated processes that support the WMS. Also, the configurational oversights within the WMS that led to time consuming complications when performing daily operational tasks. The findings of this study explain the key factors that impact a WMS implementation and opportunities to increase the chances of a successful implementation.