O problema de dimensionamento de lotes, objeto desse estudo, considera um ambiente composto por múltiplas plantas independentes, múltiplos itens e múltiplos períodos. O ambiente de produção tem capacidade limitada e as plantas podem produzir os mesmos itens. Cada planta tem uma demanda própria e é permitida a transferência de lotes entre as plantas, o que envolve um certo custo. Este problema tem como caso particular o de dimensionamento de lotes com máquinas paralelas. O objetivo desta dissertação é propor uma heurística baseada na meta-heurística GRASP (Greedy Randomized Adaptive Search Procedures). Além disso, uma estratégia path relinking foi incorporada ao GRASP como uma fase de melhoria do algoritmo. Para verificar a eficiência da heurística proposta, os seus resultados são comparados aos da literatura tanto no caso de máquinas paralelas quanto no de múltiplas plantas. Como resultado, o problema de múltiplas plantas obteve melhores resultados quando comparado aos da heurística da literatura. Com relação ao problema de máquinas paralelas, a heurística proposta se mostrou competitiva / The lot sizing problem, which is the aim of this study, considers an environment consisting of multiple independent plants, multiple items and multiple periods. The production environment has limited capacity and the plants can produce the same items. Each plant has its own demand and the lot transfers between the plants are permitted, which involves a certain cost. This problem has as a particular case the parallel machines lot sizing problem. The objective of this dissertation is to propose a heuristic based on the GRASP (Greedy Randomized Adaptive Search Procedures). Furthermore, a path relinking phase is embedded in the GRASP to obtain better performance. To verify the efficiency of the proposed heuristic, its results were compared with the literature as for the multi-plant as for parallel machines problem. Computational tests showed that the proposed heuristic performed better than other literature heuristic concerning the multiplant problem. Concerning the parallel machines, the heuristic is competitive

[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

Coordenação de Aperfeiçoamento de Pessoal de Nível Superior / The evolution of computer hardware as well as new applications of mathematical programming techniques, efficiently implemented in many commercial solvers, has given rise to new algorithms called hybrid metaheuristic, which have been applied to solve combinatorial problems. This work presents several approaches which try to deal with the hybridization of local search based metaheuristics with exact algorithms to solve two problems of combinatorial optimization. More specifically, the first problem, capacitated p-median problem, the proposed approach considers heuristic elimination of variable of the original mathematical model, that produce solutions of very good quality in a short amount of time, and a combination with an iterative procedure in which only a certain subset of points is considered. As regards the second problem, unrelated parallel machine scheduling with sequence and machine dependent setup time problem of minimizing makespan, is proposed a mathematical model to search the neighborhood of a solution and identify movement sequences to minimize the objective function. In both cases, mathematical models are solved using a commercial solver. Extensive computational experiments are carried out to demonstrate the good performance of the proposed approaches. / A recente evolução dos computadores como também dos métodos exatos oriundos da programação matemática, muitos destes eficientemente implementados em otimizadores comerciais, propiciou o surgimento de novos algoritmos, denominados metaheurísticas híbridas, que têm sido aplicados para resolução de problemas combinatoriais. Este trabalho apresenta abordagens que hibridizam metaheurísticas baseadas em busca local com algoritmos exatos de programação matemática para resolver dois problemas de otimização combinatória. Mais especificamente, para o primeiro problema, o problema das p-medianas capacitado, a proposta considera a eliminação heurística de variáveis do modelo matemático, que permite a obtenção de soluções de boa qualidade em um curto tempo computacional, e a combinação com um procedimento iterativo no qual apenas um determinado subconjunto de pontos é considerado. No que se refere ao segundo problema, programação de tarefas em máquinas paralelas não relacionadas com tempo de preparação dependente da sequência e da máquina com objetivo de minimizar o tempo de processamento total da máquina com maior carga entre todas (makespan), propõe-se um modelo matemático para varrer a vizinhança de uma solução e identificar sequências de movimentos de tarefas que podem ser aplicadas na respectiva solução de modo a minimizar a função objetivo. Nos dois casos os modelos matemáticos são resolvidos utilizando um otimizador comercial. Extensivos testes computacionais são realizados para demonstrar o bom desempenho das abordagens propostas.