Efficient multi-dimensional assignment algorithms and their application in multi-frame tracking / In this work, we propose a novel convex dual approach to the multidimensional dimensional assignment problem, which is an NP-hard binary programming problem. It is shown that the proposed dual approach is equivalent to the Lagrangian relaxation method in terms of the best value attainable by the two approaches. However, the pure dual representation is not only more elegant, but also makes the theoretical analysis of the algorithm more tractable. In fact, we obtain a su cient and necessary condition for the duality gap to be zero, or equivalently, for the Lagrangian relaxation approach to nd the optimal solution to the assignment problem with a guarantee. Also, we establish a mild and easy-to-check condition, under which the dual problem is equivalent to the original one. In general cases, the optimal value of the dual problem can provide a satisfactory lower bound on the optimal value of the original assignment problem. We then extend the purely dual formulation to handle the more general multidimensional assignment problem. The convex dual representation is derived and its relationship to the Lagrangian relaxation method is investigated once again. Also, we discuss the condition under which the duality gap is zero. It is also pointed out that the process of Lagrangian relaxation is essentially equivalent to one of relaxing the binary constraint condition, thus necessitating the auction search operation to recover the binary constraint. Furthermore, a numerical algorithm based on the dual formulation along with a local search strategy is presented. Finally, the newly proposed algorithm is shown to outperform the Lagrangian relaxation method in a number of multi-target tracking simulations. / Thesis / Doctor of Philosophy (PhD)

Scheduling is a practical optimisiation problem which can be solved by means of integer or binary programming methods. This paper focuses on university scheduling, in particular the schedule of the University of Economics in Prague, it is however possible to apply the results to schedules of other universities. We begin with the basics of linear programming, focusing on integer and binary programming as well as selected methods used to solve these problems. We then construct an optimisation model for the schedule of a subset of subjects based on real requirements (data 2009) and we compare the results with the actual schedule of the University of Economics in Prague. In conclusion we discuss some of the assumptions made during model development. The model is then generalised to include the entire set of subjects of the university. For the conversion of the software results into a more legible format, we include two MS Excel macros as part of this paper.

No description available.

This research introduces parallel U-shaped assembly lines with crossover points. Crossover points are connecting points between two parallel U-shaped lines making the lines interdependent. The assembly lines can be employed to manufacture a variety of products belonging to the same product family. This is achieved by utilizing the concepts of crossover points, multi-line stations, and regular stations. The binary programming formulation presented in this research can be employed for any scenario (e.g. task times, cycle times, and the number of tasks) in the configuration that includes a crossover point. The comparison of numerical problem solutions based on the proposed heuristic approach with the traditional approach highlights the possible reduction in the quantity of workers required. The conclusion from this research is that a wider variety of products can be manufactured at the same capital expense using parallel U-shaped assembly lines with crossover points, leading to a reduction in the total number of workers. / M. S.

Made available in DSpace on 2016-06-02T19:51:42Z (GMT). No. of bitstreams: 1 DissJFPJ.pdf: 724498 bytes, checksum: 72058d90b6e1572903d553ad3e5d24af (MD5) Previous issue date: 2004-02-26 / Initially this work explains, appraises and characterizes industrial cluster in the following classes: (C1) they are the Regional Cluster without formal coordenation that many authors call by Industrial Districts; (C2) class is about the clusters for Exportation e (C3) is about the Cluster Commanded by a Mother-company. The first class has been widely studied in literature. The group of research PLACOP of the Department of Production Engineering at Federal University in São Carlos has been developed research directed toward the classes C2 and C3. It is made a literature review on disturbance in the productive capacity once these factors are ones of the main problems of the current productive system; it is appraised change and disturbance, analyzed the impact of the disturbance and considered the classification of the types of disturbance in the productive capacity. After this it is briefly revised the problem of resource allocation. Later the problem of order allocation in industrial cluster in function of great disturbance in the production is studied, contemplating the definition of the problem with proposal of process of order allocation, the construction of the model and the use of the language of Modeling GAMS to get the results of the model. Finally a case study is presented that deepens the problem of disturbance in the productive capacity and order allocation in industrial cluster of the shoes´s sector of Birigüi (SP) commanded by a mother- company; in this case, the data are collected, the results are obtained and analysed. Since this research explore an aspect important and neglected by the Operations Management literature, this research brings a contribution for this knowledge area. / Esse trabalho inicia-se contextualizando, conceituando e caracterizando aglomerados industriais nas seguintes classes: (C1) são os Aglomerados Regionais sem coordenação formal que muitos autores denominam de Distritos Industriais; (C2) tratam-se dos Consórcios para Exportação e (C3) tratam-se dos Aglomerados Comandados por Empresa-mãe. A primeira classe tem sido amplamente estudada na literatura. O grupo de pesquisa PLACOP do Departamento de Engenharia de Produção da Universidade Federal de São Carlos vem desenvolvendo pesquisas voltadas para as classes C2 e C3. É feita uma revisão literária sobre distúrbios na capacidade produtiva uma vez que esses fatores são uns dos principais problemas do sistema produtivo atual, conceituando mudança e distúrbios, analisando o impacto dos distúrbios e propondo a classificação dos tipos de distúrbios na capacidade produtiva. A seguir é revisado de forma sucinta o problema de alocação de recursos. Depois é estudado o problema de alocação de pedidos em aglomerados industriais em função de grandes distúrbios na produção, contemplando a definição do problema com proposta de processo de alocação de pedidos, a construção do modelo e o uso da linguagem de Modelagem GAMS para obter os resultados do modelo. Por fim é apresentado um estudo de caso que aprofunda o problema de distúrbios na capacidade produtiva e de alocação de pedidos em um aglomerado industrial do setor calçadista de Birigüi (SP) comandada pela empresa-mãe, com levantamento dos dados, obtenção dos resultados e avaliação dos resultados de forma a proporcionar uma contribuição para a área de Gestão da Produção, pois explora um aspecto importante e pouco explorado formalmente.

[pt] Este trabalho apresenta uma metodologia a fim de reduzir o deslocamento de candidatos em dias de prova em um exame de admissão de uma universidade no Brasil. O exame possui diferentes tipos de prova de acordo com a série do candidato e cada local de prova pode ofertar apenas um tipo de exame. A partir da teoria de localização de instalações, desenvolveu-se um modelo matemático de programação inteira para alocar candidatos de forma ótima considerando a distância entre eles e os vários locais de prova existentes. Foram realizados diversos testes com os dados de exames já aplicados, o que mostrou uma redução no deslocamento total superior a 30 porcento. Em seguida, a metodologia foi aplicada diretamente no mais recente exame de admissão da instituição, que conta com mais de 34 mil candidatos distribuídos por 70 locais de prova em 5 cidades, com a proporção de candidatos aptos a se locomoverem a pé sendo 4 vezes maior quando comparada com alocações utilizadas em anos anteriores. / [en] This work presents a methodology in order to reduce the displacement of candidates on test days in an admission exam of a university in Brazil. The exam has different types of tests according to the candidate s grade and each test site can offer only one type of exam. Based on the theory of facility location, a mathematical model of integer programming was developed to optimally allocate candidates considering the distance between them and the various existing exam locations. Several tests were carried out with the exam data already applied, which showed a reduction in total travel distance of more than 30 percent. Then, the methodology was applied directly in the most recent admission exam of the institution, which has more than 34 thousand candidates distributed over 70 exam places in 5 cities, with the proportion of candidates able to walk on foot being 4 times higher when compared to allocations used in previous years.

The increasing penetration of proactive agents in distribution systems (DS) has opened new possibilities to make the grid more resilient and to increase participation of responsive loads (RL) and non-conventional generation resources. On the resiliency side, plug-in hybrid electric vehicles (PHEV), energy storage systems (ESS), microgrids (MG), and distributed energy resources (DER), can be leveraged to restore critical load in the system when the utility system is not available for extended periods of time. Critical load restoration is a key factor to achieve a resilient distribution system. On the other hand, existing DERs and responsive loads can be coordinated in a market environment to contribute to efficiency of electricity consumption and fair electricity tariffs, incentivizing proactive agents' participation in the distribution system. Resiliency and market applications for distribution systems are highly complex decision-making problems that can be addressed using modern optimization techniques. Complexities of these problems arise from non-linear relations, integer decision variables, scalability, and asynchronous information. On the resiliency side, existing models include optimization approaches that consider system's available information and neglect asynchrony of data arrival. As a consequence, these models can lead to underutilization of critical resources during system restoration. They can also become computationally intractable for large-scale systems. In the market design problem, existing approaches are based on centralized or computational distributed approaches that are not only limited by hardware requirements but also restrictive for active participation of the market agents. In this context, the work of this dissertation results in major contributions regarding new optimization algorithms for market design and resiliency improvement in distribution systems. In the DS market side, two novel contribution are presented: 1) A computational distributed coordination framework based on bilateral transactions where social welfare is maximized, and 2) A fully decentralized transactive framework where power suppliers, in a simultaneous auction environment, strategically bid using a Markowitz portfolio optimization approach. On the resiliency side, this research proposed a system restoration approach, taking into account uncertain devices and associated asynchronous information, by means of a two-module optimization models based on binary programming and three phase unbalanced optimal power flow. Furthermore, a Reinforcement Learning (RL) method along with a Monte Carlo tree search algorithm has been proposed to solve the scalability problem for resiliency enhancement. / Doctor of Philosophy / Distribution systems (DS) are evolving from traditional centralized and fossil fuel generation resources to networks with large scale deployment of responsive loads and distributed energy resources. Optimization-based decision-making methods to improve resiliency and coordinate DS participants are required. Prohibitive costs due to extended power outages require efficient mechanisms to avoid interruption of service to critical load during catastrophic power outages. Coordination mechanisms for various generation resources and proactive loads are in great need. Existing optimization-based approaches either neglect the asynchronous nature of the information arrival or are computationally intractable for large scale system. The work of this dissertation results in major contributions regarding new optimization methods for market design, coordination of DS participants, and improvement of DS resiliency. Four contributions toward the application of optimization approaches for DS are made: 1) A distributed optimization algorithm based on decomposition and best approximation techniques to maximize social welfare in a market environment, 2) A simultaneous auction mechanism and portfolio optimization method in a fully decentralized market framework, 3) Binary programming and nonlinear unbalanced power flow, considering asynchronous information, to enhance resiliency in a DS, and 4) A reinforcement learning method together with an efficient search algorithm to support large scale resiliency improvement models incorporating asynchronous information.

Orientador: Rubén Augusto Romero Lázaro / Resumo: Neste projeto de pesquisa, é abordado o problema otimização de grade horária. O tipo de problema de grade horária abordado é aquele que tem o enunciado e a estrutura de dados apresentado no site da Competição Internacional de Otimização do Problema de Grade Horária. Esse problema pode ser modelado como sendo um problema de Programação Linear Binária de grande porte. Entretanto, os solvers comerciais disponíveis, como o CPLEX, não tem a capacidade de encontrar as soluções ótimas das 20 instâncias mostradas no site da Competição Internacional de Otimização do Problema de Grade Horária. Neste trabalho foi desenvolvido um algoritmo VNS especializado para resolver o problema de otimização de grade horária. A parcela inovadora da proposta está relacionado com o uso da lógica de partição para encontrar a melhor solução vizinha da solução corrente de forma eficiente e para uma estrutura de vizinhança complexa e formada por muitos elementos. Dessa forma, a proposta de otimização se tornou muito eficiente na resolução das 20 instâncias cujos dados se encontram no site da Competição Internacional de Otimização do Problema de Grade Horária. / Abstract: In this research project, we address the optimization timetabling problem. The type of timetabling problem addressed is one that has the statement and data structure displayed on the site of the International Competition of Optimization of the Timetabling Problem. This problem can be modeled as a large Binary Linear Programming Problem. However, the commercial solvers available, such as CPLEX, do not have the ability to nd the optimal solutions from the 20 instances shown on the site of the International Competition of Optimization of the timetabling Problem. In this work a specialized VNS algorithm was developed to solve the optimization of Timetabling Problem . The innovative part of the proposal is related to the use of partition logic to nd the best neighborhood solution of the current solution e ciently and to a structure of complex neighborhood formed by many elements. In this way, the optimization proposal became very e cient in the resolution of the 20 instances whose data were found on the website of the International Competition for Optimization of the Timetabling Problem. / Doutor