Mgr. Tomáš Ebenlendr Combinatorial algorithms for online problems: Semi-online scheduling on related machines Abstract of doctoral thesis We construct a framework that gives optimal algorithms for a whole class of scheduling problems. This class covers the most studied semi-online variants of preemptive online scheduling on uniformly related machines with the objective to minimize makespan. The algorithms from our framework are deterministic, yet they are optimal even among all randomized algorithms. In addition, they are optimal for any fixed combination of speeds of the machines, and thus our results subsume all the previous work on various special cases. We provide new lower bound of 2.112 for the original online problem. The (deterministic) upper bound is e ≈ 2.718 as there was known e-competitive randomized algorithm before. Our framework applies to all semi-online variants which are based on some knowledge about the input sequence. I.e., they are restrictions of the set of valid inputs. We use our framework to study restrictions that were studied before, and we derive some new bounds. Namely we study known sum of processing times, known maximal processing time, sorted (decreasing) jobs, tightly grouped processing times, approximately known optimal makespan and few combinations. Based on the analysis...

Made available in DSpace on 2015-08-20T17:09:32Z (GMT). No. of bitstreams: 0 Previous issue date: 2014-11-11. Added 1 bitstream(s) on 2015-08-20T17:26:54Z : No. of bitstreams: 1 000846221.pdf: 1635996 bytes, checksum: 3433248530a7bdc61a9bdbec1086772b (MD5) / A geração eficiente de implicantes primos é um fator importante na fase de cobertura dos mintermos em métodos de minimização de funções booleanas. Este trabalho apresenta uma versão aprimorada do método denominado de Clause-Column Table, utilizado na geração de implicantes primos. Neste novo algoritmo adicionou-se o teorema da adjacência e um novo critério de parada. Estas modificações evitaram a geração de termos nulos e iterações desnecessárias que ocorriam no algoritmo original. O algoritmo original e o aprimorado foram implementados em linguagem C e comparados. O método Clause-Column Table Aprimorado também foi comparado com o método Quine-McCluskey e Expander. Os resultados comprovaram que a versão aprimorada gera menos iterações que a versão original, e que na maioria das funções analisadas evitou-se a geração de termos nulos. Ao comparar com o método de Quine-McCluskey e o Expander comprovou-se que o método Clause-Column Table Aprimorado é superior na geração dos implicantes primos, pois em alguns casos elimina aqueles que não são necessários para a cobertura da função. De posse dos implicantes primos o problema de cobertura dos mintermos foi formulado como um problema de programação linear inteira 0 e 1, em que a solução se abre a todos os avanços ocorridos na área de programação linear visando a obtenção de uma solução mínima / Efficient generation of prime implicants is an important factor in the coverage phase of minterms in minimization's methods of Boolean functions. This research presents an improved version of the method called Clause-Column Table, used to generate prime implicants. In this new algorithm was added to the adjacency theorem and a new stopping criterion. These modifications prevented the generation of null terms and unnecessary iterations that occurred in the original algorithm. The original and improved algorithms were implemented in C language and compared. The Clause-Column Table Improved method was compared with the Expander and Quine-McCluskey method. The results proved that the improved version generates fewer iterations than the original version, and that in most functions analyzed it was avoided the generation of null terms. Comparing Quine-McCluskey method and the Expander it was proved that the Clause-Column Table Enhanced method is superior in the generation of prime implicants, since in some cases eliminates those who are not required to cover the function. In ownership of the prime implicants the cover problem of minterms was formulated as an integer linear programming problem of 0 and 1, where the solution is open to all advances in the area of linear programming in order to obtain a minimal solution

Determinar probabilidades para eventos no qual temos poucas informações ou intervalos para probabilidades não é tão simples. Para isso desenvolveremos conceitos de programação linear, que nos permite resolver de certo modo, o problema de determinar uma probabilidade para um evento de interesse, porém nem sempre de maneira única. Apresentaremos alguns exemplos clássicos da estatística, sendo eles: O Problema de Monty Hall e o Problema da Probabilidade do Testemunho. Além disso, discutiremos o problema de precificação de uma opção de compra, o quais utilizaremos programação linear para resolvê-los. / Determine probabilities for events where we have few information or intervals for probabilities is not so simple. For this we will develop concepts of linear programming, which allows us to solve, in a certain way, the problem of determine a probability for an event of interest, but not always in a unique way. We will present some classic examples of statistics, such as: The Monty Hall Problem and De La Probabilité Des Témoignages. In addition, we will discuss the problem of pricing a call option, where we will use linear programming to solve them.

Para uma empresa de navegação, manter uma frota grande de contêineres próprios poderia gerar custos desnecessários para manutenção dos estoques destes contêineres; contudo, se a frota de contêineres próprios for pequena, poderia resultar em um número grande de contêineres arrendados a curto prazo. Assim, nesta dissertação desenvolve-se um modelo de programação linear capaz de estimar a frota ótima de contêineres próprios e alugados, que envolve a dificuldade da tomada de decisão em um comércio extremamente desequilibrado. A revisão bibliográfica apresenta poucas publicações que tratam do tema proposto. O trabalho desenvolvido por Imai e Rivera (2001) é examinado por ser mais semelhante ao tema proposto para esta dissertação. Por tratarem do dimensionamento de frota de contêineres para dois portos e não admitirem aleatoriedades nos tempos de movimentação terrestre de contêineres outros procedimentos foram examinados. Para tentar solucionar o problema de dimensionamento de frota de contêineres próprios para a empresa de navegação dois métodos são analisados: modelo de simulação probabilística e modelo de programação linear. O modelo de simulação é desenvolvido para um problema pequeno. Conforme a ampliação deste modelo e o aumento do número de variáveis, o modelo de simulação passou a ser difícil de ser controlado, pois a mudança dos valores destas variáveis se tornaria muito difícil. O modelo de programação linear é desenvolvido com base nas características e definições adotadas para o modelo de simulação. Este modelo matemático incorpora as aleatoriedades existentes nos processos terrestres, de acordo com as hipóteses adotadas. Este modelo permite auxiliar o planejador a tomar decisões estratégicas, com relação ao tamanho da frota de contêineres necessários para atender a demanda de transporte ao longo do horizonte de planejamento, e operacionais, por apresentar o fluxo de transporte de contêineres vazios entre portos, bem como a quantidade de contêineres alugados, se necessários, para realizar as operações emergenciais associadas a picos de demanda ao longo do período de planejamento. Para testar a consistência do modelo, cenários hipotéticos foram gerados. Por meio dos resultados obtidos para estes cenários, mostra-se a relação do custo dos contêineres alugados e do custo do transporte de contêineres próprios vazios sobre o tamanho da frota de contêineres próprios. / For a carrier, provide a large fleet of owned containers could generate unnecessary costs for maintenance of their inventories; however, if the fleet of owned containers is small, it might result in a large number of short-term leased containers. Thus, it is developed a linear programming model capable to determine the optimal fleet size of owned and leased containers that involves the difficulty of decision-making in an extremely unbalanced trade. The literature survey presents few publications that deal with the considered subject. The work developed for Imai and Rivera (2001) is examined by being more similar to the subject considered in this project. For dealing with the container fleet sizing for two ports and not admitting stochastic travel times inland of containers other procedures are examined. To solve the problem of own container fleet sizing for the carriers two methods are analyzed: probabilistic simulation model and linear programming model. The simulation model is developed for a small problem. As the growing of this model and the increase of the number of variables, the simulation model becomes difficult to control, because the change of the values of these variables would become very hard. The linear programming model is developed on the basis of the characteristics and definitions adopted for the simulation model. This mathematical model incorporates the existing stochastic inland times, in accordance with the adopted hypotheses. This model allows to assist the planner to make strategical decisions, with regard to the size of the fleet of containers necessary to attempt the demand of transport throughout the planning horizon, and operational, for presenting the flow of empty cont ainers between ports, as well as the amount of leased containers, if necessary, to carry through the special operations associated the peaks of demand throughout the period of planning. To test the consistency of the model, hypothetical scenes had been generated. By the results gotten for these scenes, it is showed the relation of the cost of leases containers and the cost of the transport of empty owned containers above the owned container fleet size.

Orientador: Maria Aparecida Diniz Ehrhardt / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Matematica, Estatistica e Computação Cientifica / Made available in DSpace on 2018-08-10T01:30:21Z (GMT). No. of bitstreams: 1 Lammoglia_Bruna_M.pdf: 679586 bytes, checksum: 221fa89afc7d9f594781baed1dfe6b0e (MD5) Previous issue date: 2007 / Resumo: Neste trabalho o objetivo principal foi a minimização de quadráticas em caixas. Dissertamos sobre os métodos de máxima descida e dos gradientes conjugados, bem como sobre um método mais recente denominado gradiente espectral. O GENCAN, um algoritmo que minimiza funções em caixas, foi estudado em detalhe, particularmente avaliando sua aplicação para quadráticas. O objetivo foi analisar o desempenho do GENCAN, comparado com algoritmos anteriores, como o LANCELOT e o QUACAN. Foram executados experimentos numéricos a fim de avaliar o desempenho das versões de GENCAN sem e com pré-condicionamento. Concluiu-se que pré-condicionar o método dos gradientes conjugados neste caso tornou o GENCAN mais robusto. No entanto, o pré-condicionador usado neste software mostrou-se computacionalmente caro. Em relação à comparação do GENCAN, LANCELOT e QUACÁN, podemos afirmar que o GENCAN. mostrou-se competitivo / Abstract: The focus of this work was the minimization of quadratic functions with box constraints. We were mainly concerned about the steepest descent and conjugated gradient methods, besides a more recent approach called spectral gradient method. The GENCAN, an algorithm that minimizes functions on a box, was studied in details particularly evaluating this algorithm applied to quadratics. The objective was to analyze the efficiency of GENCAN, comparing it to classical algorithms, such as LANCELOT and QUACAN. We executed numerical experiments in order to investigate the efficiency of GENCAN version with and without preconditioning. Evaluating the results we concluded that preconditioning the conjugated gradient method makes the GENCAN work considerably better; despite the fact that the preconditioner used here turned the computational process more expensive. Comparing GENCA'N, LANCELOT, and QUACAN we can state that GENCAN is competitive / Mestrado / Otimização / Mestre em Matemática Aplicada

Orientador: Marcius Fabius Henriques Carvalho / Dissertação (mestrado) - Universidade Estadual de Campinas, Faculdade de Engenharia Mecânica / Made available in DSpace on 2018-08-17T00:35:22Z (GMT). No. of bitstreams: 1 Pupulin_RicardoPereira_M.pdf: 3494242 bytes, checksum: 2563e0723dce908c7d4957a80a14d641 (MD5) Previous issue date: 2010 / Resumo: Este trabalho tem como objetivo encontrar a melhor programação de colheita para a usina de cana-de-açúcar em estudo. Foram desenvolvidos modelos com base em programação linear que representem o melhor mix varietal do canavial, a melhor programação de colheita com as variedades existentes e o pior cenário, este desenvolvido para quantificar a produção real percebida no período. Estes modelos foram feitos com os rendimentos das variedades divididos em dois grupos que seriam os modelos com base de dados no histórico de colheita e os modelos com base na safra de 08/09 / Abstract: The main purpose of this project is to find the best harvest scheduling program to sugar cane. Models were developed with a linear programming that represent the best variety mix for the reed, the best harvest program with the current sugar cane varieties and the worst scenario, this was done to qualify the real production perceived at the period. These models were done with the varieties income shared in two groups that would be the models based on the harvest historic and the models based on the 08/09 crop / Mestrado / Materiais e Processos de Fabricação / Mestre em Engenharia Mecânica

Orientador: Valéria Abrão de Podestá / Dissertação (mestrado profissional) - Universidade Estadual de Campinas, Instituto de Matemática, Estatística e Computação Científica / Made available in DSpace on 2018-08-16T01:49:31Z (GMT). No. of bitstreams: 1 Trevisan_EbersonPaulo_M.pdf: 1587820 bytes, checksum: 334e76317d2424126dd4bb1fb621c7e4 (MD5) Previous issue date: 2010 / Resumo: Neste trabalho são apresentados alguns assuntos iniciais da teoria de Programação Linear e o método Simplex. Mostramos também como a Programação Linear pode ser utilizada na separação de dois conjuntos de pontos (padrões), através de um modelo linear cuja solução é um hiperplano separador. Finalizamos o trabalho com a apresentação de alguns exemplos de aplicação da Programação Linear na separação de dois conjuntos linearmente separáveis e linearmente inseparáveis / Abstract: In this work we present some introductory issues from Linear Programming theory and the Simplex method. We also show how we can use Linear Programming in two patterns separation by constructing a linear model which solution is a separating hyperplane. Finaly, we also present some examples of Linear Programming application in the linear separability and inseparability of two patterns sets / Mestrado / Programação Linear / Mestre em Matemática

In this work we propose a flexible numerical approach to deal with models of dynamic moral hazard with simultaneous learning about the production function. Because of the complexity of the problem, analytical solutions have so far been limited in scope. The contribution is methodological: through computation, the problem can be studied under few assumptions about functional forms. We depart from a general mechanism, reformulate it as an incentive compatible mechanism, and show how it can be solved by backward induction through a sequence of linear programs. We apply our method to a few cases of interest, and confirm that uncertainty about the production function increases the volatility of the agent\'s utility in order to prevent belief manipulation, as found in the literature. / Neste trabalho, propomos uma estratégia numérica para lidar com modelos de risco moral dinâmico com aprendizado sobre a função de produção. Pela complexidade do problema, soluções analíticas na literatura têm sido limitadas em seu escopo. Nossa contribuição é metodológica: através de métodos computacionais, o problema pode ser estudado sob poucas hipóteses a respeito de formas funcionais. Partindo de um mecanismo geral, reformulamos o problema como um mecanismo compatível em incentivos, e então mostramos como este pode ser resolvido por indução retroativa por meio de uma sequência de programas lineares. Aplicamos o método a alguns casos de interesse, e confirmamos a conclusão da literatura de que a incerteza sobre a função de produção aumenta a volatilidade da utilidade do agente para prevenir manipulação de crenças.

This thesis project will attempt to answer the question if it is possible to gain performance by using SIMD instructions when generating code for scalar computation. The current trend in processor architecture is to equip the processors with multi-way SIMD units to form so-called throughput cores. This project uses the CELL SPE processor for a concrete implementation. To get good code quality the thesis project continues work on the code generator by Mattias Eriksson and Andrzej Bednarski based on integer linear programming. The code generator is extended to handle generation of SIMD code for 32bit operands. The result show for some basic blocks, positive impact in execution time of the generated schedule. However, further work has to be done to get a feasable run time of the code generator.

The school's schedule involves folding lessons within five working days, so that in each class were taught subjects required by the school curriculum in the correct number of hours and for each hour was assigned a teacher and a number of classrooms in which teaching will be realized. However, it is necessary to keep order in the resulting schedule avoid collision or vice versa unnecessary delays in the schedules of students and teachers in order to meet the conditions laid down by legislation and at the same time it was granted as much as possible the requirements of the management, teachers, or students or their parents. In this study it is proposed a mathematical model for the formation of a high school schedule that was created with the help of MPL for Windows and data provided by Gymnázium Chomutov.