Zugl.: Erlangen, Nürnberg, University, Diss., 2008.

Thesis (M.S.)--University of North Carolina Wilmington, 2008. / Title from PDF title page (viewed September 24, 2008) Includes bibliographical references (p. 46-47)

Würzburg, Univ., Diss., 2009

Thesis (M.S.)--Montana State University--Bozeman, 2004. / Typescript. Chairperson, Graduate Committee: Brendan Mumey. Includes bibliographical references (leaves 45-47).

Techn. University, Diss., 2001-- Berlin.

Smith, T.H.C., Prof.

Neste trabalho, abordamos métodos de resolução para o problema de dimensionamento de lotes que contempla o planejamento da produção de vários produtos em múltiplas máquinas. A fabricação dos produtos consome tempo de produção e preparação de uma capacidade de produção limitada. A demanda pelos produtos é conhecida e pode ser atendida com atraso durante um horizonte de planejamento finito. O objetivo é minimizar a soma dos custos de produção, preparação para a produção, estoque dos produtos e atraso na entrega destes. Em uma primeira etapa, desenvolvemos uma busca tabu determinística baseada em outra, aleatória, que foi apresentada na literatura. Com isso, realizamos uma análise sobre a influência de fatores aleatórios sobre heurísticas do tipo busca tabu quando aplicadas ao problema estudado. Posteriormente, desenvolvemos um método híbrido baseado em busca tabu, branch-and-cut e programação linear para a resolução do problema. Nos testes computacionais realizados, o método proposto mostrou-se competitivo quando comparado a outras heurísticas apresentadas na literatura / This paper proposes two methods to solve the capacitated lot-sizing problem with multiple products and parallel machines. The manufacturing of products consumes machines capacity (production time and setup time), which is scarce. The demand for the products is known and can be met with backlogging. The objective is to minimize the sum of production, setup, holding and backlog costs. In a first step, we developed a deterministic tabu search heuristic based on a random version from the literature and then conducted an analysis of the influence of random factors on tabu search heuristics when applied to solve the studied problem. Subsequently, we designed a hybrid method based on tabu search, branch-andcut and linear programming. Computational experiments show that this hybrid method is competitive with other heuristics presented in the literature

O problema de seleção de características, no contexto de Reconhecimento de Padrões, consiste na escolha de um subconjunto X de um conjunto S de características, de tal forma que X seja \"ótimo\" dentro de algum critério. Supondo a escolha de uma função custo c apropriada, o problema de seleção de características é reduzido a um problema de busca que utiliza c para avaliar os subconjuntos de S e assim detectar um subconjunto de características ótimo. Todavia, o problema de seleção de características é NP-difícil. Na literatura existem diversos algoritmos e heurísticas propostos para abordar este problema; porém, quase nenhuma dessas técnicas explora o fato que existem funções custo cujos valores são estimados a partir de uma amostra e que descrevem uma \"curva em U\" nas cadeias do reticulado Booleano (P(S),<=), um fenômeno bem conhecido em Reconhecimento de Padrões: conforme aumenta-se o número de características consideradas, há uma queda no custo do subconjunto avaliado, até o ponto em que a limitação no número de amostras faz com que seguir adicionando características passe a aumentar o custo, devido ao aumento no erro de estimação. Em 2010, Ris e colegas propuseram um novo algoritmo para resolver esse caso particular do problema de seleção de características, que aproveita o fato de que o espaço de busca pode ser organizado como um reticulado Booleano, assim como a estrutura de curvas em U das cadeias do reticulado, para encontrar um subconjunto ótimo. Neste trabalho estudamos a estrutura do problema de minimização de funções custo cujas cadeias são decomponíveis em curvas em U (problema U-curve), provando que o mesmo é NP-difícil. Mostramos que o algoritmo de Ris e colegas possui um erro que o torna de fato sub-ótimo, e propusemos uma versão corrigida e melhorada do mesmo, o algoritmo U-Curve-Search (UCS). Apresentamos também duas variações do algoritmo UCS que controlam o espaço de busca de forma mais sistemática. Introduzimos dois novos algoritmos branch-and-bound para abordar o problema, chamados U-Curve-Branch-and-Bound (UBB) e Poset-Forest-Search (PFS). Para todos os algoritmos apresentados nesta tese, fornecemos análise de complexidade de tempo e, para alguns deles, também prova de corretude. Implementamos todos os algoritmos apresentados utilizando o arcabouço featsel, também desenvolvido neste trabalho; realizamos experimentos ótimos e sub-ótimos com instâncias de dados reais e simulados e analisamos os resultados obtidos. Por fim, propusemos um relaxamento do problema U-curve que modela alguns tipos de projeto de classificadores; também provamos que os algoritmos UCS, UBB e PFS resolvem esta versão generalizada do problema. / The feature selection problem, in the context of Pattern Recognition, consists in the choice of a subset X of a set S of features, such that X is \"optimal\" under some criterion. If we assume the choice of a proper cost function c, then the feature selection problem is reduced to a search problem, which uses c to evaluate the subsets of S, therefore finding an optimal feature subset. However, the feature selection problem is NP-hard. Although there are a myriad of algorithms and heuristics to tackle this problem in the literature, almost none of those techniques explores the fact that there are cost functions whose values are estimated from a sample and describe a \"U-shaped curve\" in the chains of the Boolean lattice o (P(S),<=), a well-known phenomenon in Pattern Recognition: for a fixed number of samples, the increase in the number of considered features may have two consequences: if the available sample is enough to a good estimation, then it should occur a reduction of the estimation error, otherwise, the lack of data induces an increase of the estimation error. In 2010, Ris et al. proposed a new algorithm to solve this particular case of the feature selection problem: their algorithm takes into account the fact that the search space may be organized as a Boolean lattice, as well as that the chains of this lattice describe a U-shaped curve, to find an optimal feature subset. In this work, we studied the structure of the minimization problem of cost functions whose chains are decomposable in U-shaped curves (the U-curve problem), and proved that this problem is actually NP-hard. We showed that the algorithm introduced by Ris et al. has an error that leads to suboptimal solutions, and proposed a corrected and improved version, the U-Curve-Search (UCS) algorithm. Moreover, to manage the search space in a more systematic way, we also presented two modifications of the UCS algorithm. We introduced two new branch-and-bound algorithms to tackle the U-curve problem, namely U-Curve-Branch-and-Bound (UBB) and Poset-Forest-Search (PFS). For each algorithm presented in this thesis, we provided time complexity analysis and, for some of them, also proof of correctness. We implemented each algorithm through the featsel framework, which was also developed in this work; we performed optimal and suboptimal experiments with instances from real and simulated data, and analyzed the results. Finally, we proposed a generalization of the U-curve problem that models some kinds of classifier design; we proved the correctness of the UCS, UBB, and PFS algorithms for this generalized version of the U-curve problem.

Neste trabalho, abordamos métodos de resolução para o problema de dimensionamento de lotes que contempla o planejamento da produção de vários produtos em múltiplas máquinas. A fabricação dos produtos consome tempo de produção e preparação de uma capacidade de produção limitada. A demanda pelos produtos é conhecida e pode ser atendida com atraso durante um horizonte de planejamento finito. O objetivo é minimizar a soma dos custos de produção, preparação para a produção, estoque dos produtos e atraso na entrega destes. Em uma primeira etapa, desenvolvemos uma busca tabu determinística baseada em outra, aleatória, que foi apresentada na literatura. Com isso, realizamos uma análise sobre a influência de fatores aleatórios sobre heurísticas do tipo busca tabu quando aplicadas ao problema estudado. Posteriormente, desenvolvemos um método híbrido baseado em busca tabu, branch-and-cut e programação linear para a resolução do problema. Nos testes computacionais realizados, o método proposto mostrou-se competitivo quando comparado a outras heurísticas apresentadas na literatura / This paper proposes two methods to solve the capacitated lot-sizing problem with multiple products and parallel machines. The manufacturing of products consumes machines capacity (production time and setup time), which is scarce. The demand for the products is known and can be met with backlogging. The objective is to minimize the sum of production, setup, holding and backlog costs. In a first step, we developed a deterministic tabu search heuristic based on a random version from the literature and then conducted an analysis of the influence of random factors on tabu search heuristics when applied to solve the studied problem. Subsequently, we designed a hybrid method based on tabu search, branch-andcut and linear programming. Computational experiments show that this hybrid method is competitive with other heuristics presented in the literature

Orientadores: Ariovaldo Verandio Garcia, Marcos Julio Rider Flores / Tese (doutorado) - Universidade Estadual de Campinas, Faculdade de Engenharia Eletrica e de Computação / Made available in DSpace on 2018-08-15T23:19:01Z (GMT). No. of bitstreams: 1 Oliveira_MarinaLavoratode_D.pdf: 1360671 bytes, checksum: e66710c118252edf8c3638375c56fdc7 (MD5) Previous issue date: 2010 / Abstract: In this work the Distribution System Integrated Planning (DSIP) problem is modeled as a mixed integer (binary) nonlinear program problem. Two techniques were investigated to solve this problem. First, a specialized Constructive Heuristic Algorithm (CHA) was implemented. A sensitivity index is used in each step of the CHA to add a circuit, a substation, a capacitor bank or a voltage regulator to the distribution system. This sensitivity index is obtained by solving the DSIP problem considering the numbers of circuits and substations to be added as continuous variables (the DSIP relaxed problem). The objective of the DSIP is to minimize the operation costs and the construction costs of circuits, substations, capacitors and voltage regulators, which are subjected to constraints of power balance, voltage magnitude, maximum circuit and substation capacities, taps control and radiality constraint. In addition, a local improvement phase to improve the initial solution of the CHA and a branching technique to avoid the infeasibility cases in the distribution system operation were included / Doutorado / Energia Eletrica / Doutor em Engenharia Elétrica