O presente trabalho desenvolve uma extensão do problema de corte de estoque unidimensional no caso em que a demanda pelos vários tipos de itens não é exatamente conhecida. Para considerar a aleatoriedade, foi proposto um modelo de programação estocástica de dois estágios com recurso. As varáveis de primeiro estágio são os números de barras cortadas por padrão de corte, e as variáveis de segundo estágio, os números de itens produzidos em escassez e em escassez. O objetivo do modelo é minimizar o custo total esperado. Para resolver a relaxação linear do modelo, foram propostos um método exato baseado no método Simplex com geração de colunas e uma estratégia heurística, que considera o valor esperado da demanda na resolução do problema de corte de estoque. As duas estratégias foram comparadas, assim como a possibilidade de resolver o problema de corte ignorando as incertezas. Finalmente, observou-se que é mais interessante determinar o valor ótimo do modelo recurso quando o problema sofre mais influência da aleatoriedade / This paper presents an integer linear optimization model of large scale for the one-dimensional cutting stock problem in the case which a demand is considered a random variable. To take this randomness into account, the problem was formulated as a two-stage stochastic linear program with recourse. The first stage decision variables are given by the number of bars that has to be cut according to each pattern, and the second stage decision variables by the number of holding items or backordering items production. The model objective is minimizes the total expected cost. We propose two methods to solve the model linear relaxation, one of them it is a Simplex-based method with column generation. The second method is a heuristic strategy that adopted the expected value of demand. We compare both strategies and the possibly of ignoring uncertainties on model. Finally, we observe that is much more interesting to determine the optimal recourse model solution when we have problems that are more afected by randomness

Uma representação retangular de um grafo plano G é uma representação de G, onde cada vértice é desenhado como um retângulo de modo que dois retângulos devem compartilhar algum segmento de seus lados se e somente se existe uma aresta em G entre os vértices correspondentes aos retângulos. Ainda, a representação de G deve formar um retângulo e não deve existir buracos, ou seja, toda região interna deve corresponder a algum vértice de G. Um desenho retangular de um grafo plano H é um desenho de H, onde todas as arestas são desenhadas como segmentos horizontais ou verticais. Ainda, todas as faces internas são retângulos e as arestas que incidem na face externa também formam um retângulo. Nesta dissertação, apresentamos os principais trabalhos existentes na literatura para problemas associados à representação retangular. Também apresentamos resultados para problemas associados ao desenho retangular. Por fim, apresentamos o algoritmo que desenvolvemos para determinar as coordenadas dos vértices de um desenho retangular quando a orientação das arestas já foram determinadas. / A rectangular representation of a plane graph G is a representation of G, where each vertex is drawn as a rectangle, such as two rectangles have to share some boundary if and only if exist an edge in G between the corresponding vertices. Also, the representation of G must form a rectangle and does not contain any holes, in other words, every point inside the formed rectangle must correspond to some vertex of G. A rectangular drawing of a plane graph H is a drawing of H, where all edges are drawn either in vertical or in horizontal. Also, every internal face is a rectangle and the edges which are incident in the external face define a rectangle. In this dissertation, we present the main studies in the literature for problems associated with the rectangular representation. We also present results for problems associated with rectangular drawing. Finally, we present the algorithm we developed to determine the coordinates of the vertices of a rectangular drawing when the orientation of the edges have been determined.

O Problema de Escalonamento de Médicos (Physician Scheduling Problem) consiste em atribuir tarefas a médicos num horizonte de planejamento respeitando regras laborais, contratuais e de preferências pessoais de modo a satisfazer a demanda de serviços de um hospital. O problema lida majoritariamente com o objetivo de maximizar o atendimento dos requisitos de preferência pessoal, respeitando as restrições laborais e organizacionais. Sobre esta classe de problemas, vários métodos de resolução e suas variantes têm sido propostos na literatura. Ademais, mais características têm sido agregadas ao problema, tornando-o mais complexo e deste modo fazendo-se mais necessária a aplicação de métodos mais elaborados para a sua resolução. Neste trabalho são estudados, reformulados e propostos métodos de resolução baseados em programação matemática para tratar o problema de escalonamento acíclico de médicos em departamento de emergência de hospitais. O primeiro modelo tem como objetivo a minimização da soma ponderada dos desvios das restrições de distribuição. O segundo modelo tem como objetivo, a minimização do máximo dos desvios obtidos nas restrições de distribuição, a fim de se obter escalas mais equilibradas entre os médicos. Foram também propostas heurísticas baseadas na formulação matemática cujos resultados não foram competitivos com as dos modelos. Os modelos foram testados sobre um conjunto de instâncias fictícias resultantes de uma mescla entre instâncias benchmark e características do problema. Os resultados computacionais demonstram que formulação ponderada obteve solução ótima para grande parte das instâncias, embora os limitantes inferiores tenham sido majoritariamente fracos. Em relação ao segundo modelo, soluções ótimas não foram obtidas e os limitantes inferiores foram igualmente fracos. Relativamente a qualidade das escalas, o segundo modelo teve melhor comportamento comparando ao modelo de somas ponderadas. Dada a qualidade das soluções, nota-se a viabilidade da solução baseada em técnicas de otimização em detrimento da manual, pois esta ainda é mais suscetível de erros e acarreta um alto tempo para obtenção de solução. / The Physician Scheduling Problem consists in task assignment to physicians in a planning horizon considering a set of organizational rules, work regulations and individual preferences in order to satisfy an hospital wards work demand. The aim is to find a schedule which maximizes the satisfaction of individual preferences requirements while meeting work regulations and organizational rules. A plethora of solution methods and its variants have been proposed in the literature to solve this class of problem. Moreover, more features have been aggregated to the problem turning it into a more complex and thus estimulating the application of more elaborated methods to its decision. In this work we study, reshape and propose decision methods based in mathematical programming to handle non-ciclic physician scheduling problem in emergency wards. The first formulation targets the minimization of the weighted sum of distribution constraints deviations. The second formulation targets the minimization of the maximum deviations obtained at the distribution constraints aiming more balanced schedules between the physicians. Mathematical formulation heuristics were also proposed and the findings were not satisfactory as they were not competitive with the model. Experiments with our models were performed over a set of dummy instances, as result a of a mixture of benchmark instances and the considered problems features. From our experiments we have found that optimal solutions were obtained through the weighted sum model, despite the poor lower bounds. On the other hand, for the second model, no optimal solution was found and poor lower bounds were similarly obtained. Regarding to the schedules quality, the min-max model had a better performance comparing to the weighted sum model. Given the solutions quality we can assume that optimization based techniques are sustainable comparing to manual, because the latter is prone to errors and omissions and also critical in terms of solutions achievement time.

Submitted by Carmen Torres (carmensct@globo.com) on 2018-02-05T18:07:49Z No. of bitstreams: 2 license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) Dissertacao_AvaliacaoAlgoritmosEvolucionarios.pdf: 15152588 bytes, checksum: 17f1be44824b1303f352e08ae2bc2063 (MD5) / Rejected by Edisangela Bastos (edisangela@ufpa.br), reason: on 2018-02-07T16:17:24Z (GMT) / Submitted by Carmen Torres (carmensct@globo.com) on 2018-02-09T18:32:35Z No. of bitstreams: 2 license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) Dissertacao_AvaliacaoAlgoritmosMultiobjetivo.pdf: 7336466 bytes, checksum: 844408a690f2522ac2b67b232626c56f (MD5) / Approved for entry into archive by Edisangela Bastos (edisangela@ufpa.br) on 2018-02-21T17:14:20Z (GMT) No. of bitstreams: 2 license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) Dissertacao_AvaliacaoAlgoritmosMultiobjetivo.pdf: 7336466 bytes, checksum: 844408a690f2522ac2b67b232626c56f (MD5) / Made available in DSpace on 2018-02-21T17:14:20Z (GMT). No. of bitstreams: 2 license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) Dissertacao_AvaliacaoAlgoritmosMultiobjetivo.pdf: 7336466 bytes, checksum: 844408a690f2522ac2b67b232626c56f (MD5) Previous issue date: 2017-08-10 / O crescimento dos grandes centros urbanos traz como consequência imediata o aumento das cargas nos sistemas de distribuição. Além disso, a crescente demanda implica em igual crescimento no consumo de reativos, que, como já se sabe, são sinônimos de perdas nos sistemas de potência, bem como de comprometimento de alguns de seus componentes. Dessa forma, é grande o desafio das concessionárias de distribuição de energia elétrica, uma vez que a dinâmica da carga imprime um maior esforço no que diz respeito ao planejamento da expansão e de melhorias no sistema. Como forma de mitigar os problemas gerados, a instalação de bancos de capacitores surge como solução prática, econômica e consolidada tecnicamente. Entretanto, há de se pensar no dimensionamento e posição de instalação dos bancos, de modo que alcancem o melhor desempenho possível. Paralelamente, o crescimento de cargas nos sistemas de distribuição introduz um novo paradigma, a presença de harmônicos provenientes de cargas não lineares. Uma das peculiaridades da presença simultânea de harmônicos e capacitores dentro de uma mesma rede elétrica é a possibilidade de ocorrência do fenômeno da ressonância, em que o valor das amplitudes de alguns componentes harmônicos ultrapassam os limites aceitáveis, produzindo diversos efeitos indesejados. Nesse contexto, este trabalho propõe a comparação entre duas técnicas evolucionárias de otimização multiobjetivo, o NSGA-II e o SPEA2, para a solução do Problema de Alocação e Dimensionamento de Bancos de Capacitores (PADBC) em redes de distribuição radiais, considerando os efeitos dos harmônicos na presença de cargas não lineares. / The rapid growth of urban areas bring, as a consequence, an increase in the amount of loads connected to the distribution grids. Furthermore, the increase in the demand implies in equal raise in reactive loads, which are known to cause losses in the network. Thus, the utilities have a great challenge ahead, as the dynamics of the load require a greater effort in terms of expansion and improvements of the grid. In an attempt to mitigate the problems caused, the allocation of capacitor banks can become a practical, economical and technically robust solution. Nevertheless, it is extremely important to analyze the sizing and positioning of the banks, in order to achieve the best possible outcome. In parallel, the increasing use of nonlinear loads cause harmonics to appear in the system. When in conjunction with capacitor banks, it is possible to develop the far more dangerous phenomenon of resonance, where the amplitude of some of the harmonics goes beyond acceptable limits, resulting in undesirable effects. In this context, this work proposes a comparison between two multiobjective optimization tehcniques, NSGA-II and SPEA2, to solve the problem of sizing and placement of capacitor banks in electric energy distribution grids, considering the effects of harmonics produced by nonlinear loads.

Submitted by Rosana Moreira (rosanapsm@outlook.com) on 2018-07-18T18:04:30Z No. of bitstreams: 2 license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) Tese_FerramentasApoioTomada.pdf: 6868217 bytes, checksum: e0d7650db6e4b0ab9e91fe2ec5acbee4 (MD5) / Approved for entry into archive by Luciclea Silva (luci@ufpa.br) on 2018-07-19T12:17:58Z (GMT) No. of bitstreams: 2 license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) Tese_FerramentasApoioTomada.pdf: 6868217 bytes, checksum: e0d7650db6e4b0ab9e91fe2ec5acbee4 (MD5) / Made available in DSpace on 2018-07-19T12:17:59Z (GMT). No. of bitstreams: 2 license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) Tese_FerramentasApoioTomada.pdf: 6868217 bytes, checksum: e0d7650db6e4b0ab9e91fe2ec5acbee4 (MD5) Previous issue date: 2017-12-14 / O uso de Bancos de Capacitores (BCs) devidamente alocados vem constituindo, por muito tempo, uma das principais estratégias utilizadas para manter variáveis elétricas tais como módulo da tensão, fator de potência e carregamento de alimentadores dentro de um nível aceitável. A constante presença de harmônicos na rede acrescenta limitações no uso dessa estratégia, no entanto. Nesse contexto, este trabalho propõe a avaliação a posteriori do Índice de Ressonância (RI) no apoio à tomada de decisão juntamente com o emprego do algoritmo evolutivo multiobjetivo, SPEA2, na solução do Problema de Alocação Ótima de Bancos de Capacitores (PAOBC) em redes de distribuição radiais trifásicas considerando os fenômenos da ressonância e amplificação harmônicas devido a presença de cargas não-lineares. O PAOBC é abordado neste estudo considerando as mudanças da impedância equivalente da rede (driving point impedance) vista a partir do ponto de alocação do respectivo banco de capacitores, seja pela variação de carga durante o dia seja pelas inúmeras manobras a que o sistema é submetido. Os resultados aqui apresentados foram obtidos a partir da rede de distribuição radial trifásica IEEE 34 barras e a rede IEEE 123 barras, nas quais foram inseridos os modelos de três fontes harmônicas comumente encontradas em casos reais. Por fim, destaca-se a praticidade do uso de rotinas multiobjetivo na resolução do PAOBC e importância da avaliação de cenários de ressonância a fim de garantir o funcionamento adequado e seguro do sistema. / The use of properly allocated capacitor banks has long been one of the main strategies used to maintain electrical variables such as voltage, power factor and feeder loading within acceptable levels. However, the constant presence of harmonics in the grid limits the applicability of this strategy. In this context, this work proposes an a posteriori evaluation of the Resonance Index to support the decision making process, in conjunction with the multiobjective evolutionary algorithm, SPEA2, to solve the Optimal Capacitor Allocation Problem (OCAP) in three-phase radial distribution networks considering the harmonic resonance and amplification phenomena due to the presence of non-linear loads. A study of the variation of the equivalent impedance of the network (driving point impedance) seen from the allocation point of the respective capacitor bank, either by the variation of load during the day or by the numerous maneuvers to which the system is subjected. The results presented here were obtained from the IEEE 34-bus three-phase radial distribution network and the IEEE 123- bus network, in which the models from three different harmonic sources commonly found in real case scenarios were inserted. Finally, the convenience of the use of multiobjective routines in solving the OCAP and the importance of the evaluation of resonance scenarios in order to guarantee an adequate and safe operation of the system are highlighted.

Made available in DSpace on 2015-03-05T14:01:22Z (GMT). No. of bitstreams: 0 Previous issue date: 12 / Bolsa para curso e programa de Pós Graduação / Este trabalho aborda o uso de uma metaheurística populacional para a solução do problema de otimização conhecido, na Pesquisa Operacional, como Programação de Horário de Cursos Baseada em Currículos. O problema de Programação de Horário de Cursos Baseada em Currículos consiste na construção das grades de horário de cursos em instituição de ensino que indicam em quais períodos semanais cada disciplina destes cursos deverá ocorrer, alocando professores e salas e respeitando um conjunto de requisitos organizacionais, pedagógicos e pessoais. Este trabalho apresenta uma formulação matemática para o problema e especifica um algoritmo de solução baseado na técnica metaheurística Busca Dispersa, combinada com o método de Reconexão por Caminhos. Além disso, é apresentado o registro de testes realizados com instâncias de problemas utilizadas na International Timetabling Competition e também em um problema real de uma instituição local de esino superior. / This paper discusses the use of a populational metaheuristic to solve the optimization problem known in Operational Research, as Curriculum Based Timetabling. The Curriculum Based Timetabling problem is the construction of schedule of courses in educational institutions that indicate which weekly times each subject of these courses should occur, allocating rooms and teachers and a respecting a set of organizational, pedagogical and personal requirements. This paper presents a mathematical formulation for the problem and specify a solution algorithm based on the Scatter Search metaheuristic technique, combined with the method Path Relinking. Furthermore, it is present the record of tests with instances of problems used in the International Timetabling Competition and also a real problem of a local institution.

Submitted by William Justo Figueiro (williamjf) on 2015-07-27T20:23:06Z No. of bitstreams: 1 09d.pdf: 2136888 bytes, checksum: 8bc73fd7975259c3bc984b913580a5c1 (MD5) / Made available in DSpace on 2015-07-27T20:23:06Z (GMT). No. of bitstreams: 1 09d.pdf: 2136888 bytes, checksum: 8bc73fd7975259c3bc984b913580a5c1 (MD5) Previous issue date: 2013 / CAPES - Coordenação de Aperfeiçoamento de Pessoal de Nível Superior / Com a expansão do transporte marítimo, passou a ser adotado o uso de contêineres para o transporte de cargas, sendo evidenciados alguns problemas. Dentre eles, um dos principais, é o problema de carregamento e descarregamento de contêineres em navios. O problema surge devido aos altos custos operacionais gerados a partir da movimentação de contêineres. Este problema é o foco desta pesquisa, que tem como objetivo principal elaborar planos de carga eficientes que gerem um número mínimo de movimentações de contêineres, nas operações de carga e descarga de navios-contêineres, diminuindo assim os custos de operação. Neste trabalho, é proposta a aplicação da metaheurística Algoritmo Genético e da metaheurística Enxame de Abelhas, resolvendo o problema através de uma codificação baseada em regras de carregamento e descarregamento. A codificação por regras é compacta e adequada, assegurando que as soluções do problema sejam factíveis e de simples representação, acelerando o processo de solução. Nos experimentos realizados, as duas metaheurísticas foram empregadas, assumindo diferentes configurações de regras, com o intuito de comparar o seu desempenho. A proposta de novas regras de carregamento e descarregamento, em complemento às existentes na literatura, trouxeram bons resultados. Desta forma, foram obtidas soluções de boa qualidade e melhores que aquelas encontradas na literatura que abordam o mesmo problema. / With the expansion of maritime transportation, the use of containers for goods transportation has increased, being evidenced some problems. Among these problems, the container ship stowage problem arose as one of the main problems due to the high operational costs related to movement of containers. This problem is the focus of this research, where the main objective is the formulation of stowage plans that generate a minimum number of container shiftings in the operations of loading and unloading performed in port calls of container ships. In order to determine a suitable stowage plan, the application of Genetic Algorithm and Bee Swarm Optimization metaheuristics are proposed to solve the problem by using a rule-based encoding for the solution. The solution encoding based on loading and unloading rules is compact and suitable, ensuring the feasibility of solutions and also the simple representation of it, speeding up the solution procedures. In the performed experiments, both metaheuristics were applied assuming different rules settings with the objective to compare each performance. The proposal of new rules of loading and unloading, in addition with those existing in literature, has produced good solutions. Thereby, good quality solutions were achieved and also better than that found in the literature which discuss the same problem

Submitted by Silvana Teresinha Dornelles Studzinski (sstudzinski) on 2015-11-04T15:30:21Z No. of bitstreams: 1 Kelly Cristina Ferreira Dias.pdf: 6056954 bytes, checksum: f38a4fe2aa64b584f392432c93244c7f (MD5) / Made available in DSpace on 2015-11-04T15:30:21Z (GMT). No. of bitstreams: 1 Kelly Cristina Ferreira Dias.pdf: 6056954 bytes, checksum: f38a4fe2aa64b584f392432c93244c7f (MD5) Previous issue date: 2015-07-29 / Nenhuma / O desempenho operacional das instituições hospitalares tem relação direta com a escala de trabalho das pessoas. Assim, a tarefa de construção das mesmas exige atenção a diversos detalhes para obtenção de bons resultados. É neste contexto que um modelo, computacionalmente viável, para a elaboração das escalas de trabalho de pessoal de enfermagem, capaz de gerar elementos para avaliação de sua influência no desempenho operacional do hospital, torna-se importante. A contribuição desta pesquisa é apresentar um modelo matemático, baseado em restrições que permitam a elaboração de escalas para equipes de enfermagem com suporte computacional. Além disso, o estudo apresenta elementos para avaliação do Quadro de Lotação da equipe de trabalho. A tarefa de escalar pessoal é responsável por consumir muito tempo e nem sempre garantir o cumprimento das legislações e normas vigentes, visto ser normalmente um processo manual, sem uso de ferramentas computacionais personalizáveis às particularidades de cada hospital. O estudo foi realizado a partir de dados levantados junto a Unidade de Internação de um hospital em Porto Alegre/RS. Foram obtidas, no estudo de campo, informações relativas às necessidades da escala de trabalho nesta realidade particular, além do levantamento de indicadores de desempenho. Foram realizados experimentos para avaliar a influência das variáveis de decisão e parâmetros do Algoritmo empregado para a obtenção da solução. Na validação do modelo foram utilizados casos de teste hipotéticos, baseados em dados reais levantados no estudo. Com a aplicação do modelo, as escalas de trabalho puderam ser obtidas de forma a atender as necessidades dos setores hospitalares proporcionando menor impacto no desempenho operacional do hospital. / The operating performance of hospitals have directly related of rostering colaboration. Thus, the construction of the same task requires attention to the many details to obtain good results. In this context, a model computationally feasible to prepare the rostering nursing, capable of generating elements to assess its influence on the hospital's operating performance, it is important. The contribution of this research is to present a formal mathematical model, based on restrictions to allow the construction of scheduling nursing with computer support. In addition, the study presents elements for evaluating the Board's work team Capacity. Personal climbing task is responsible for time-consuming and not always ensure compliance with existing laws and regulations, as it is usually a manual process, without the use of customizable computational tools to the particularities of each hospital. The study was conducted from data collected at the inpatient unit of a hospital in Porto Alegre/ RS. They were obtained from the information field study on working range of needs in this particular reality, beyond the performance indicators survey. Experiments were conducted to evaluate the effect of the decision variables and the influence of the parameters of the Evolutionary Algorithm in the final solution. To validate the model we used cases of hypothetical test, based on real data collected in the study. With the application of the model, working scales can be obtained to meet the needs of hospital departments providing less negative impact on the hospital's operating performancer.

Submitted by Franciele Moreira (francielemoreyra@gmail.com) on 2018-04-17T15:48:39Z No. of bitstreams: 2 Tese - Joelma de Moura Ferreira - 2018.pdf: 58164875 bytes, checksum: c19d300de77be476834ac9c2e7ca8b0e (MD5) license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) / Approved for entry into archive by Luciana Ferreira (lucgeral@gmail.com) on 2018-04-18T11:17:22Z (GMT) No. of bitstreams: 2 Tese - Joelma de Moura Ferreira - 2018.pdf: 58164875 bytes, checksum: c19d300de77be476834ac9c2e7ca8b0e (MD5) license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) / Made available in DSpace on 2018-04-18T11:17:22Z (GMT). No. of bitstreams: 2 Tese - Joelma de Moura Ferreira - 2018.pdf: 58164875 bytes, checksum: c19d300de77be476834ac9c2e7ca8b0e (MD5) license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) Previous issue date: 2018-03-21 / Edge bundling is a technique to group, align, coordinate and position the depiction of edges in a graph drawing, so that sets of edges appear to be brought together into shared visual structures, i.e. bundles. The ultimate goal is to reduce clutter to improve how it conveys information. This thesis provides a general formulation for the explicity edge bundling problems, as a formal combinatorial optimization problem. This allows for the definition and comparison of edge bundling problems. In addition, we present four explicity edge bundling optimization problems that address minimizing the total number of bundles, in conjunction with other aspects, as the main goal. An evolutionary edge bundling algorithm is described. The algorithm was successfully tested by solving three related problems applied to real-world instances. The reported experimental results demonstrate the effectiveness and the applicability of the proposed evolutionary algorithm to help resolve edge bundling problems formally defined as optimization models. / A união de arestas em feixes é uma técnica para agrupar, alinhar, coordenar e posicionar a representação de arestas em um desenho de grafo, de modo que os conjuntos de arestas pareçam ser reunidos em estruturas visuais compartilhadas, ou seja, feixes. O objetivo final é reduzir a poluição visual do desenho melhorando a forma como ele transmite informações. Esta tese apresenta uma formulação geral para problemas de união explícita de arestas, como um problema formal de otimização. Essa formulação pode ser usada para definir e comparar problemas de união de arestas. Ainda, são definidos quatro problemas de otimização de união explícita de arestas, que têm por objetivo minimizar o número total de feixes, em conjunto com outros aspectos. Um algoritmo evolucionário é descrito. O algoritmo foi testado com sucesso em três dos problemas relacionados aplicados a instâncias do mundo real. Os resultados experimentais demonstram a eficácia e a aplicabilidade do algoritmo evolutivo proposto para ajudar a resolver problemas de união de arestas em feixes formalmente definidos como um modelo de otimização.

Submitted by Luciana Ferreira (lucgeral@gmail.com) on 2017-08-03T11:05:17Z No. of bitstreams: 2 Dissertação - Carlos Alexandre Xavier da Silva - 2017.pdf: 2190162 bytes, checksum: 7c5e13d2301a93a75a0e2d68e1b9a893 (MD5) license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) / Approved for entry into archive by Luciana Ferreira (lucgeral@gmail.com) on 2017-08-03T11:06:02Z (GMT) No. of bitstreams: 2 Dissertação - Carlos Alexandre Xavier da Silva - 2017.pdf: 2190162 bytes, checksum: 7c5e13d2301a93a75a0e2d68e1b9a893 (MD5) license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) / Made available in DSpace on 2017-08-03T11:06:02Z (GMT). No. of bitstreams: 2 Dissertação - Carlos Alexandre Xavier da Silva - 2017.pdf: 2190162 bytes, checksum: 7c5e13d2301a93a75a0e2d68e1b9a893 (MD5) license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) Previous issue date: 2017-06-26 / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior - CAPES / In one version of the Simple Assembly Line Balancing Problem (SALBP) tasks are assigned to stations along an assembly line with a fixed cycle time in order to minimise the required number of stations. It is assumed that the total work needed for each product unit has been partitioned into economically indivisible tasks. In practice, it may be that the minimal number of stations can be reduced when it is possible to further divide particular tasks in limited ways even with additional time penalty costs. Allowing task division leads to a new assembly line balancing problem, TDALBP (Task Division Assembly Line Balancing Problem) and a solution procedure for it. This work introduces a mathematical model for the TDALBP and presents promising computational results for the adaptation of some classical SALBP instances from the research literature. The results demonstrate that the TDALBP has the potential to significantly improve assembly line performance. / O balanceamento eficaz de uma linha de produção é importante para aprimorar a produtividade e reduzir custos de uma industria. O problema do balanceamento de linhas de produção (Assembly Line Balancing Problem - ALBP) envolve atribuir as tarefas necessárias para produzir cada unidade de um produto entre estações de trabalho ao longo de uma linha de produção, a fim de otimizar alguma medida de desempenho do sistema. Tradicionalmente, supõe-se que o trabalho total necessário para cada unidade de produto foi particionado em tarefas economicamente indivisíveis, de modo que uma maior divisão gera custos desnecessários. Assim, cada tarefa requerida não pode ser dividida e deve ser realizada em uma única estação. Na prática, no entanto, isso pode não ser sempre verdadeiro quando existe um objetivo orientado ao tempo, tal como a minimização do número de estações para um determinado tempo de ciclo. Neste caso, pode ser que o número mínimo das estações possa ser reduzido quando for possível continuar a dividir tarefas particulares de formas limitadas, mesmo se a divisão induzir custos adicionais de tempo. A permissão de tal divisão de tarefas nos leva a um novo problema de balanceamento de linhas de produção, o qual denotamos por TDALBP (Task Division Assembly Line Balancing Problem). Nós propomos um modelo de programação linear inteira binária para o TDALBP e procedimentos efetivos para solucioná-lo. Os procedimentos foram avaliados sobre adaptações de várias instâncias SALBP clássicas da literatura. Os resultados computacionais são promissores e mostram o potencial do TDALBP para a melhora significativa do desempenho de linhas de produção.