Esta tese integra dois problemas de áreas distintas e interdependentes intitulados de Sequenciamento Otimizado de Faturamento (SOF) e Sequenciamento Otimizado de Coleta (SOC). Abordados de forma disjunta pelos pesquisadores, o SOF refere-se a um problema de maximização do faturamento e o SOC consiste de uma variação do Order Batching and Sequencing Problem (OBSP). Fundamentados por pressupostos práticos e científicos, o SOF/SOC retratam o cotidiano dos processos de faturamento e picking de um típico Armazém de Distribuição (AM). No SOF a demanda é estocástica e os faturamentos ocorrem a partir de janelas de tempo variáveis ajustadas para evitar o tardiness mediante a priorização das datas de atendimento pela regra Earliest Due Date (EDD). No SOC o picking é manual e enquadra-se na categoria picker-to-parts (low level) com pick-and-sort utilizando um trolley que é transportado pelo operador ao longo das ruas do AM. Neste contexto, esta tese tem como objetivo desenvolver uma ferramenta de gestão que integre e apresente soluções otimizadas para o SOF/SOC. A perspectiva de integração do SOF/SOC dar-se-á mediante à formulação de dois Algoritmos Genéticos (AGs) nomeados de AG-SOF e AG-SOC. Assim, o enfoque desta pesquisa está na avaliação da eficácia prática do AG-SOF/AG-SOC em resolver problemas reais do SOF/SOC. A eficácia do AG-SOF é comparada à um Algoritmo Guloso Iterativo (AI-SOF) enquanto que a predileção pelo AG-SOC é justificada pela natureza NP-hard do SOC. As experimentações para problemas de diferentes níveis de complexidade demonstraram que os algoritmos satisfazem todas as regras, restrições e variáveis decisórias obtendo soluções de qualidade satisfatória para qualquer categoria do SOF/SOC. O AISOF/ AG-SOF lidam com as restrições de estoque e as possibilidades de faturar pedidos parciais para maximizar o Faturamento Total (FT). Apesar de obterem soluções com a mesma qualidade, o AI-SOF tem desempenho superior ao AG-SOF que é, em termos de Tempo de Processamento Computacional (TPC), limitado às categorias de médio porte do SOF. O AG-SOC é composto pela iteração de dois AGs (AGLOTE e AGPCV) que minimizam o Custo Total das Operações de Picking (CT). Logo, o AGLOTE agrupa os SKUs (Stock Keeping Units) dos diferentes pedidos em múltiplos lotes pela restrição de carga dos trolleys de forma a reduzir o Número de Viagens de Coleta (NVC) e define a sequência de coleta por meio de lotes prioritários para evitar o Atraso no Atendimento dos Pedidos (AAP). O AGPCV faz a roteirização dos lotes dentro do AM de modo que impeça a ocorrência de avarias aos SKUs frágeis e minimize a Distância Total das Rotas (DTR) e o Tempo Total de Picking (TTP). Evidenciou-se que para problemas de complexidade superior os lotes são mais homogêneos, nos quais o Desvio Padrão é pequeno e o Coeficiente de Variação é de 11,22% a 25,20% para a DTR. Para ambientes reais em que se utiliza janelas de tempo e logs de processamentos para lotes off-lines) a combinação do AI-SOF/AGSOC provê soluções otimizadas em tempo e qualidade satisfatória ao SOF/SOC. Em suma, esta pesquisa foi além das abordagens existentes para preencher um gap na literatura e prover uma importante contribuição à prática da otimização do SOF/SOC. É possível conclui que a integração do AI-SOF/AGSOC é capaz de maximizar o faturamento e melhorar a produtividade de forma a minimizar os tempos e custos operacionais de picking do AM. / This thesis integrates two problems from distinct and independent areas called Optimal Sequencing Billing (OSB) and Optimal Picking Sequencing (OPS). Studied separately by researchers, OBS refers to a billing maximization problem and OPS is a variation of the Order Batching and Sequencing Problem (OBSP). Based on practical and scientific assumptions, OSB/OPS portray the picking daily routine in a typical Distribution Warehouse (WA). In OSB, the demand is stochastic and billings occur based on variables time windows that are adjusted to avoid tardiness by prioritizing the service dates based on the Earliest Due Date (EDD) rule. In OPS, picking is manual and falls into the low-level picker-to-parts category, and it uses a trolley that is pushed by an employee along WA aisles. In this context, this thesis has the objective of developing a management tool that can integrate and provide optimal solutions for OSB/OPS. The perspective of integrating OSB/OPS can be achieved through the formulation of two Genetic Algorithms (GAs) called GA-OSB and GA-OPS. Therefore, the focus of this research is to assess GA-OSB/GA-OPS practical efficiency to solve actual OSB/OPS problems. GA-OSB efficiency is compared to an Iterative Greedy Algorithm (IA-OSB) whereas the preference for GA-OPS is justified by the NP-hard nature of OPS. Experiments for problems of different complexity levels showed that algorithms satisfy every rule, restriction and decision variable and provide satisfactory solutions for any OSB/OPS category. IA-OSB/GA-OSB deal with inventory restrictions and the possibility of billing partial orders to maximize Total Billing (TB). Although they also provide quality solutions, IA-OSB performance is better than GA-OSB performance which is limited to OSB medium-sized categories in terms of Computational Processing Time (CPT). GA-OPS comprises the iteration of two GAs (GABATCH and GATSP) that minimize the Total Cost of Picking Operations (TC). Therefore, GABATCH groups SKUs (Stock Keeping Units) of different orders into multiple lots according to trolley load restrictions so as to reduce the Number of Picking Travels (NPT). It also defines a picking sequence by means of priority lots to avoid Tardiness in Customer Orders (TCO). GATSP maps out the routes of lots inside the WA in order to prevent damages to fragile SKUs and to minimize Total Route Distance (TRD) as well as Total Picking Time (TPT). It was evidenced that, for problems of higher complexity, lots are more homogeneous where the Standard Deviation is small and the Coefficient of Variation (CV) ranges from 11.22% to 25.20% to the TRD. For actual environments where time windows and processing logs are used for off-line lots, the IA-OSB/GA-OPS integration provides optimal time solutions and satisfactory quality to OSB/OPS. In short, this research has gone beyond existing approaches to fill a gap in the literature and provide an important contribution to the practice of optimal OSB/OPS. It can be concluded that the integration of IA-OSB/GA-OPS can maximize billing and improve productivity in order to minimize picking operational time and costs in a WA.

Tese de mestrado integrado. Engenharia Informática e Computação. Faculdade de Engenharia. Universidade do Porto. 2012

Esta tese integra dois problemas de áreas distintas e interdependentes intitulados de Sequenciamento Otimizado de Faturamento (SOF) e Sequenciamento Otimizado de Coleta (SOC). Abordados de forma disjunta pelos pesquisadores, o SOF refere-se a um problema de maximização do faturamento e o SOC consiste de uma variação do Order Batching and Sequencing Problem (OBSP). Fundamentados por pressupostos práticos e científicos, o SOF/SOC retratam o cotidiano dos processos de faturamento e picking de um típico Armazém de Distribuição (AM). No SOF a demanda é estocástica e os faturamentos ocorrem a partir de janelas de tempo variáveis ajustadas para evitar o tardiness mediante a priorização das datas de atendimento pela regra Earliest Due Date (EDD). No SOC o picking é manual e enquadra-se na categoria picker-to-parts (low level) com pick-and-sort utilizando um trolley que é transportado pelo operador ao longo das ruas do AM. Neste contexto, esta tese tem como objetivo desenvolver uma ferramenta de gestão que integre e apresente soluções otimizadas para o SOF/SOC. A perspectiva de integração do SOF/SOC dar-se-á mediante à formulação de dois Algoritmos Genéticos (AGs) nomeados de AG-SOF e AG-SOC. Assim, o enfoque desta pesquisa está na avaliação da eficácia prática do AG-SOF/AG-SOC em resolver problemas reais do SOF/SOC. A eficácia do AG-SOF é comparada à um Algoritmo Guloso Iterativo (AI-SOF) enquanto que a predileção pelo AG-SOC é justificada pela natureza NP-hard do SOC. As experimentações para problemas de diferentes níveis de complexidade demonstraram que os algoritmos satisfazem todas as regras, restrições e variáveis decisórias obtendo soluções de qualidade satisfatória para qualquer categoria do SOF/SOC. O AISOF/ AG-SOF lidam com as restrições de estoque e as possibilidades de faturar pedidos parciais para maximizar o Faturamento Total (FT). Apesar de obterem soluções com a mesma qualidade, o AI-SOF tem desempenho superior ao AG-SOF que é, em termos de Tempo de Processamento Computacional (TPC), limitado às categorias de médio porte do SOF. O AG-SOC é composto pela iteração de dois AGs (AGLOTE e AGPCV) que minimizam o Custo Total das Operações de Picking (CT). Logo, o AGLOTE agrupa os SKUs (Stock Keeping Units) dos diferentes pedidos em múltiplos lotes pela restrição de carga dos trolleys de forma a reduzir o Número de Viagens de Coleta (NVC) e define a sequência de coleta por meio de lotes prioritários para evitar o Atraso no Atendimento dos Pedidos (AAP). O AGPCV faz a roteirização dos lotes dentro do AM de modo que impeça a ocorrência de avarias aos SKUs frágeis e minimize a Distância Total das Rotas (DTR) e o Tempo Total de Picking (TTP). Evidenciou-se que para problemas de complexidade superior os lotes são mais homogêneos, nos quais o Desvio Padrão é pequeno e o Coeficiente de Variação é de 11,22% a 25,20% para a DTR. Para ambientes reais em que se utiliza janelas de tempo e logs de processamentos para lotes off-lines) a combinação do AI-SOF/AGSOC provê soluções otimizadas em tempo e qualidade satisfatória ao SOF/SOC. Em suma, esta pesquisa foi além das abordagens existentes para preencher um gap na literatura e prover uma importante contribuição à prática da otimização do SOF/SOC. É possível conclui que a integração do AI-SOF/AGSOC é capaz de maximizar o faturamento e melhorar a produtividade de forma a minimizar os tempos e custos operacionais de picking do AM. / This thesis integrates two problems from distinct and independent areas called Optimal Sequencing Billing (OSB) and Optimal Picking Sequencing (OPS). Studied separately by researchers, OBS refers to a billing maximization problem and OPS is a variation of the Order Batching and Sequencing Problem (OBSP). Based on practical and scientific assumptions, OSB/OPS portray the picking daily routine in a typical Distribution Warehouse (WA). In OSB, the demand is stochastic and billings occur based on variables time windows that are adjusted to avoid tardiness by prioritizing the service dates based on the Earliest Due Date (EDD) rule. In OPS, picking is manual and falls into the low-level picker-to-parts category, and it uses a trolley that is pushed by an employee along WA aisles. In this context, this thesis has the objective of developing a management tool that can integrate and provide optimal solutions for OSB/OPS. The perspective of integrating OSB/OPS can be achieved through the formulation of two Genetic Algorithms (GAs) called GA-OSB and GA-OPS. Therefore, the focus of this research is to assess GA-OSB/GA-OPS practical efficiency to solve actual OSB/OPS problems. GA-OSB efficiency is compared to an Iterative Greedy Algorithm (IA-OSB) whereas the preference for GA-OPS is justified by the NP-hard nature of OPS. Experiments for problems of different complexity levels showed that algorithms satisfy every rule, restriction and decision variable and provide satisfactory solutions for any OSB/OPS category. IA-OSB/GA-OSB deal with inventory restrictions and the possibility of billing partial orders to maximize Total Billing (TB). Although they also provide quality solutions, IA-OSB performance is better than GA-OSB performance which is limited to OSB medium-sized categories in terms of Computational Processing Time (CPT). GA-OPS comprises the iteration of two GAs (GABATCH and GATSP) that minimize the Total Cost of Picking Operations (TC). Therefore, GABATCH groups SKUs (Stock Keeping Units) of different orders into multiple lots according to trolley load restrictions so as to reduce the Number of Picking Travels (NPT). It also defines a picking sequence by means of priority lots to avoid Tardiness in Customer Orders (TCO). GATSP maps out the routes of lots inside the WA in order to prevent damages to fragile SKUs and to minimize Total Route Distance (TRD) as well as Total Picking Time (TPT). It was evidenced that, for problems of higher complexity, lots are more homogeneous where the Standard Deviation is small and the Coefficient of Variation (CV) ranges from 11.22% to 25.20% to the TRD. For actual environments where time windows and processing logs are used for off-line lots, the IA-OSB/GA-OPS integration provides optimal time solutions and satisfactory quality to OSB/OPS. In short, this research has gone beyond existing approaches to fill a gap in the literature and provide an important contribution to the practice of optimal OSB/OPS. It can be concluded that the integration of IA-OSB/GA-OPS can maximize billing and improve productivity in order to minimize picking operational time and costs in a WA.

Orientador: Rubén Augusto Romero Lázaro / Resumo: The purpose of this research is to develop a tool for optimization in power system distribution that uses meta-heuristic based on a multi-start methodology to reconfigure and allocate fixed and switched capacitor banks to obtain the radial topology that presents the lowest operating cost. To find initial radial topologies for system reconfiguration, the Prim algorithm was applied and to the current solution an improvement process called “neighborhood search” was performed. The improved system is subjected to a capacitor allocation algorithm showing that it is possible to get a radial topology that presents more economic cost of operation. As a proposal of the multi-start methodology, the procedure is repeated until a desired stop criterion, then several solutions are generated and the best one can be the solution of the problem. All programs were written in C ++ and applied to systems of 69 nodes, 84 nodes and 135 nodes. / Mestre

Submitted by MÁRCIO MASATOSHI MONTSUTSUMI null (montsujp@gmail.com) on 2017-01-25T16:40:08Z No. of bitstreams: 1 Dissertação_Márcio.pdf: 1995959 bytes, checksum: 8aa82a70776b8de6528f15a91ec55e78 (MD5) / Approved for entry into archive by LUIZA DE MENEZES ROMANETTO (luizamenezes@reitoria.unesp.br) on 2017-01-27T12:45:18Z (GMT) No. of bitstreams: 1 montsutsumi_mm_me_ilha.pdf: 1995959 bytes, checksum: 8aa82a70776b8de6528f15a91ec55e78 (MD5) / Made available in DSpace on 2017-01-27T12:45:18Z (GMT). No. of bitstreams: 1 montsutsumi_mm_me_ilha.pdf: 1995959 bytes, checksum: 8aa82a70776b8de6528f15a91ec55e78 (MD5) Previous issue date: 2017-01-18 / Conselho Nacional de Desenvolvimento Científico e Tecnológico (CNPq) / O objetivo deste trabalho é desenvolver uma ferramenta para otimização de sistema de distribuição que utiliza uma meta-heurística baseada em uma metodologia multipartida para reconfigurar e alocar bancos de capacitores fixos e chaveados para obter a topologia radial que apresente o menor custo de operação. Para encontrar topologias iniciais radiais na reconfiguração do sistema foi aplicado o algoritmo de Prim e com a solução obtida realizouse um processo de melhoria denominado busca pela vizinhança. O sistema melhorado é submetido a um algoritmo de alocação de bancos de capacitores mostrando que é possível obter uma topologia radial que apresenta mais econômico custo de operação. Como proposta da metodologia multipartida o procedimento é repetido até um critério de parada definido, assim são geradas diversas soluções e a melhor delas será a solução do problema. Todos os programas foram escritos em linguagem C++, e aplicado em sistemas de 69 barras, 84 barras e 135 barras. / The purpose of this research is to develop a tool for optimization in power system distribution that uses meta-heuristic based on a multi-start methodology to reconfigure and allocate fixed and switched capacitor banks to obtain the radial topology that presents the lowest operating cost. To find initial radial topologies for system reconfiguration, the Prim algorithm was applied and to the current solution an improvement process called “neighborhood search” was performed. The improved system is subjected to a capacitor allocation algorithm showing that it is possible to get a radial topology that presents more economic cost of operation. As a proposal of the multi-start methodology, the procedure is repeated until a desired stop criterion, then several solutions are generated and the best one can be the solution of the problem. All programs were written in C ++ and applied to systems of 69 nodes, 84 nodes and 135 nodes. / CNPq: 130695/2015-7

Made available in DSpace on 2016-08-17T13:45:25Z (GMT). No. of bitstreams: 1 Leandro da Silva Pinheiro.pdf: 12011503 bytes, checksum: cfb85a56c46d3b7b25de578ead063b72 (MD5) Previous issue date: 2016-06-16 / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior / Linear Programming problems will be broach in this work together with some ways to find their solutions. Graphically, using geometric figures such as Geogebra, algebraic solutions and, at least, it will be described the use of the tool "Solver"of the Cal spreedsheet of the LibreOffice, that it is easy tool and application in larger problems, relating to the matter worked in high school content, making analogies with situations of applications of this theory in eveyday life of the student without live of highlight the presentation of the great tool that this theory can display and be of geat importance in other areas of knowledge, providing the student with a greater and more "tangible" view of mathmatics as a tool for implementing. / Os problemas de Programação Linear serão abordados neste trabalho juntamente com algumas maneiras de encontrar suas soluções. Graficamente utilizando recursos geométricos como o Geogebra, soluções algébricas e por último será descrita a utilização da ferramenta "Solver" da planilha Calc do LibreOffice, que se trata de uma ferramenta de fácil utilização e aplicação em problemas de dimensões maiores, relacionando com assuntos trabalhados nos conteúdos do Ensino Médio, fazendo analogias com situações de aplicações dessa teoria na vida cotidiana do aluno sem deixar de destacar a apresentação da grandiosa ferramenta que essa teoria pode exibir e ser de grande importância em outras áreas de conhecimento, proporcionando ao aluno uma visão maior e mais "palpável" da Matemática como instrumento de aplicação.