Um mercado globalizado altamente competitivo e a crescente horizontalização das cadeias de abastecimento realçam a importância da racionalização dos custos e da adequada seleção de fornecedores. Esses mesmos fatores, no entanto, agravam a complexidade envolvida no desempenhar dessas tarefas. A fim de desatar tais nós, o presente trabalho propõe uma abordagem para a seleção de fornecedores que conjuga técnicas de programação matemática que permitam a exploração de economias de escala e escopo a uma metodologia inovadora para construção de cenários de demanda baseada em conceitos modernos de suprimentos. O resultado desta abordagem foi um modelo de programação inteira mista visando a minimização dos custos por desempenho adquirido. Os resultados obtidos na aplicação a um caso hipotético relevam efetividade na redução dos custos, sem prejuízo à qualidade dos materiais adquiridos. O impacto nos custos decorre da reconfiguração da demanda, aumento do poder de barganha interno e externo e aproveitamento de ganhos de escala e escopo. / A highly competitive globalized market and a growingly horizontalization through supply chains highlight the importance of properly selecting suppliers and managing costs. These same factors, however, increase the complexity in performing such tasks. In order to solve this plot, it is presented in this work an approach for supplier selection connecting mathematical programming techniques, which allow the use of economies of scope and scale, and an innovative methodology that applies modern concepts of purchasing management for constructing new demand scenarios. From this approach a mixed integer programming model derives, with the goal of minimizing costs per performance acquired. The results of its application in a hypothetical case reveal the effectiveness of the approach in reducing the costs with no significant impact on the acquired performance. This is explained by the reconfiguration of the demand, a shift in the bargaining power within and out of the company and the incorporation of economies of scope and scale.

CoordenaÃÃo de AperfeiÃoamento de Pessoal de NÃvel Superior / Planejar as atividades de distribuiÃÃo de materiais em obras de terraplenagem pode representar um ganho na obra como um todo. Alguns estudos afirmam que, para obter uma economia geral na construÃÃo, os planejadores devem desenvolver uma estratÃgia de forma a otimizar a utilizaÃÃo dos recursos. Uma das formas de fazer isso à minimizar a distÃncia total percorrida pelos veÃculos na movimentaÃÃo de terra entre as zonas de corte e aterro. Hà muitos estudos e trabalhos que focam a otimizaÃÃo da distribuiÃÃo de materiais entre zonas de corte e aterro, porÃm poucos aplicaram em projetos reais com a consideraÃÃo de mÃltiplos equipamentos, alÃm de nÃo terem feito uma anÃlise baseada na distÃncia entre estacas. Este trabalho teve como objetivo desenvolver um modelo de ProgramaÃÃo MatemÃtica que minimize a distÃncia percorrida pelos caminhÃes basculantes em atividades de distribuiÃÃo de materiais na terraplenagem. O modelo elaborado com princÃpios da ProgramaÃÃo Linear Inteira foi baseado no problema de roteamento, cujo objetivo à minimizar o caminho percorrido. O modelo foi aplicado em um estudo de caso utilizando o projeto da obra rodoviÃria PE099, onde se obteve a alocaÃÃo de corte e aterro Ãtima, de forma a minimizar a distÃncia percorrida pelos caminhÃes. Ao comparar o resultado obtido pelo modelo e o resultado fornecido pelo diagrama de massas obtÃm-se uma economia de 40% no momento de transporte e, por conseguinte, na distÃncia mÃdia de transporte percorrida. O modelo proposto considerou algumas lacunas da literatura, entre elas o fato de considerar o problema de roteamento com mÃltiplos veÃculos, aplicado em um projeto real. Utilizando esse modelo, engenheiros, planejadores e analistas tem uma importante ferramenta computacional que facilitarà a tomada de decisÃo.

Irregular cutting and packing problems, with convex and non-convex polygons, are found in many industries such as metal mechanics, textiles, of shoe making, the furniture making and others. In this thesis we study the two-dimensional version of these problems, where we want to allocate a set of items, without overlap, inside one or more containers, limited or unlimited, so as to optimize an objective function. In this document we study the knapsack problem, placement problem, strip packing problem, cutting stock problem and bin packing problem. For these problems, the heuristic methods and mathematical programming models are proposed and presented very promising results, surpassing in many cases the best results in the specialized literature. This thesis is organized as follows. In Chapter 1, we present a review of the studied problems, the value proposition for this thesis with the main contributions and ideas. In Chapter 2, we propose a metaheursitic for the strip packing problem with irregular items and circles. Then, in Chapter 3, we present a generic heuristic for the allocation of irregular items that may be weakly or strongly heterogeneous and will be allocated in a container (output maximization problems) or multiple containers (input minimization problems). In Chapter 4, we propose a solution method for the cutting stock problem with deterministic demand and stochastic demand. In Chapters 5 and 6, we present mathematical programming models for the strip packing problem. Finally, in Chapter 7, we present a conclusion and a concise direction for future works. / Os problemas de corte e empacotamento de itens irregulares, polígonos convexos e não convexos, são encontrado em diversas indústrias, tais como a metal-mecânica, a têxtil, a de calçados, a moveleira e outras. Nesta tese estudamos a versão bidimensional destes problemas, na qual desejamos alocar um conjunto de itens, sem sobreposição, no interior de um ou mais recipientes, limitados ou ilimitados, de modo a otimizar uma função objetivo. Neste trabalho estudamos o problema da mochila, o problema do assentamento, o problema empacotamento em faixa, o problema de corte de estoque e o problema de empacotamento de contêineres. Para estes problemas, os métodos heurísticos e modelos de programação matemática propostos e apresentam resultados muito promissores, ultrapassando em muitos casos os melhores resultados da literatura especializada. Esta tese esta organizada da seguinte maneira. No Capítulo 1, apresentamos uma revisão dos problemas estudados, a proposta de valor deste doutorado com as principais contribuições e ideias. No Capítulo 2, propomos uma meta-heurística para o problema de empacotamento em faixa para itens irregulares e círculos. Em seguida, no Capítulo 3 apresentamos uma heurística genérica para a alocação de itens irregulares que podem ser fracamente ou fortemente heterogêneos e serão alocados em um recipiente (problema de maximização de saída) ou de múltiplos recipientes (problemas de minimização de entrada). O Capítulo 4 propõem um método de solução para o problema de corte de estoque com demanda conhecida e demanda estocástica. Nos Capítulos 5 e 6 apresentamos modelos de programação matemática para o problema de corte de itens irregulares em faixa. Finalmente, no Capítulo 7, apresentamos a conclusão e uma sucinta direção para os trabalhos futuros.

A logística de contêiner vem aumentando sua participação em volume de cargas transportadas, tornando-se a parcela mais significativa do tráfego de mercadorias. Com isso, o gerenciamento dos altos custos envolvidos com a aquisição, manutenção, manipulação e transporte desses contêineres tornam-se um problema relevante para as organizações. As alocações dos contêineres cheios e vazios são comumente vistos como dois sistemas distintos e estáticos e não de forma intregada e dinâmica. Há um número restrito de trabalhos na literatura desenvolvendo heurísticas integrando os sistemas, porém não foi encontrada uma formulação ótima para o problema. Logo, a questão para a dissertação é quão próximo estão os resultados das heurísticas encontradas na literatura, para o problema da alocação de contêineres, dos resultados ótimos. O presente trabalho apresenta uma formulação matemática para o problema de alocação dinâmica, e integrada, para contêineres cheios e vazios. A formulação foi testada com diversos cenários, objetivando saber o limite computacional das instâncias para a formulação. Como o problema é um problema NP-Hard, heurísticas são comumente apresentadas na literatura. Demonstra-se como podem ser realizadas comparações entre os resultados das heurísticas e os resultados ótimos e visam a constatação da importância de uma formulação ótima para comparações. / Containers' Logistics has increased their importance in the goods transportion and nowadays, has the most important share of them. With that in mind, the management of high costs of acquisition, maintenance, manipulation and transportation of them became a significant problem to organizations. The problem of empty container allocation and load container allocation are commonly treated as two distinct, and static, systems, which means without integration and not dynamically. Just a couple of examples could be found of the two systems dynamically integrated, and no optimal model was found. So, the question here is how close heuristics' results are from the optimal results. A mathematical formulation is presented to the problem concerned with the integration and the dynamics associated to it. The formulation was tested with several scenarios to determine the maximum size that could be tested with optimal results, in an acceptable computacional time. Since the problem is a NP-Hard problem, heuristics approach are commonly used. Here is demonstrated how could be compare optimal solutions of the formulation and solutions from heuristics, and aim to demonstrate the significance of the optimal formulation.

O planejamento de produção é um elemento essencial para as empresas, pois permite definir os volumes a serem produzidos, conforme a estimativa de demanda e a capacidade produtiva disponível. Este trabalho contribui para o planejamento da produção, integrando variáveis e parâmetros que podem ajudar na maximização do resultado econômico das organizações. Esta dissertação apresenta três objetivos principais relacionados a esse tema: (i) identificar os problemas e as variáveis que precisam ser analisadas no desenvolvimento de métodos que se adéquam às necessidades das áreas envolvidas; (ii) desenvolver algoritmo para integrar as variáveis identificadas e os dados empresariais, de forma a viabilizar a aplicação do modelo, baseado em programação matemática e distribuições de probabilidade; (iii) aplicar os modelos propostos, a fim de avaliar sua utilidade e discutir os resultados obtidos. O estudo realizado revela a importância do uso de métodos formais de planejamento da produção integrados à definição do preço do produto. A definição de preços ou volumes de produção diferente dos valores ótimos pode afetar substancialmente o lucro global do sistema produtivo. / Production planning is an essential tool for companies, since it establishes the volumes to be produced, according to estimated demand and available production capacity. This work contributes with production planning field by integrating variables and parameters that impact the economic results of the organizations. This study presents three main objectives: (i) identification of issues and variables that need to be analyzed to develop methods suited to the needs of the areas involved, (ii) development of algorithms to integrate the identified variables and business data, in order to enable the application of the model, based on mathematical programming and probability distributions, (iii) application of the proposed models to evaluate their usefulness and discuss results. The study reveals the importance of using production planning formal methods that integrate products’ prices. The establishment of prices or production volumes different from optimum values may substantially affect production system global profit.

A construção de grades horárias dos cursos de uma universidade é um problema que deve ser enfrentado no início de todos os semestres e, por mobilizar quantidades significativas de recursos, se constitui numa das mais importantes tarefas administrativas de uma universidade. Trata-se de um problema clássico, combinatório, que tem atraído atenção por conta da dificuldade de se encontrar boas soluções. É classificado, em termos de complexidade computacional, como NP-hard, o que implica grande exigência de capacidade de processamento. É modelado de maneiras muito diversas, no intuito de se obter adequação quanto ao contexto educacional do país, às regras específicas da instituição ou aos objetivos específicos dos gestores, entre outros. Foi feita uma revisão de literatura no intuito de apoiar a modelagem do problema, nesse trabalho, e de contribuir com a comunidade de pesquisadores sobre o tema ao agregar informações a respeito das pesquisas publicadas até então. O problema é modelado, neste trabalho, por meio de técnicas de Pesquisa Operacional com o objetivo de produzir grades horárias com aulas distribuídas uniformemente ao longo da semana, em uma primeira etapa, para que, na etapa seguinte, ao se atribuir salas de aula às turmas, a utilização dos espaços físicos da Universidade seja otimizada. Dados foram coletados de uma instituição federal de ensino superior para a implementação do modelo. Resultados obtidos no processamento com os dados reais mostraram que o modelo reduz consideravelmente a utilização de salas de aula. / The timetabling construction for University courses is a problem that must be faced at each beginning of semester and, since it mobilizes significant amounts of resources, it constitutes in one of the most important administrative tasks in a University. It's a classic, combinatorial problem that has attracted attention due to its difficulty in finding good solutions. In terms of computational complexity, it's classified as NP-hard, which involves great processing capacity. It's modeled in a number of different ways, aimed to obtain adequacy to the educational context of the country, to the specific higher education institutional rules, or to the specific managers goals, amongst others. A literature review was performed, aimed to support, in this research, the problems modeling, and to contribute to the researchers community, adding the research information published so far. The problem is modeled, in this work, by means of Operations Research techniques, aiming to produce evenly distributed timetables along the week, in the first step, and to assign the classrooms to the groups of students in the next, in such a way that the physical spaces utilization of the University is optimized. Data was collected from a federal higher education institution in order to implement de model. Results obtained through its processing with this data showed that the model considerably reduces the classrooms utilization.

Orientador: Paulo Augusto Valente Ferreira / Tese (doutorado) - Universidade Estadual de Campinas, Faculdade de Engenharia Elétrica e de Computação / Made available in DSpace on 2018-08-21T14:52:27Z (GMT). No. of bitstreams: 1 Ashtiani_AlirezaMohebi_D.pdf: 1381601 bytes, checksum: 9ae82bd53a7cf70422fed2348416f8f0 (MD5) Previous issue date: 2012 / Resumo: Muitos problemas práticos em Engenharia, Economia e Planejamento são modelados de maneira conveniente como problemas de Otimização Global. Esta tese tem como objetivo principal apresentar novas técnicas de Otimização Global com foco na resolução de duas importantes classes de problemas: problemas de Programação Multiplicativa Generalizada, os quais envolvem a minimização e a maximização de uma soma finita de produtos de funções convexas e côncavas, respectivamente, e problemas de Programação Fracionária Generalizada, os quais, por sua vez, envolvem a minimização e a maximização de uma soma finita de razões de funções convexa-côncava ou côncava-convexa, respectivamente. Na tese demonstra-se que todos estes problemas podem ser eficientemente resolvidos por um mesmo algoritmo de aproximação externa, a partir da reformulação dos problemas como problemas com infinitas restrições lineares de desigualdade. Um algoritmo baseado em enumeração de restrições e um algoritmo de aproximação externa combinado a uma técnica branch-and-bound são usados para resolver globalmente problemas de Programação Multiplicativa. Em seguida, as mesmas técnicas são empregadas na resolução de problemas de Programação Fracionária. Experiências computacionais atestam a viabilidade e a eficiência dos métodos de Otimização Global propostos, os quais também são facilmente programáveis a partir de pacotes de otimização disponíveis comercialmente / Abstract: Many practical problems in Engineering, Economics and Planning are modeled in a convenient way by Global Optimization problems. The principal objective of this thesis is to introduce new global optimization techniques with focus on the resolution of two important classes of problems: Generalized Multiplicative Programming Problems, in which involve the minimization and maximization of a finite sum of products of convex and concave functions, respectively, and Generalized Fractional Programming Problems, in which, in turn, involve the minimization and maximization of a finite sum of convex-concave and concave-convex ratio functions, respectively. The thesis demonstrates that all these problems can be efficiently solved by the same outer approximation algorithm, from the reformulation of the problems as problems with infinite linear inequality constraints. An algorithm based on a constraint enumeration and an outer approximation algorithm together with a branch-and-bound technique are used to globally solve Multiplicative Programming problems. Then, the same techniques are employed in the resolution of Fractional Programming problems. Computational experiments certify the viability and efficiency of the proposed Global Optimization methods, which are also easily programmable through commercially available optimization packages / Doutorado / Automação / Doutor em Engenharia Elétrica

En raison de problèmes opérationnels et d’autres événements inattendus, un grand nombre d’incidents se produisent quotidiennement dans les systèmes de transport ferroviaire. Certains d’entre eux ont un impact local, mais quelques fois, essentiellement dans les réseaux ferroviaires plus saturés, des petits incidents peuvent se propager à travers tout le réseau et perturber de manière significative les horaires des trains. Dans cette thèse doctorale, nous présentons le problème de réordonnancement de plan de circulation ferroviaire en cas d’incident comme la problématique de créer un plan de circulation provisoire de manière à minimiser les effets de la propagation des incidents. Ce travail est issu du projet MAGES (Module d’Aide à la Gestion des Sillons) qui développe des systèmes de régulation pour le trafic ferroviaire. Nous présentons deux modèles différents qui permettent de trouver des solutions à ce problème : Programmation Linéaire en Nombres Entiers (PLNE) et Programmation Par Contraintes (PPC). Du fait de la nature fortement combinatoire du problème et de la nécessité de répondre rapidement aux incidents, il ne paraît pas raisonnable d’envisager une résolution exacte. Les méthodes correctives proposées consistent donc à explorer un voisinage restreint des solutions : right-shift rescheduling; une méthode basée sur des coupes de proximité; une méthode d’analyse statistique de la propagation des incidents (SAPI) et un méthode basée sur la PPC. Additionnellement, certaines de ces méthodes ont été adaptées sous forme d’algorithmes itératifs avec l’objectif d’améliorer progressivement la solution quand le temps d’exécution le permet. SAPI est une des principales contributions de cette thèse. SAPI intègre les concepts de right-shift rescheduling avec les coupes de proximité. Du fait de la taille des réseaux en jeu et du nombre de circulations, les phénomènes complexes de propagation d’un incident font qu’il est très difficile de connaitre de manière précise les événements qui seront affectés. Toutefois, il est tout de même envisageable d’évaluer la probabilité qu’un événement soit affecté. Pour calculer cette probabilité, un modèle de régression logistique est utilisé avec des variables explicatives dérivées du réseau et des circulations. Diverses variantes de ces méthodes sont évaluées et comparées en utilisant deux réseaux ferroviaires localisés en France et au Chili. À partir des résultats obtenus, il est possible de conclure que SAPI est meilleure que les autres méthodes en terme de vitesse de convergence vers l’optimum pour les instances de petite taille et moyenne alors qu’une méthode coopérative PNLE/PPC est capable de trouver des solutions pour les instances de plus grande taille. La difficulté de comparer SAPI avec d’autres méthodes présentées dans la littérature nous a encouragés à appliquer la méthode à un autre problème. Ainsi, cette méthodologie a été également adaptée au problème de réordonnancement de passagers, vols et appareils (avions) en cas de perturbations, problème originalement proposé dans le contexte du Challenge ROADEF 2009. Les résultats montrent que SAPI est efficace pour résoudre ce problème avec des solutions au-dessus de la moyenne des équipes finalistes en obtenant la troisième place du challenge / For operational and unpredictable reasons, many small incidents occur day after day in rail transportation systems. Most of them have a local impact; but, in some cases, minimal disruptions can spread out through the whole network and affect significantly the train schedules. In this Thesis, we present the Railway Rescheduling Problem (RRP) as the problem of finding a new schedule of trains after one or several incidents by minimizing some measure of the effect, e.g., the total delay. This Thesis has been developed in the context of the MAGES project that builds mathematical models and algorithms for optimizing railway operations. Two complementary formulations are proposed to model this problem: Mixed-Integer Programming (MIP) and Constraint Programming (CP). Because of the impossibility of solving real-world instances by using standard solvers, we propose several solutions methods: right-shift rescheduling; a MIP-based local search method; Statistical Analysis of Propagation of Incidents (SAPI); and a CP-based approach. Some methods are presented in different versions by extending them to iterative approaches. Among them; SAPI is one of the major contributions of this Thesis. It integrates the concepts of right-shift rescheduling and the MIP-based local search method by fixing integer variables and adding linear inequalities (cuts). SAPI assumes that the effects of disruptions can be propagated to other upcoming events. Nevertheless, this propagation is not uniform to all events and could be forecasted by a statistical analysis. Different versions of the methods are compared in two different networks located in France and Chile. From the results, it is possible to conclude that SAPI finds good solutions faster than the other methods, while a cooperative CP/MIP approach that takes advantage of both formulations seems to be appropriate for large instances. Because of the difficulty to compare SAPI to other methods presented in the literature due to lack of public benchmarks, we applied it to another problem where public instances are available. Hence, the methodology was adapted and applied to the problem of rescheduling passengers, flights, and aircraft under disrupted operations in the context of the ROADEF challenge 2009. SAPI took the third position on this competition, showing that the method seems to be effective solving such type of problems efficiently

Multi-service outsourcing has become an important business approach since it can significantly reduce service cost, shorten waiting time, improve the customer satisfaction and enhance the firm’s core competence. In fact, on-demand cloud resources can lead manufacturers to improve their business processes and use an integrated and intelligent supply chain network. In addition, cloud manufacturing, as an emerging manufacturing system technology, will likely enable small and medium sized enterprises (SMEs) to move towards using dynamic scalability and ‘free’ available data resources in a virtual manner. Although there has been some research in these areas, there is still a lack of proper cloud based solutions for the whole manufacturing supply chain network. In addition, of the research papers studied, only a few reviewed and implemented the cloud based supply chain from a decision-making point of view, especially in suppliers evaluation and selection studies. Most studies only focused on cloud-based supply chain definitions, architectures, applications, advantages and limitations which can be offered to SMEs. Hence, a comprehensive research study to find an optimum set of suppliers for a number of goods and services required for a project within the cloud manufacturing context is necessary. Providing real and multi-way relationships through a suppliers selection process based on an intelligent cloud-based manufacturing supply chain network, by using the Internet, is the main aim of this research. The research has an emphasis on multi-criteria decision making approach. The proposed model is based on ‘Goal Integer 0-1 Programming’ method for the suppliers selection part and ‘Linear Programming’ method for the project planning part. The proposed framework consists of four modules, namely a) multi-criteria module, b) bidding module, c) optimisation module, and d) learning module. Learning module allows the model to learn about the suppliers’ past performance over the course of the system’s life. Average performance measures are calculated over a moving fixed period, results of which are stored in a ‘dynamic memory’ element as linked to the suppliers’ database. The methodological approach is validated based on a case study in the oil and gas industry, characterised by 29 services linked together in a network structure, 108 suppliers, and 128 proposals for the services. The case study covers a variety of services from designing to manufacturing and delivery. On the implementation side, a cloud manufacturing based suppliers selection system (OPTiSupply.uk®) is designed and uploaded on the virtual server of Amazon EC2. The system enables customers and suppliers to offer and receive various services on the Web. Apart from the user interface functionality, the system also allows interaction with the MS-Excel© based data and the associated mathematical programming.

The aim of the thesis is the mathematical model, which is capable to divide participants of large summer camps into groups, according to specific limitations. The first part describes the economics model and all valid conditions. The second part is devoted to theoretical description. There are mentioned the basics of mathematical programming and the basic of working with Excel and VBA. The thesis describes only actually used methods. The following third part shows the final form of the model. So the reader doesn´t have to go through the whole process, described in the fourth part. There is a model testing in the fourth part, especially with the help of the Excel Solver. The problems are sold immediately. That is the reason why the fifth part can be used for implementation of working environment, which allows the end user to run the model without any significant knowledge of the issue. The app uses the wide possibilities of VBA. The sixth part briefly describes other add-ins, that are able to solve mathematical problem. The conclusion summarizes all the previous parts and offeres solution, that would be used in real application of the thesis.