Made available in DSpace on 2016-08-18T12:52:12Z (GMT). No. of bitstreams: 1 DISSERTACAO_ALLAN KASSIO BECKMAN SOARES DA CRUZ.pdf: 3904761 bytes, checksum: fcf2b0e10224d47b174664dcde46f7b8 (MD5) Previous issue date: 2015-06-02 / In recent years within the emerged game development tools and methodologies that try define, practical and theoretically, the practices for the creative process of game design (SALEN; ZIMMERMAN, 2012). These tools and methodologies often xclude and end up to be more difficult the job of game designer. Factors such as playful interaction,rules and culture are relevant to the development of a good game. This master s thesis uses as a study object the board games and aims to create a set of heuristics that are able to assess the rules of any board game. To achieve this goal was established a methodology that trasnform the rule of these games in an interaction model that can be evaluated by computer systems assessment methodologies as the heuristics of Nielsen (1994). Originally the Nielsen heuristics have been proposed and developed for sability evaluation in computer systems interfaces. We proposes an analysis and redesign in order to specialize these heuristics to use in the evaluation rules of board games. Heuristics pass through redesign process from literature, considerations and models generated on the rules found in each tested game, and analysis of existing rules in these games through inspection method using heuristics Nielsen (1994). The results indicate the viability of using generated heuristics for the evaluating of usability of the board games rules. / Nos últimos anos dentro da área de desenvolvimento de jogos surgiram ferramentas e metodologias que tentam por vezes de forma prática e por vezes de forma teórica definir as práticas do processo criativo do design de jogos (SALEN; ZIMMERMAN, 2012). Essas ferramentas e metodologias muitas vezes se excluem e acabam tornando mais difícil o trabalho do designer de jogos. Fatores como interação lúdica, regras e cultura são relevantes para o desenvolvimento de um bom jogo. Este trabalho utiliza como objeto de estudo os jogos de tabuleiro e tem como objetivo a criação de um conjunto de heurísticas que sejam capazes de avaliar as regras de qualquer jogo de tabuleiro. Para alcançar esse objetivo foi criada uma etodologia que transforma a regra desses jogos em um modelo de interação passível de ser avaliado por metodologias de avaliação de sistemas computacionais como as heurísticas de Nielsen (1994). Originalmente as heurísticas de Nielsen foram propostas e desenvolvidas para avaliação de usabilidade em interfaces de sistemas computacionais.No decorrer do trabalho propõe-se uma análise e redesenho de forma a especializar essas heurísticas para emprego na avaliação de regras de jogos de tabuleiros. As heurísticas passam pelo processo de redesenho a partir de levantamento bibliográfico, considerações e modelos gerados sobre as regras encontradas em cada jogo testado, além da análise das regras existentes nesses jogos através de método de inspeção utilizando as heurísticas de Nielsen (1994) e as eurísticas geradas durante o redesenho. Os resultados apontam para a viabilidade da utilização das heurísticas geradas para a avaliação de usabilidade das regras de jogos de tabuleiro.

Submitted by Jose Roberto Carvalho de Moura (jrcmoura@gmail.com) on 2012-08-01T00:58:05Z No. of bitstreams: 1 Dissertação de Mestrado (FGV).pdf: 2317080 bytes, checksum: 3e9561309b6754601ad2973d8b53c207 (MD5) / Approved for entry into archive by Janete de Oliveira Feitosa (janete.feitosa@fgv.br) on 2012-08-23T14:56:06Z (GMT) No. of bitstreams: 1 Dissertação de Mestrado (FGV).pdf: 2317080 bytes, checksum: 3e9561309b6754601ad2973d8b53c207 (MD5) / Approved for entry into archive by Marcia Bacha (marcia.bacha@fgv.br) on 2012-08-24T13:01:30Z (GMT) No. of bitstreams: 1 Dissertação de Mestrado (FGV).pdf: 2317080 bytes, checksum: 3e9561309b6754601ad2973d8b53c207 (MD5) / Made available in DSpace on 2012-08-24T13:01:44Z (GMT). No. of bitstreams: 1 Dissertação de Mestrado (FGV).pdf: 2317080 bytes, checksum: 3e9561309b6754601ad2973d8b53c207 (MD5) Previous issue date: 2012-07-05 / This study aims to investigate the decision-making process of individuals from different nationalities, who work in organizational project management, in their lives out of professional’s context. As the existing methodologies in the area of project management highlight the need of a rational, logical and objective decision-making process, this study will explore if the professionals extrapolate this same linear decision-making process, taken from professional’s sphere, to their daily lives. The academic studies over the years discussed the rational, linear and logical decisionmaking, where they were able to refute this assumption along with new perspectives for the human cognitive’s judgment. Thus, this research will not only present the project management study’s field and its concepts, but also approach the several evolutions of the theory related to decision-making process along the years. Taking into consideration the subjective aspect of the decision theories presented, and cognitive limitation that imposes itself most of the times, this study aims to explore the different heuristics (simplified strategies, mental shortcuts) of judgment and their respective cognitive biases. The three main meta-heuristics, exposed by Tversky e Kahneman in their academic study from 1974 and also focus of this research are, respectively: representativeness, availability and adjustment and anchoring. In this study a quantitative research is performed with organizational individuals who work in project management, or at least had any experience with any projects in the companies they work. It is worth to note this study is not limited to Brazil, as it also extends to other countries containing the same public that are the focus of this research. The results of this research reveal that professionals who work in project management are subject to cognitive biases out of their organizational’s context, considering that Brazilians are less subject to these biases, in comparison to the different nationalities investigated. Also, the research revealed that professional’s experience doesn’t significantly contribute to a rational and logical decision-making in their daily personal lives. / Este trabalho tem por objetivo estudar a tomada de decisão dos indivíduos de diferentes nacionalidades, que atuam na gestão de projetos organizacionais, em sua vida fora do âmbito profissional. Dado que as metodologias existentes na área de gestão de projetos atentam para a necessidade de um processo decisório racional, lógico e objetivo, este estudo pretende explorar até que ponto os sujeitos organizacionais extrapolam este mesmo processo decisório linear, advindo do mundo profissional, para o seu cotidiano. Os estudos acadêmicos ao longo dos anos trataram de discutir esta temática da decisão racional, linear e lógica, os quais foram capazes de refutar esta hipótese com novas perspectivas para o julgamento cognitivo dos humanos. Portanto, além deste trabalho apresentar o campo de estudo da gerência de projetos e seus conceitos, ele também aborda as diversas evoluções teóricas acerca da tomada de decisão ao longo do tempo. A partir da consideração do caráter subjetivo nas teorias de decisão apresentadas, e a limitação cognitiva que muitas vezes se impõe, este estudo busca então explorar as diferentes heurísticas (estratégias simplificadoras, atalhos mentais) de julgamento e seus respectivos vieses cognitivos. As três principais meta-heurísticas, expostas por Tversky e Kahneman em seu trabalho acadêmico de 1974 e também foco deste estudo são, respectivamente: da representatividade, da disponibilidade e da ancoragem e ajustamento. Neste trabalho é realizada uma pesquisa quantitativa com sujeitos organizacionais que trabalham com gestão de projetos, ou que tiveram alguma experiência em algum projeto nas empresas em que trabalham. Ressalta-se que este estudo não se limita ao Brasil, extendendo-se também a outros países com o mesmo público-alvo de pesquisa. Os resultados da pesquisa revelaram que os profissionais que atuam em gestão de projetos estão sujeitos a vieses cognitivos fora do âmbito organizacional, sendo que os brasileiros são os menos propensos a estes vieses, em comparação com as demais nacionalidades estudadas. Também revelou-se que o tempo de experiência profissional não contribui de modo significante para uma tomada de decisão mais racional e lógica no cotidiano pessoal.

Submitted by Joel de Lima Pereira Castro Junior (joelpcastro@uol.com.br) on 2016-07-23T21:45:30Z No. of bitstreams: 1 VivianFrança.pdf: 2881557 bytes, checksum: 1ce976b103742f469288ae61c5b5fec4 (MD5) / Approved for entry into archive by Biblioteca de Administração e Ciências Contábeis (bac@ndc.uff.br) on 2016-08-03T18:45:49Z (GMT) No. of bitstreams: 1 VivianFrança.pdf: 2881557 bytes, checksum: 1ce976b103742f469288ae61c5b5fec4 (MD5) / Made available in DSpace on 2016-08-03T18:45:49Z (GMT). No. of bitstreams: 1 VivianFrança.pdf: 2881557 bytes, checksum: 1ce976b103742f469288ae61c5b5fec4 (MD5) / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior / Centro Universitário Hermínio da Silveira (IBMR) / O objetivo desta pesquisa é identificar os vieses cognitivos que motivaram os funcionários da Petrobras a tomarem a decisão de aderir ao Plano de Demissão Voluntária (PDV). Como objetivos específicos têm-se: a) compreender como os vieses cognitivos agiram no processo de decisão de adesão ao PDV; b) identificar como os vieses cognitivos agiram nos funcionários que não aderiram ao PDV nesta mesma época. Para isso, realizou-se uma pesquisa de natureza quantitativa, com a aplicação de dois questionários padronizados, direcionado para cada perfil de sujeitos da pesquisa. Estes totalizaram em 61 respondentes, sendo 31 Pedevistas (sujeitos que aderiram ao PDV) e 30 Não Pedevistas (sujeitos que não aderiram ao PDV). Para análise dos dados utilizou-se o site de gerenciamento de pesquisa www.enquetefacil.com e para as análises complementares de estatística o software SPSS (Statistical Package for the Social Sciences), como forma de garantir a fidedignidade das informações obtidas. Constatou-se que em muitos momentos Pedevistas e Não Pedevistas comportaram-se de maneira muito similar, minimizando qualquer possibilidade de diferenças estatísticas observadas. Em outros momentos, os Pedevistas revelaram-se como indivíduos menos analíticos, excessivamente confiantes e ingênuos. Enquanto os Não Pedevistas também demostraram-se ser potencialmente confiantes, porém analíticos e conservadores. Conclui-se que os Não Pedevistas conseguiram usufruir positivamente do potencial adverso das heurísticas de julgamento e seus vieses cognitivos, consequentemente obtiveram melhores resultados com a sua decisão. No entanto, os Pedevistas foram potencialmente prejudicados pelos efeitos negativos dos vieses cognitivos e até hoje sofrem os danos gerados pela decisão de tomaram. / The purpose of this research is to identify the cognitive biases that motivated employees of Petrobras to take the decision to join the Plano de Demissão Voluntária – PDV. The specific objectives are to: a) understand how cognitive biases acted in decision to join the PDV b) identify how cognitive biases acted in employees who do not adhere to this same time PDV. Then, we carried out a quantitative survey applicated by two standardized questionnaires, directed to each profile of research subjects. These totaled in 61 respondents, 31 Pedevistas (subjects who adhered to PDV) and 30 Non Pedevistas (subjects who did not adhere to PDV). Data analysis used the site management and www.enquetefacil.com search for complementary analyzes of the statistical software SPSS (Statistical Package for the Social Sciences), in order to guarantee the reliability of information obtained. It was found that in many instances that not Pedevistas and Pedevistas behaved in a very similar manner, minimizing any possible statistical differences observed. At other times, Pedevistas proved as individuals less analytical, overly trusting and naive. While not Pedevistas demonstrated to be potentially confident, analytical and conservative. We conclude that Pedevistas could take advantage of the positive potential adverse judgment heuristics and their cognitive biases, thus reached better results with his decision. However, Pedevistas were potentially affected by the negative effects of cognitive biases and still suffer the damage caused by the decision taken.

Problemas de corte e empacotamento de itens irregulares são problemas que visam determinar um leiaute ótimo de objetos pequenos dentro de objetos maiores, a fim de atender a uma demanda. Estes problemas têm grande importância prática, já que surgem em vários tipos de indústria (como a têxtil, a de móveis e a de calçados). O problema estudado neste trabalho é o problema de corte de itens irregulares em recipientes. Os recipientes são delimitados e o objetivo é encontrar um leiaute dos objetos menores, sem sobreposição, dentro dos objetos maiores utilizando a menor quantidade de recipientes. Propomos um novo método de resolução para o problema. Nosso método é um algoritmo que gerencia um conjunto de heurísticas, de baixo nível, específicas para a resolução do problema com recipientes retangulares e irregulares. Recipientes irregulares são polígonos convexos e não convexos, que podem ser furados. As heurísticas desenvolvidas utilizam uma malha de pontos sobre a técnica de no-fit polygon para evitar a sobreposição dos itens e encontrar posições viáveis no recipiente retangular ou irregular. Os experimentos computacionais foram feitos para um grande conjunto de instâncias, de recipientes retangulares e irregulares. Os resultados demonstram a competitividade do método, que obtêm resultados bons e algumas soluções ótimas, em um tempo computacional aceitável. / Cutting and packing of irregular items are problems that aim to determine the optimum layout of small objects within larger objects (that we call bins), in order to meet a demand. These problems have great practical importance, since they emerge in various types of industry (such as textile, furniture and shoemaking). The problem studied in this work is the irregular bin packing problem. The bins are enclosed and the goal is to find a layout of items, without overlap, within the bins by using the minimum quantity of them. We propose a new method of resolution to this problem. Our method is an algorithm that manages a set of low-level heuristics, specific to solve the problem with rectangular bins and irregular bins. Irregular bins are convex and non-convex polygons, which may contain holes. The developed heuristics uses a mesh of points and the technique of no-fit polygon to avoid the overlapping of items and find feasible positions in rectangular or irregular bins. The computational experiments were performed for a large set of instances, using both rectangular and irregular bins. The results demonstrate the competitiveness of the method, which can get good results and some optimal solutions within an acceptable computational time.

O problema do caixeiro viajante (PCV) é um problema clássico de otimização que possui diversas variações, aplicações e instâncias. Encontrar a solução ótima para muitas instâncias desse problema é geralmente muito difícil devido o alto custo computacional. Vários métodos de otimização, conhecidos como meta-heurísticas (MHs), são capazes de encontrar boas soluções para o PCV. Muitos algoritmos baseados em diversas MHs têm sido propostos e investigados para diferentes variações do PCV. Como não existe um algoritmo universal que encontre a melhor solução para todas as instâncias de um problema, diferentes MHs podem prover a melhor solução para diferentes instâncias do PCV. Desse modo, a seleção a priori da MH que produza a melhor solução para uma dada instância é uma tarefa difícil. A pesquisa desenvolvida nesta tese investiga o uso de abordagens de meta-aprendizado para selecionar as MHs mais promissoras para novas instâncias de PCV. Essas abordagens induzem meta-modelos preditivos a partir do treinamento das técnicas de aprendizado de máquina em um conjunto de meta-dados. Cada meta-exemplo, em nosso conjunto de meta-dados, representa uma instância de PCV descrita por características (meta-atributos) do PCV e pelo desempenho das MHs (meta-atributo alvo) para essa instância. Os meta-modelos induzidos são usados para indicar os valores do meta-atributo alvo para novas instâncias do PCV. Vários experimentos foram realizados durante a investigação desta pesquisa e resultados importantes foram obtidos / The traveling salesman problem (TSP) is a classical optimization problem that has several variations, applications and instances. To find the optimal solution for many instances of this problem is usually a very hard task due to high computational cost. Various optimization methods, known as metaheuristics (MHs), are capable to generate good solutions for the TSP. Many algorithms based on different MHs have been proposed and investigated for different variations of the TSP. Different MHs can provide the best optimization solution for different TSP instances, since there is no a universal algorithm able to find the best solution for all instances. Thus, a priori selection of the MH that produces the best solution for a given instance is a hard task. The research developed in this thesis investigates the use of meta-learning approaches to select the most promising MHs for new TSP instances. These approaches induce predictive meta-models from the training of machine learning techniques on a set of meta-data. In our meta-data, each meta-example is a TSP instance described by problem characteristics (meta-features) and performance of MHs (target meta-features) for this instance. The induced meta-models are used to indicate the values of the target meta-feature for new TSP instances. During the investigation of this research, several experiments were performed and important results were obtained

Submitted by Nadir Basilio (nadirsb@uninove.br) on 2016-07-01T14:58:21Z No. of bitstreams: 1 Marisa Carla Voigt Gava.pdf: 1946904 bytes, checksum: 369bf987709311eddcb1f66a7c5fad55 (MD5) / Made available in DSpace on 2016-07-01T14:58:21Z (GMT). No. of bitstreams: 1 Marisa Carla Voigt Gava.pdf: 1946904 bytes, checksum: 369bf987709311eddcb1f66a7c5fad55 (MD5) Previous issue date: 2016-02-29 / The cutting problem involves cutting larger objects into smaller items with the aim of minimizing waste. The objects can be raw materials, such as rolls of paper, glass sheets, metal plates, steel, aluminum or wood. The items represent the shape to be cut and may be described as concave or convex irregular geometries. The cut of raw material is an industrial process which has attracted the attention of many researchers, since it can generate large waste, increasing the production cost. Nevertheless, the set of possible solutions to this problem has a large number of combinations and, therefore, its computational complexity is considered NP-Hard. In this work, we proposed an approach based on Genetic Algorithm (GA) and Digital Image Processing (DIP) to deal with the problem of to cut rectangular plates (objects) in equal parts (items) with irregular shapes, categorized in the literature as 2D-I-IIPP. The aim is to maximize the number of items to be cut into the available area of the object in order to reduce waste and thus adding economic gains to the cutting process. In this approach the object and the items are represented as digital images. The GA is responsible for generating possible solutions (sets of translations and orientations of items). The evaluation of each solution generated by GA is performed by a RPID algorithm, which basically detects overlaps between the items placed on the object and calculates the quality of solution. To develop the proposed approach it was used the programming language C/C++ in addition to GAlib and Proeikon libraries. Based on computational experiments conducted the results indicate that the proposed approach is a good alternative to solve the problem investigated. / O problema de corte consiste em cortar objetos maiores em itens menores com o objetivo de minimizar as sobras. Os objetos podem ser matérias-primas, tais como bobinas de papel, folhas de vidro, placas de metal, aço, alumínio ou madeira. Os itens representam o formato que deverá ser cortado e podem ser descritos como de geometrias irregulares côncavas ou convexas. O corte de matéria-prima é um processo industrial que tem atraído a atenção de muitos pesquisadores, visto que pode gerar grandes desperdícios, elevando o custo da produção. Não obstante, o conjunto de possíveis soluções para esse tipo de problema possui um grande número de combinações e, por esse motivo, sua complexidade computacional é considerada NP-Hard. Neste trabalho é proposta uma abordagem baseada em Algoritmo Genético (AG) e Processamento de Imagens Digitais para lidar com o problema de cortar placas retangulares (objetos) em peças idênticas (itens) com formas irregulares, categorizado na literatura como 2D-I-IIPP. O objetivo é maximizar o número de itens a serem cortados na área disponível do objeto, visando diminuir os desperdícios e, consequentemente, agregando ganhos econômicos ao processo de corte. Nesta abordagem tanto os objetos como os itens são representados como imagens digitais. O AG é responsável por gerar as possíveis soluções (conjuntos de translações e orientações dos itens). A avaliação de cada solução gerada pelo AG é realizada por um algoritmo de Processamento de Imagens Digitais que basicamente detecta as sobreposições entre os itens posicionados sobre o objeto e calcula a qualidade da solução. Para desenvolver a abordagem proposta foi utilizada a linguagem de programação C/C++, além das bibliotecas GAlib e Proeikon. Os resultados obtidos nos experimentos computacionais realizados indicam que a abordagem proposta é uma boa alternativa para solução do problema investigado.

Submitted by Nadir Basilio (nadirsb@uninove.br) on 2018-01-24T20:35:47Z No. of bitstreams: 1 Luigi Tavolaro Santini.pdf: 2357766 bytes, checksum: b70528f7db6bf88f1285744982eb4234 (MD5) / Made available in DSpace on 2018-01-24T20:35:47Z (GMT). No. of bitstreams: 1 Luigi Tavolaro Santini.pdf: 2357766 bytes, checksum: b70528f7db6bf88f1285744982eb4234 (MD5) Previous issue date: 2017-02-23 / The present work deals with the Capacitated Vehicle Routing Problem with Three-Dimensional Loading Constraints. This problem is difficult to solve exactly, still relatively little studied, but important in the logistics activities of movement, warehousing and transportation. This problem consists in minimizing the total traveled distance by a homogeneous fleet of vehicles that address the issue of deliveries of customer demands, in which these demands are composed of items that have three relevant spatial dimensions. The objective of the present work is to develop heuristic and metaheuristic algorithms to solve the problem in question. The algorithms are based on the Clarke & Wright and George & Robinson heuristics, and on the Iterated Local Search and Adaptive Large Neighborhood Search metaheuristics. In the proposed algorithm, the routing problem is firstly addressed by adapting the Clarke & Wright heuristic, creating routes that are used to verify the loading pattern, thus obtaining an initial solution. In the following, an extensive search in the solution neighborhood is applied with the Iterated Local Search metaheuristic. For the best results of this search, it is checked if the loading pattern is feasible using an adapted George & Robinson algorithm. If it is not feasible, the Adaptive Large Neighborhood Search metaheuristic is executed in an attempt to find a feasible solution to the loading problem. Instances from the literature are used to evaluate the efficiency of the developed methods. The results obtained for the routing problem individually were of paramount importance to ensure the effectiveness of the Iterated Local Search metaheuristic. For the loading problem individually, the tests were also satisfactory, allowing for several feasible loading patterns using the adapted George & Robinson algorithm and the Adaptive Large Neighborhood Search metaheuristic. The results obtained with the proposed algorithm for the integrated problem were also good, being very close to those in the literature and with computational time relatively lower. As perspectives for future research, it is intended to investigate more efficient ways of exploring the solution space of the integrated problem, as well as the use of other metaheuristics. / O presente trabalho trata do Problema de Roteamento de Veículos Capacitado com Restrições de Carregamento Tridimensional. Este é um problema de difícil solução exata, ainda relativamente pouco estudado, porém importante nas atividades logísticas de movimentação, armazenagem e transporte de produtos. Este problema consiste em minimizar a distância total percorrida por uma frota homogênea de veículos que supram a questão das entregas das demandas de clientes, em que tais demandas são compostas por itens que possuem três dimensões espaciais relevantes. O objetivo do presente trabalho consiste em desenvolver algoritmos heurísticos e meta-heurísticos para resolver o problema em questão. Os algoritmos são baseados nas heurísticas de Clarke & Wright e de George & Robinson, e nas meta-heurísticas Iterated Local Search e Adaptive Large Neighborhood Search. No algoritmo proposto, primeiro trata-se o problema de roteamento adaptando-se a heurística de Clarke & Wright, criando roteiros que são utilizados para a verificação do padrão de carregamento, tendo-se assim uma solução inicial. Em seguida, é aplicada uma busca extensiva na vizinhança com a meta-heurística Iterated Local Search. Para os melhores resultados desta busca, verifica-se se o padrão de carregamento é viável utilizando o algoritmo de George & Robinson adaptado. Nos casos em que não é viável, a meta-heurística Adaptive Large Neighborhood Search é executada na tentativa de se encontrar soluções viáveis para o problema de carregamento. Instâncias da literatura são utilizadas para avaliar a eficiência dos métodos desenvolvidos. Os resultados obtidos para o problema de roteamento separadamente foram de suma importância para assegurar a eficiência do meta-heurística Iterated Local Search. Para o problema de carregamento separadamente, os testes utilizando o algoritmo de George & Robinson adaptado e a meta-heurística Adaptive Large Neighborhood Search também foram satisfatórios, permitindo a obtenção de vários padrões de carregamento factíveis. Os resultados obtidos com o algoritmo proposto para o problema integrado também foram bons, sendo bastante próximos aos da literatura e com tempo computacional relativamente menor. Como perspectivas de pesquisas futuras, pretende-se estudar formas mais eficientes de se explorar o espaço de busca do problema integrado, bem como a utilização de outras meta-heurísticas.

[ES] En esta tesis doctoral se estudia el problema de secuenciación de máquinas paralelas no relacionadas con necesidad de ajustes y recursos adicionales asignados en los ajustes. En este problema, se tiene un grupo de tareas (también llamadas trabajos), donde cada una debe ser procesada en una de las máquinas paralelas disponibles. Para procesar una tarea después de otra en la misma máquina, se debe hacer un ajuste en la máquina. Se asume que estos ajustes deben ser realizados por un recurso adicional limitado (por ejemplo, operarios). En esta tesis doctoral se estudian dos variantes del problema planteado: 1) considerando el problema con el único objetivo de minimizar el tiempo máximo de finalización de todos los trabajos (makespan), y 2) considerando el problema multi-objetivo minimizando simultáneamente el makespan y el consumo máximo de recursos adicionales. Inicialmente, se realiza una completa revisión bibliográfica sobre estudios relacionados con el problema planteado. En esta revisión se detecta que, a pesar de existir numerosos estudios de secuenciación de máquinas paralelas, no muchos de estos estudios tienen en cuenta recursos adicionales. Posteriormente, para introducir el problema a estudiar antes de plantear métodos de resolución, se realiza una breve explicación de los principales problemas de secuenciación de máquinas paralelas. El problema de un solo objetivo está clasificado como NP-Hard. Por ello, para abordar su resolución se han diseñado e implementado heurísticas y metaheurísticas siguiendo dos enfoques diferentes. Para el primer enfoque, que ignora la información sobre el consumo de recursos adicionales en la fase constructiva, se adaptan dos de los mejores algoritmos existentes en la literatura para el problema de máquinas paralelas con ajustes sin necesidad de recursos adicionales. En el segundo enfoque, que sí tiene en cuenta la información sobre el consumo de recursos adicionales en la fase constructiva, se proponen nuevos algoritmos heurísticos y metaheurísticos para resolver el problema. Tras analizar los resultados de los experimentos computacionales realizados, concluimos que hay diferencias entre los dos enfoques, siendo significativamente mejor el enfoque que tiene en cuenta la información sobre los recursos adicionales. Al igual que en el caso de un solo objetivo, la complejidad del problema multi-objetivo obliga a presentar algoritmos heurísticos o metaheurísticos para resolverlo. En esta tesis se presenta un nuevo algoritmo metaheurístico multi-objetivo eficiente para encontrar buenas aproximaciones a la frontera de Pareto del problema. Además, se adaptaron otros tres algoritmos que han mostrado buenos resultados en diferentes estudios de problemas de secuenciación de máquinas multi-objetivo. Después de realizar experimentos computacionales exhaustivos, concluimos que el nuevo algoritmo propuesto en esta tesis es significativamente mejor que los otros tres algoritmos existentes, y que se han adaptado para resolver este problema. / [CAT] En aquesta tesi doctoral s'estudia el problema de seqüenciació de màquines paral·leles no relacionades amb necessitat d'ajustos i recursos addicionals assignats en els ajustos. En aquest problema, es tenen un grup de tasques (també anomenades treballs), on cadascuna ha de ser processada en una de les màquines paral·leles disponibles. Per processar una tasca després d'una altra en la mateixa màquina, s'ha de fer un ajustament en la màquina. S'assumeix que aquests ajustos en les màquines per a processar una tasca després del processament d'una altra, han de ser realitzats per un recurs addicional limitat (per exemple, operaris). En aquesta tesi doctoral s'estudien dos variants al problema plantejat: 1) considerant el problema com l'únic objectiu de minimitzar el temps màxim de finalització de tots els treballs (makespan), i 2) considerant el problema multi-objectiu minimitzant simultàniament el makespan i el consum màxim de recursos addicionals. Inicialment, es realitza una completa revisió bibliogràfica sobre estudis relacionats amb el problema plantejat. En esta revisió es detecta que, tot i existir nombrosos estudis de seqüenciació de màquines paral·leles, hi ha molts pocs que tenen en compte recursos addicionals. Posteriorment, per introduir el problema a estudiar abans de plantejar mètodes de resolució, es realitza una breu explicació dels principals problemes de seqüenciació de màquines paral·leles. El problema d'un sol objectiu està classificat com NP-Hard. Per això, per abordar la seua resolució s'han dissenyat i implementat heurístiques y metaheurístiques seguint dos enfocs diferents. El primer enfoc ignora la informació sobre el consum de recursos en la fase constructiva, adaptant dos dels millors algoritmes existents en la literatura per al problema de seqüenciació de màquines paral·leles amb ajustaments sense necessitat de recursos. Per al segon enfoc si es té en compte la informació sobre el consum de recursos en la fase constructiva. Després d'analitzar els resultats dels experiments computacionals realitzats, concloem que hi ha diferencies entre els dos enfocs, sent significativament millor l'enfoc que té en compte la informació sobre el recursos. De la mateixa manera que en el cas d'un sol objectiu, la complexitat del problema multi-objectiu obliga a presentar algoritmes heurístics o metaheurístics per a resoldre-ho. En aquesta tesi es presenta un nou algoritme metaheurístic multi-objectiu eficient per trobar bones aproximacions a la frontera de Pareto del problema. A més, es van adaptar altres tres algoritmes que han mostrat bons resultats en diferents estudis de problemes de seqüenciació de màquines multi-objectiu. Després de realitzar experiments computacionals exhaustius, concloem que el nou algoritme proposat en aquesta tesi és significativament millor que els altres tres algoritmes existents i que s'han adaptat per resoldre aquest problema. / [EN] In this thesis we study the unrelated parallel machine scheduling problem with setup times and additional limited resources in the setups. In this problem, we have a group of tasks (also called jobs), where each one must be processed on one of the available parallel machines. To process one job after another on the same machine, a setup must be made on the machine. It is assumed that these setups on machines must be made by a limited additional resource (eg, operators). In this thesis two variants of the problem are studied: 1) considering the problem with the objective of minimizing the maximum completion time of all jobs (makespan), and 2) considering the multi-objective problem, minimizing the makespan and the maximum consumption of additional resources. Initially, a complete literature review is carried out on studies related to the problem addressed in this thesis. This review finds that despite numerous parallel machine scheduling studies, there are very few that take into account additional resources. Subsequently, to introduce the problem addressed before proposing resolution methods, a brief explanation of the main parallel machines scheduling problems is made. The problem with a single objective is classified as NP-Hard. Therefore, to solve it, heuristics and metaheuristics have been designed and implemented following two different approaches. For the first approach, which ignores the information on the consumption of resources in the construction phase, two of the best algorithms existing in the literature for the problem of parallel machines with setups without additional resources are adapted. For the second approach, which does take into account information on the consumption of resources in the construction phase, new heuristic and metaheuristic algorithms are proposed to solve the problem. Following the results of the computational experiments, we conclude that there are differences between the two approaches, the approach that takes into account the information on resources being significantly better. As in the case of a single objective, the complexity of the multi-objective problem requires the formulation of heuristic or metaheuristic algorithms to solve it. In this thesis, a new efficient multi-objective metaheuristic algorithm is presented to find good approximations to the Pareto front of the problem. In addition, three other algorithms that have shown good results in different studies of multi-objective machine scheduling problems were adapted. After carrying out exhaustive computational experiments, we concluded that the new algorithm proposed in this thesis is significantly better than the other three adapted algorithms. / Yepes Borrero, JC. (2020). Secuenciación de máquinas con necesidad de ajustes y recursos adicionales [Tesis doctoral]. Universitat Politècnica de València. https://doi.org/10.4995/Thesis/10251/158742

Exploramos o seguinte problema: dadas duas sequências X e Y sobre um alfabeto finito, encontre uma subsequência comum máxima de X e Y sem símbolos repetidos. Estudamos a estrutura deste problema, particularmente do ponto de vista de grafos e de combinatória poliédrica. Desenvolvemos algoritmos de aproximação e heurísticas para este problema. O enfoque deste trabalho está na construção de um algoritmo baseado na técnica branch-and-cut, aproveitando-nos de um algoritmo de separação eficiente e de heurísticas e técnicas para encontrarmos uma solução ótima mais cedo. Também estudamos um problema mais fácil no qual este problema é baseado: dadas duas sequências X e Y sobre um alfabeto finito, encontre uma subsequência comum máxima de X e Y. Exploramos este problema do ponto de vista de combinatória poliédrica e descrevemos vários algoritmos conhecidos para resolvê-lo. / We explore the following problem: given two sequences X and Y over a finite alphabet, find a longest common subsequence of X and Y without repeated symbols. We study the structure of this problem, particularly from the point of view of graphs and polyhedral combinatorics. We develop approximation algorithms and heuristics for this problem. The focus of this work is in the construction of an algorithm based on the branch-and-cut technique, taking advantage of an efficient separation algorithm and of heuristics and techniques to find an optimal solution earlier. We also study an easier problem on which this problem is based: given two sequences X and Y over a finite alphabet, find a longest common subsequence of X and Y. We explore this problem from the point of view of polyhedral combinatorics and describe several known algorithms to solve it.

Este trabalho aborda o problema multiestágio de planejamento e programação da produção em indústrias cervejeiras. O processo de fabricação de cerveja pode ser dividido em duas etapas principais: preparação do líquido e envase. A primeira etapa ocorre, na maior parte do tempo, dentro de tanques de fermentação e maturação. A segunda ocorre nas linhas de envase, podendo ter início assim que o líquido estiver pronto nos tanques. O tempo de preparação do líquido demora vários dias, enquanto que na maioria das indústrias de bebidas carbonatadas este tempo é de no máximo algumas horas. O objetivo deste estudo é obter planos de produção viáveis que visam otimizar as decisões de programação envolvidas nestes processos. Visitas a cervejarias no Brasil e em Portugal foram realizadas para uma maior familiaridade do processo de produção e dados foram coletados. Modelos de programação inteira mista para representar o problema foram desenvolvidos, baseados em abordagens CSLP (The Continuous Setup Lot-Sizing Problem), GLSP (General Lot Sizing and Scheduling Problem), SPL (Simple Plant Location Problem) e ATSP (Asymmetric Travelling Salesman Problem). Os resultados mostram que os modelos são coerentes e representam adequadamente o problema, entretanto, mostram-se difíceis de serem resolvidos na otimalidade. Esta dificuldade de resolução dos modelos motivou o desenvolvimento de procedimentos MIP-heurísticos, como também de uma metaheurística GRASP (Greedy Randomized Adaptive Search Procedure). As soluções obtidas pelos procedimentos heurísticos são de boa qualidade, quando comparadas ao melhor limitante inferior encontrado por meio da resolução dos modelos matemáticos. Os testes computacionais foram realizados utilizando instâncias geradas com base em dados reais. / This study deals with the multistage lot-sizing and scheduling problem in breweries. The brewing process can be divided into two main stages: preparation and filling of the liquid. The first stage occurs most of the time in fermentation and maturation tanks. The second stage occurs in the filling lines and it can start as soon as the liquid gets ready. The preparation time of the liquid takes several days, while in the carbonated beverage industries this time is at most a few hours. The purpose of this study is to obtain feasible production plans aimed at optimizing the decisions involved in these processes. Visits to brewery industries in Brazil and Portugal were held to a greater familiarity of the production process and data were collected. Mixed integer programming models have been developed to represent the problem, based on approaches for the CSLP (The Continuous Setup Lot-Sizing Problem), GLSP (General Lot Sizing and Scheduling Problem), SPL (Simple Plant Location Problem) and ATSP (Asymmetric Travelling Salesman Problem). The results show that the models are consistent and adequately represent the problem; however, they are difficult to be solved at optimality. This motivated the development of MIP-heuristic procedures, as well as a meta-heuristic GRASP (Greedy Randomized Adaptive Search Procedure). The obtained solutions by the heuristics are of good quality, when compared to the best lower bound found by solving the mathematical models. The tests were conducted using generated instances based on real data.