Esta tese melhora o upper bound de tempo e de espaço da resolução paralela do Subset-Sum Problem (SSP) - que é uma variante do Problema da Mochila - numa máquina PRAM SIMD CREW (Parallel Random Access Machine; Single Instruction/Multiple Data; Concurrent Read/Exclusive Write) nos dois paradigmas mais consagrados na literatura científica, isto é, tanto na abordagem através das listas como por programação dinâmica. Com relação ao primeiro paradigma, é apresentada uma paralelização ótima e adaptativa do conhecido algoritmo das duas listas de Horowitz e Sahni (JACM, 1974) numa PRAM SIMD CREW de p processadores: ela resolve o SSP de n objetos em tempo O(2n/2/p) e espaço O(2n/2), onde 1 p < 2n/2/n2. Como esse algoritmo seqüencial tem até hoje a melhor complexidade de tempo para a resolução do Problema da Mochila, então nosso algoritmo paralelo pode ser considerado, a partir de agora, como o melhor resultado teórico de toda a literatura. Além disso, são apresentados três algoritmos paralelos adaptativos baseados no paradigma da programação dinâmica, que são os primeiros a resolverem o SSP de n objetos e capacidade c em tempo o(nc/p) e espaço O(n+c) numa PRAM SIMD CREW de p processadores. Eles melhoram as complexidades de tempo e de espaço do algoritmo de Lin e Storer, (JPDC, 1991), que vinha sendo o mais eficiente até o momento.

Nesse trabalho, estudamos um problema de otimização combinatorial conhecido por Problema da Mochila Compartimentada, que é uma extensão do clássico Problema da Mochila. O problema consiste em determinar as capacidades adequadas de vários compartimentos que podem vir a ser alocados em uma mochila e como esses compartimentos devem ser carregados, respeitando as restrições de capacidades dos compartimentos e da mochila. Busca-se maximizar o valor de utilidade total. O problema é muito pouco estudado na literatura, apesar de surgir naturalmente em aplicações práticas. Nesse estudo, propomos uma modelagem matemática não linear para o problema e verificamos algumas heurísticas para sua resolução. / In this work, we studied a combinatorial optimization problem called the Clustered Knapsack Problem, that is an extension of the standard Knapsack Problem. The problem is to determine the right capacities of several clusters which can be allocated in a knapsack and how these clusters should be placed so as to respect the constraints on the capacities of the clusters and the knapsack. The objective is to maximize a total utility value. The problem has seldom been studied in the literature, even though it appears naturally in practical applications. In this study, we propose a non-linear model for the problem and we insert some heuristics for its resolution.

Orientador: Eduardo Candido Xavier / Dissertação (mestrado) - Universidade Estadual de Campinas, Insituto de Computação / Made available in DSpace on 2018-08-17T16:49:45Z (GMT). No. of bitstreams: 1 DelValle_AlineMarques_M.pdf: 1217777 bytes, checksum: 66f10d1b6b4533727cbe82431f97660d (MD5) Previous issue date: 2010 / Resumo: Nesta dissertação, estudamos problemas de empacotamento com itens irregulares. Estamos particularmente interessados no Problema da Mochila Bidimensional: dados um recipiente de tamanho W x H e uma lista de itens bidimensionais, o objetivo é empacotar um subconjunto dos itens de forma a maximizar a área dos itens empacotados. Existem diversos trabalhos que lidam com problemas para itens e recipientes bidimensionais com forma regular (retangular). No entanto, são poucos os estudos que tratam de itens com formas irregulares. Nós propomos algoritmos de empacotamento para itens irregulares em recipientes limitados baseados no uso de No-Fit-Polygon (NFP). Este trabalho apresenta uma heurística GRASP para a versão restrita do Problema da Mochila: uma solução inicial gulosa é gerada e, em seguida, utiliza-se um algoritmo de busca local para melhorar solução atual. Uma estratégia híbrida também foi proposta para versão irrestrita do Problema da Mochila. Ela divide-se em passos de empacotamento de itens irregulares e empacotamento de itens regulares. Testamos os algoritmos com instâncias adaptadas do problema de Strip Packing. O GRASP obteve empacotamentos ótimos para várias instancias testadas e, mesmo para as instâncias em que o algoritmo não obteve resultados ótimos, os empacotamentos obtidos tiveram boa taxa de ocupação, com valores relativamente próximos do ótimo. O tempo de execução do algoritmo foi razoável. Na estratégia híbrida, obtiveram-se empacotamentos bons para a maioria das instâncias, com taxa de ocupação acima de 90% e tempos de execução relativamente baixos / Abstract: In this work, we study packing problems dealing with two dimensional irregular items. We are particularly interested in the knapsack version of the problem: given a container with size W x H and a list of two dimensional items, the goal is to pack a subset of items such that the total area of packed items is maximized. There are several works that deal with problems for the case where items and containers have regular shapes (rectangular). However, only a few studies deal with items with irregular shapes. We propose algorithms for packing irregular items in limited containers based on the use of No-Fit-Polygon (NFP). This work presents a GRASP algorithm for the restricted version of the Knapsack Problem: first, a greedy initial solution is generated, then, the local search algorithm is used to improve the current solution. A hybrid strategy has also been proposed for the unrestricted version of the Knapsack Problem. It is divided into steps of packing irregular items and packing regular items. We tested the algorithms using adapted instances for the Strip Packing problem. The GRASP algorithm achieved optimal packings for several of the tested instances, and, even for those that the algorithm did not, the obtained packings had a good occupancy rate, with values relatively close to the optimum. The runtime of the algorithm was reasonable. In the hybrid strategy, we obtained good packings for most of the instances, with occupancy rates above 90% and relatively low execution times / Mestrado / Teoria da Computação / Mestre em Ciência da Computação

O objetivo deste estudo foi determinar a influência das características de três tipos de mochila através de parâmetros biomecânicos e fisiológicos selecionados. Foram voluntários 49 carteiros (30±7 anos, 1,74±0,62 m e 72,6±11,8 kg), que utilizaram 3 tipos de mochilas: mochila lateral simples (MLS), mochila lateral com cinto pélvico (MLCP) e mochila dupla com cinto pélvico (MDCP). Os sujeitos andaram durante 10 minutos sobre esteira rolante Trotter instrumentada com duas plataformas de força de reação do solo Kistler, utilizando um analisador de gases que analisou os gases expirados. As variáveis cinéticas da locomoção apresentaram diferenças significativas entre as mochilas. As variáveis cinemáticas não mostraram diferenças significativas. A ventilação apresentou diferenças entre MLCP (23,2±5,4 L · min-1) e MLS (22,5±5,0 L · min-1) e MDCP (22,3±4,8 L · min-1) e o consumo de oxigênio apresentou diferenças entre MDCP (14,6±4,1 mL · kg-1 · min-1) e MLS (15,1±3,6 mL · kg-1 · min-1) e MLCP (15,2±4,3 mL · kg-1 · min-1). Os dados dinâmicos apontaram para benefícios do uso da MLS, e os dados fisiológicos apontaram para benefícios do uso da MDCP. Embora os dados tenham apresentado diferenças estatísticas, estas não foram de magnitudes representativas, assim, a MDCP parece induzir maior demanda metabólica e a MLS menor estresse físico. / The aim of this study was to determine the influence of the satchel construction characteristics in selected biomechanical and physiological parameters during the accomplishment of the locomotion of mailmen pedestrians. 49 mailmen had been voluntary (30±7 years, 1.74±0.62 m and 72.6±11.8 kg), which had used 3 types of satchels, simple lateral satchel (MLS), lateral satchel with pelvic belt (MLCP) and double satchel with pelvic belt (MDCP). The subjects had walked 10 minutes on Trotter treadmill instrumented with two Kistler force platforms, using a gas analyzer that made analyzes of the exhaled gases. Fy1 presented differences between MLS (1.35±0.10) and MLCP (1.37±0.11) and MDCP (1.37±0.10), like others FRS parameters. The step and strike lengths had not been sensible to the different satchels. The VE presented differences between MLCP (23.2±5.4 L · min-1) and MLS (22.5± 5.0 L · min-1) and MDCP (22.7±4.8 L · min-1) and the VO2, presented differences between MDCP (14.6± .1 mL · kg-1 · min-1) and MLS (15.1±3. 6 mL · kg-1 · min-1) and MLCP (15.2±4.3 mL · kg-1 · min-1). The dynamic data had pointed to benefits using MLS, but the physiological data had indicated to benefits using MDCP. Although the data have presented statistical differences, but these had not been representative magnitudes, thus, the MDCP seems to induce bigger metabolic demand and MLS the lesser physical stress.

Submitted by Eduarda Figueiredo (eduarda.ffigueiredo@ufpe.br) on 2015-03-13T15:28:42Z No. of bitstreams: 2 Dissertação Clériston.pdf: 4465259 bytes, checksum: 1bc61d926c2cff840a99fbca45e50303 (MD5) license_rdf: 1232 bytes, checksum: 66e71c371cc565284e70f40736c94386 (MD5) / Made available in DSpace on 2015-03-13T15:28:42Z (GMT). No. of bitstreams: 2 Dissertação Clériston.pdf: 4465259 bytes, checksum: 1bc61d926c2cff840a99fbca45e50303 (MD5) license_rdf: 1232 bytes, checksum: 66e71c371cc565284e70f40736c94386 (MD5) Previous issue date: 2011-11-25 / O uso da Metodologia Seis Sigma nas organizações tornou-se economicamente viável para a maioria das empresas que buscam sustentabilidade, lucratividade e dominância no mercado competitivo. A maior parte das empresas que possuem a metodologia difundida e implementada, estão mais preocupadas com relação ao processo de seleção e priorização de projetos no Gerenciamento de Portfólios de Projetos Seis Sigma. O Processo de Seleção e Priorização de Projetos Seis Sigma é considerado uma parte crítica no Processo de Gerenciamento de Portfólios de Projetos, que de certa forma, influencia positivamente ou negativamente na estratégica da organização. A Seleção e Priorização de projetos, para a maioria das empresas, são realizadas por meio de julgamento subjetivo do decisor ou empregada de certas ferramentas que não garantem a integridade na escolha de potenciais projetos para compor a carteira de investimentos. Diante do cenário observado foi proposto um framework detalhado do Processo de Seleção e Priorização de Projetos Seis Sigma, abrangendo o PROMETHEE V, um modelo híbrido de Decisão Multicritério e Programação Combinatória Discreta. O uso do Método PROMETHEE II favoreceu uma pré – ordem completa dos projetos de forma decrescente, a partir de então, foi empregado o uso do Problema da Mochila 0 – 1, para maximizar os projetos que tenham maiores scores em certas condições de investimento e disponibilidade de recursos. Os projetos identificados são os que irão fazer parte da carteira de investimentos. A partir dos resultados obtidos na aplicação do modelo no ambiente empresarial, foi constado que o mesmo satisfaz as condições e necessidades da empresa que pretende obter o Processo de Seleção e Priorização de Projetos Seis Sigma eficiente.

Nesta tese é abordado o problema da mochila compartimentada e o problema de corte de estoque unidimensional acoplado ao problema dimensionamento de lotes. Para o problema da mochila compartimentada é apresentada a versão unidimensional e proposta a versão bidimensional, denominados como problema da mochila compartimentada unidimensional e problema da mochila compartimentada bidimensional, respectivamente. Para o problema de corte de estoque acoplado ao dimensionamento de lotes são apresentadas três variações: uma máquina para produzir um tipo de objeto; uma máquina para produzir vários tipos de objetos; múltiplas máquinas para produzir vários tipos de objetos. Algumas formulações matemáticas de programação inteira e inteira-mista, decomposições dos problemas em problema mestre e subproblemas e heurísticas baseadas no método geração de colunas são propostas para os problemas da mochila compartimenta e o problema acoplado. Em específico, para o problema acoplado são aplicadas decomposições Dantzig-Wolfe, que podem ser por período, por máquina ou por período e máquina. Além disso, uma heurística baseada em grafo E/OU é proposta para o problema da mochila compartimentada bidimensional / In this thesis we present the constrained compartmentalized knapsack problem and the one dimensional cutting stock problem integrated with the capacitated lot sizing problem. For the constrained compartmentalized knapsack problem, the one dimensional version is presented and the two dimensional version is proposed, called one-dimensional compartmentalized knapsack problem and two-dimensional compartmentalized knapsack problem, respectively. For the cutting stock problem integrated with the capacitated lot sizing problem three variations are considered: one machine to produce one type of object; one machine to produce multiple types of objects; multiple machines to produce multiple types of objects. Some integer and mixed programming formulations, decompositions of the problems in master problem and subproblems and heuristics based on column generation method are proposed for the compartmentalized knapsack problem and the cutting stock problem integrated with the capacitated lot sizing problem. In particular, the period, the machine, and the period and machine Dantzig- Wolfe decompositions are applied for the integrated problem. Moreover, a heuristic based on the graph AND/OR is proposed for the two-dimensional compartmentalized knapsack problem. Computational results show that these mathematical formulations and methods provide good solutions

Neste trabalho apresentamos dois modelos de otimização e um método heurístico de solução para tratar um problema de comprovação fiscal em exportações de commodities no Brasil. Dos modelos de otimização, um foi desenvolvido baseado no Problema de Dimensionamento de Lotes e outro no Problema da Mochila. O governo brasileiro estimula as exportações no país através de alguns benefícios fiscais, alguns desses, sendo possíveis através da comprovação fiscal das exportações de mercadorias acompanhadas de notas fiscais de tipo de operação de fim específico para a exportação. Os benefícios deixam de ser concedidos a partir da perda do prazo da comprovação fiscal da nota fiscal, que é realizado utilizando a Declaração Única de Exportação (DU-E). Cada nota fiscal possui uma data de emissão, dias de isenção fiscal, o percentual da alíquota de ICMS cobrado dependendo do estado emissor, os itens e suas quantidades. As decisões visam estabelecer as combinações de quais notas fiscais devem ser comprovadas em cada embarque de produtos para o mercado exterior, obedecendo às suas datas de isenção de modo a minimizar os impostos pagos devido aos vencimentos dos prazos de despachos das notas. Os resultados obtidos por meio do modelo matemático mostram que a política otimizada de embarque dos produtos das notas fiscais apresenta uma redução dos custos em aproximadamente 39% em determinadas situações. / In this paper we present two optimization models and a heuristic method to deal with a problem of export tax on Brazilian commodities. Regarding the optimization models, one was developed based on the lot-sizing problem and an other on the knapsack problem. The Brazilian government encourages local exportation through tax benefits, some of them being possible by the taxation of exported goods being accompanied by invoices of an operation type that is specific for the purpose of the export. These benefits cease to be granted as a result of exceeding the tax invoice verification period, which is granted using the Single Export Declaration (DU-E). Each invoice has a date issue, days of tax exemption, the percentage of the ICMS tax rate charged depending on the issuing state, the items and their quantities. The decisions aim to establish the combinations of which invoices must be presented for each shipment of products to the foreign market, obeying their exemption dates in order to minimize the taxes paid due the maturity of the delivery times on the documents. The results obtained using the mathematical model show that the optimized shipping policy for invoiced products presents a 39% reduction in costs in certain situations.

Made available in DSpace on 2016-12-12T20:22:53Z (GMT). No. of bitstreams: 1 LEANDERSON ANDRE.pdf: 2236080 bytes, checksum: a52e91a8b1a8e6a12497786254e94344 (MD5) Previous issue date: 2015-08-27 / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior / Nature offers a wide range of phenomena that inspire the development of new technologies. The researchers from the area of Natural Computing abstracts the concept of optimization from various biological processes such as the evolution of species, the behavior of social groups, the search for food, among others. Such computer systems that have a similarity to natural biological systems are called biologically plausible. The development of biologically plausible algorithms gets interesting by the fact that biological systems are able to handle extremely complex problems. In this way, symbiotic relationships are one of several phenomena that can be observed in nature. These relationships consist of interactions that organisms carry out with each other resulting in benefit or disadvantage to those involved. In an optimization context, symbiotic relationships can be used to perform exchange of information between populations of candidate solutions to a given problem. Thus, this work highlights the concepts involving symbiotic relationships that may be important for the development of computer systems to solve complex problems. The main discussion presented in this study refers to the use of symbiotic relationships between populations of candidate solutions co-evolving in an ecological context. According to the analogy, populations interact with each other according to a specific symbiotic relationship in order to evolve their solutions. The proposed model is applied to several continuous benchmark functions with a high number of dimensions (D = 200) and in several benchmark instances of the multiple knapsack problem. The results obtained so far were promising concerning the application of symbiotic relationships. Finally, the conclusions are presented and some future directions for research are suggested. / A Natureza apresenta uma grande variedade de fenômenos que inspiram o desenvolvimento de novas tecnologias. Os pesquisadores da área de Computação Natural abstraem o conceito de otimização de vários processos biológicos, tais como a evolução das espécies, comportamento de grupos sociais, busca por comida, dentre outros. Tais sistemas computacionais que apresentam uma semelhança com os sistemas biológicos naturais são chamados de biologicamente plausíveis. O desenvolvimento de algoritmos biologicamente plausíveis se torna interessante pelo fato de que os sistemas biológicos são capazes de lidar com problemas extremamente complexos. As relações simbióticas são um dos vários fenômenos que podem ser observados na natureza. Essas relações consistem de interações que organismos realizam entre si resultando em benefícios ou prejuízos para os envolvidos. Em um contexto de otimização, as relações simbióticas podem ser utilizadas para realizar a troca de informação entre populações de soluções candidatas para um dado problema. Desta forma, este trabalho destaca os conceitos que envolvem as relações simbióticas que podem ser importantes para o desenvolvimento de sistemas computacionais para a resolução de problemas complexos. A principal discussão apresentada nesse trabalho refere-se a utilização de relações simbióticas entre populações de soluções candidatas, coevoluindo em um contexto ecológico. Com essa analogia, cada população interage com uma outra de acordo com uma relação simbiótica específica, com o objetivo de evoluir suas soluções. O modelo apresentado é aplicado a várias funções benchmark contínuas com um número alto de dimensões (D = 200) e várias instâncias benchmark do problema da mochila múltipla. Os resultados obtidos se mostraram promissores considerando a aplicação das relações simbióticas. Por fim, as conclusões são apresentadas e algumas direções para pesquisas futuras são sugeridas.

Nesta tese é abordado o problema da mochila compartimentada e o problema de corte de estoque unidimensional acoplado ao problema dimensionamento de lotes. Para o problema da mochila compartimentada é apresentada a versão unidimensional e proposta a versão bidimensional, denominados como problema da mochila compartimentada unidimensional e problema da mochila compartimentada bidimensional, respectivamente. Para o problema de corte de estoque acoplado ao dimensionamento de lotes são apresentadas três variações: uma máquina para produzir um tipo de objeto; uma máquina para produzir vários tipos de objetos; múltiplas máquinas para produzir vários tipos de objetos. Algumas formulações matemáticas de programação inteira e inteira-mista, decomposições dos problemas em problema mestre e subproblemas e heurísticas baseadas no método geração de colunas são propostas para os problemas da mochila compartimenta e o problema acoplado. Em específico, para o problema acoplado são aplicadas decomposições Dantzig-Wolfe, que podem ser por período, por máquina ou por período e máquina. Além disso, uma heurística baseada em grafo E/OU é proposta para o problema da mochila compartimentada bidimensional / In this thesis we present the constrained compartmentalized knapsack problem and the one dimensional cutting stock problem integrated with the capacitated lot sizing problem. For the constrained compartmentalized knapsack problem, the one dimensional version is presented and the two dimensional version is proposed, called one-dimensional compartmentalized knapsack problem and two-dimensional compartmentalized knapsack problem, respectively. For the cutting stock problem integrated with the capacitated lot sizing problem three variations are considered: one machine to produce one type of object; one machine to produce multiple types of objects; multiple machines to produce multiple types of objects. Some integer and mixed programming formulations, decompositions of the problems in master problem and subproblems and heuristics based on column generation method are proposed for the compartmentalized knapsack problem and the cutting stock problem integrated with the capacitated lot sizing problem. In particular, the period, the machine, and the period and machine Dantzig- Wolfe decompositions are applied for the integrated problem. Moreover, a heuristic based on the graph AND/OR is proposed for the two-dimensional compartmentalized knapsack problem. Computational results show that these mathematical formulations and methods provide good solutions

[pt] Um importante ramo do estudo de logística é aquele que se preocupa com a otimização da eficiência do uso de recursos de transporte. No segmento de aviação da Petrobras, que transporta cerca de 20 por cento de todos os passageiros offshore do planeta, otimizações são bastante significativas e podem gerar importantes benefícios econômicos (menor custo total), logísticos (maior disponibilidade de recursos), ambientais (menores emissões de gases poluentes) e de segurança (menor exposição aos riscos da atividade). Por estes motivos, é imperativo que se busque formas de aumentar a eficiência do uso das aeronaves contratadas, maximizando sua utilização dentro de limites permitidos por normas de voo offshore, limites de fadiga de tripulantes, limites operacionais dos aeroportos de origem e destino, além de limites de capacidades de cada aeronave. Neste sentido, o objetivo deste estudo é apresentar o desenvolvimento de soluções para redução dos custos da operação aérea, buscando o máximo aproveitamento das aeronaves contratadas, a partir de uma proposta de otimização da programação de voos através da resolução de um resolução de uma formulação de Programação Linear Inteira, que estende um Problema de Múltiplas Mochilas, respeitando as limitações impostas por regulamentação e necessidades operacionais. Foi desenvolvida uma ferramenta computacional e os resultados obtidos a partir deste trabalho foram implementados nas operações da Petrobras e fazem parte do Plano de Resiliência desta empresa. Os ganhos econômicos obtidos representam uma redução de 100 milhões de reais no quinquênio do Plano de Negócios e Gestão 2020-2024, o que comprova o benefício das soluções implementadas. / [en] An important field of the logistics study is one that is concerned with optimizing the efficiency of the use of transport resources. In Petrobras aviation segment, which transports about 20 percent of all offshore passengers worldwide, optimizations are quite significant and can generate important economic (lower total cost), logistical (increased availability of resources), environmental (lower emissions of polluting gases) and safety (reduced exposure to the risks of the activity) benefits. For these reasons, it is imperative to seek ways to increase efficiency in the use of contracted aircrafts, maximizing their use within the boundaries imposed by offshore flight rules, crew fatigue restrictions, operational restrictions of the origin and destination airports, in addition to capacity limits for each aircraft. Hereupon, the objective of this study is to present the development of solutions to reduce the costs of aerial operation, seeking the maximum use of contracted aircrafts, based on a proposal to optimize the flight schedule through the resolution of an Integer Linear Programming formulation that extends a Multiple Knapsack Problem, but within the boundaries imposed by regulations and operational needs. A computational tool was developed and results obtained from this work were implemented in Petrobras operations, and are part of this company s Resilience Plan. The economic gains obtained represent a reduction of USD 27 million in the five-year period of the 2020-2024 Business Plan, which proves the benefit of the implemented solutions.