Thesis (M.S.)--Virginia Polytechnic Institute and State University, 1993. / Vita. Abstract. Includes bibliographical references (leaves 92-97). Also available via the Internet.

Thesis (Ph. D.)--University of Wisconsin--Madison, 1981. / Vita. eContent provider-neutral record in process. Description based on print version record. Includes bibliographical references (leaves 117-121).

Thesis (Ph. D.)--University of Wisconsin--Madison, 1970. / Typescript. Vita. eContent provider-neutral record in process. Description based on print version record. Includes bibliographical references.

Typescript. Includes bibliographical references.

Thesis (Ph. D.)--University of Texas at Austin, 2008. / Vita. Includes bibliographical references.

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.

This article studies the linear multicommodity network flow problem. This kind of problem arises in a wide variety of contexts. A numerical implementation of the primal-dual interior-point method is designed to solve the problem. In the interior-point method, at each iteration, the corresponding linear system, expressed as a normal equations system, is solved by using the AINV algorithm combined with a preconditioned conjugate gradient algorithm or by the AINV algorithm for the whole normal equations. Numerical experiments are conducted for networks of different dimensions and numbers of products for the distribution problem. The computational results show the effectiveness of the interior-point method for this class of network problems.

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.