Search

In this paper, we propose a new approach for including quay crane travel and setup times in the berth allocation and quay crane assignment problem. We first develop a new mixed integer linear programming model (MILP) for the problem without setups (BACASP), in which berthing positions and times are considered as continuous variables. Several groups of valid inequalities are also set forth. Then, for the BACASP with crane travel and setup times, which we denote as BACASP-S, we propose two MILPs: the first is based on the previous BACASP formulation and the second on routing formulations. Due to the complexity of the BACASP-S, we also propose a genetic algorithm and an exact approach which combines various MILPs with the genetic algorithm. All methods and valid inequalities are computationally tested over two different sets of randomly generated instances. According to the results, the models and algorithms can optimally solve, in less than one hour, BACASP-S instances of up to 40 vessels within a quay one kilometer long and a time horizon of one week. Additionally, extensive experiments were conducted on a new large set of instances to assess the effect of various BACASP-S input parameters on the computation effort required to solve the problem. Ceteris paribus, the computational effort required seems to increase with decreasing number of cranes, while vessel processing times and crane setup times seem not to affect it.

This article deals with one of the types of “Satellite Range Scheduling” problems arising in Earth Observation Satellite operations, Antenna-Satellite Scheduling. Given a set of satellites, a set of available antennas and a time horizon, the problem consists of designing an operational plan that assigns satellites to antennas in an optimal fashion. Extending a previous integer linear programming (ILP) model (shortening model, with only integer variables), we propose a mixed ILP (MILP) (shaving model, which includes both continuous and integer variables), to more efficiently solve this problem. After computing the passes generated by the satellites' windows of visibility from the antennas, the optimal planner is able to cancel a pass, move it to another antenna, or shorten its duration, in order to avoid scheduling conflicts. In contrast to the shortening model, which used intersections between passes to determine the best schedule, the shortening operation is now referred to as shaving, since the shaving model can arbitrarily adjust the duration of a pass in a razor-like fashion, giving the model its name. Computational results obtained in tests over realistic scenarios prove that the shaving model outperforms the shortening model, producing fewer cancellations, smaller shaved times, and a fairer distribution of cancelled passes among satellites, with much shorter preprocessing times.

In this paper, we propose a new approach for including quay crane travel and setup times in the berth allocation and quay crane assignment problem. We first develop a new mixed integer linear programming model (MILP) for the problem without setups (BACASP), in which berthing positions and times are considered as continuous variables. Several groups of valid inequalities are also set forth. Then, for the BACASP with crane travel and setup times, which we denote as BACASP-S, we propose two MILPs: the first is based on the previous BACASP formulation and the second on routing formulations. Due to the complexity of the BACASP-S, we also propose a genetic algorithm and an exact approach which combines various MILPs with the genetic algorithm. All methods and valid inequalities are computationally tested over two different sets of randomly generated instances. According to the results, the models and algorithms can optimally solve, in less than one hour, BACASP-S instances of up to 40 vessels within a quay one kilometer long and a time horizon of one week. Additionally, extensive experiments were conducted on a new large set of instances to assess the effect of various BACASP-S input parameters on the computation effort required to solve the problem. Ceteris paribus, the computational effort required seems to increase with decreasing number of cranes, while vessel processing times and crane setup times seem not to affect it.

El propósito de este proyecto consiste en crear un modelo de programación lineal entera mixta que pueda ser utilizado por los equipos de Fórmula 1 para determinar la mejor estrategia de carrera. El modelo considerará varios parámetros, como la degradación de los neumáticos basada en datos de tiempos por vuelta de la temporada 2020/2021 de la Fórmula 1, y también el reglamento actual de la Federación Internacional del Automóvil (FIA). Aunque el modelo no tendrá en cuenta la presencia de otros competidores, determinará cuándo debe ingresar el coche a boxes para completar la carrera en el menor tiempo posible. Para evaluar la precisión del modelo, se compararán sus resultados con los de carreras reales., The goal of this project is to build a mixed integer linear programming model that can be used by Formula 1 teams to determine the optimal race strategy in the presence of a number of parameters that influence it. The model takes into account tyre degradation, based on lap time data observed during 2020/2021 Formula 1 season, and also the current FIA (Federation Internationale de l’Automobile) regulations. No other competitors are considered in the model, but we will determine which laps the car should enter to finish the race in the shortest time possible. The results will be compared with the results of real races to see the differences.

El diseño de un modelo matemático exacto para la planificación de redes de tránsito rápido en una ciudad es posible, pero no es una tarea sencilla debido a la complejidad y la cantidad de variables involucradas. Como se ha introducido anteriormente, requiere una planificación cuidadosa y una consideración de varios factores, como las necesidades de transporte de la ciudad, el crecimiento futuro, las características topográficas y la demanda de transporte. El uso de modelos matemáticos en el diseño de una red de tránsito rápido en una ciudad es cada vez más común. Los modelos matemáticos pueden ayudar a los planificadores de transporte a analizar diferentes opciones de rutas, evaluar la demanda de pasajeros y determinar la capacidad necesaria para el sistema. Por otro lado, los modelos matemáticos también pueden ayudar a optimizar la ubicación de las estaciones, la frecuencia de los trenes y otros aspectosimportantes del diseño de la red de tránsito rápido. Además, estos modelos pueden ser útiles para simular diferentes escenarios y evaluar el impacto de posibles cambios en la red en términos de tiempos de viaje, capacidad, costes, y otros aspectos. No obstante, los modelos matemáticos avanzados que se han desarrollado para la planificación de redes de transporte son de alto coste, y requieren una cantidad significativa de recursos y tiempo para desarrollarse y mantenerse actualizados. Adicionalmente, la utilización de modelos matemáticos en el diseño de una red de tránsito rápido depende en gran medida de la disponibilidad de datos precisos y actualizados, así como de los recursos financieros y técnicos necesarios para llevar a cabo la planificación y construcción del sistema. Esto hace, que se dificulte su aplicación matemática, dado que es importante tener en cuenta las limitaciones y posibilidades de los solvers que resuelven los modelos matemáticos en función de las condiciones específicas de cada proyecto. Es por esta razón, que a lo largo de este capítulo se e

Machine scheduling problems arise in many production processes, and are something that needs to be consider when optimizing the supply chain. Among them, flowshop scheduling problems happen when a number of jobs have to be sequentially processed by a number of machines. This paper addressees, for the first time, the Permutation Flowshop Scheduling problem with additional Resources during Setups (PFSR-S). In this problem, in addition to the standard permutation flowshop constraints, each machine requires a setup between the processing of two consecutive jobs. A number of additional and scarce resources, e.g. operators, are needed to carry out each setup. Two Mixed Integer Linear Programming formulations and an exact algorithm are proposed to solve the PFSR-S. Due to its complexity, these approaches can only solve instances of small size to optimality. Therefore, a GRASP metaheuristic is also proposed which provides solutions for much larger instances. All the methods designed for the PFSR-S in this paper are computationally tested over a benchmark of instances adapted from the literature. The results obtained show that the GRASP metaheuristic finds good quality solutions in short computational times.

Firms’ growth, the darling measure of investors, comes from higher revenues. Thus, sales and marketing departments make extreme efforts to accept as many customer orders as possible. Unfortunately, not all orders contribute equally to profits, and some orders may even reduce net profits. Thus, saying no (i.e., not accepting an order) may be a necessary condition for net profits growth. For understanding the impact of rejecting orders on profitability, we propose an order acceptance and scheduling problem (OAS). Although the OAS has extensively been studied in the literature, there is still some gap between these papers and real-life problems in industry. In an attempt to close that gap, the OAS we propose considers orders revenues, machines costs, holding costs and tardiness costs. We develop a mixed integer linear programming (MILP) model for solving this problem. Since the complexity of the problem makes it impossible for the MILP to solver large-scale instances, we also propose a metaheuristic algorithm. Numerical experiments show that the metaheuristic finds good quality solutions in short computational times. In the last part of the paper we confirm some managerial insights: higher holding and tardiness costs imply a lower acceptance of orders, forcing production has a concave negative impact on net profits, and accurately estimating costs is essential for good planning.

Firms’ growth, the darling measure of investors, comes from higher revenues. Thus, sales and marketing departments make extreme efforts to accept as many customer orders as possible. Unfortunately, not all orders contribute equally to profits, and some orders may even reduce net profits. Thus, saying no (i.e., not accepting an order) may be a necessary condition for net profits growth. For understanding the impact of rejecting orders on profitability, we propose an order acceptance and scheduling problem (OAS). Although the OAS has extensively been studied in the literature, there is still some gap between these papers and real-life problems in industry. In an attempt to close that gap, the OAS we propose considers orders revenues, machines costs, holding costs and tardiness costs. We develop a mixed integer linear programming (MILP) model for solving this problem. Since the complexity of the problem makes it impossible for the MILP to solver large-scale instances, we also propose a metaheuristic algorithm. Numerical experiments show that the metaheuristic finds good quality solutions in short computational times. In the last part of the paper we confirm some managerial insights: higher holding and tardiness costs imply a lower acceptance of orders, forcing production has a concave negative impact on net profits, and accurately estimating costs is essential for good planning.

Machine scheduling problems arise in many production processes, and are something that needs to be consider when optimizing the supply chain. Among them, flowshop scheduling problems happen when a number of jobs have to be sequentially processed by a number of machines. This paper addressees, for the first time, the Permutation Flowshop Scheduling problem with additional Resources during Setups (PFSR-S). In this problem, in addition to the standard permutation flowshop constraints, each machine requires a setup between the processing of two consecutive jobs. A number of additional and scarce resources, e.g. operators, are needed to carry out each setup. Two Mixed Integer Linear Programming formulations and an exact algorithm are proposed to solve the PFSR-S. Due to its complexity, these approaches can only solve instances of small size to optimality. Therefore, a GRASP metaheuristic is also proposed which provides solutions for much larger instances. All the methods designed for the PFSR-S in this paper are computationally tested over a benchmark of instances adapted from the literature. The results obtained show that the GRASP metaheuristic finds good quality solutions in short computational times.

Firms’ growth, the darling measure of investors, comes from higher revenues. Thus, sales and marketing departments make extreme efforts to accept as many customer orders as possible. Unfortunately, not all orders contribute equally to profits, and some orders may even reduce net profits. Thus, saying no (i.e., not accepting an order) may be a necessary condition for net profits growth. For understanding the impact of rejecting orders on profitability, we propose an order acceptance and scheduling problem (OAS). Although the OAS has extensively been studied in the literature, there is still some gap between these papers and real-life problems in industry. In an attempt to close that gap, the OAS we propose considers orders revenues, machines costs, holding costs and tardiness costs. We develop a mixed integer linear programming (MILP) model for solving this problem. Since the complexity of the problem makes it impossible for the MILP to solver large-scale instances, we also propose a metaheuristic algorithm. Numerical experiments show that the metaheuristic finds good quality solutions in short computational times. In the last part of the paper we confirm some managerial insights: higher holding and tardiness costs imply a lower acceptance of orders, forcing production has a concave negative impact on net profits, and accurately estimating costs is essential for good planning.

Firms’ growth, the darling measure of investors, comes from higher revenues. Thus, sales and marketing departments make extreme efforts to accept as many customer orders as possible. Unfortunately, not all orders contribute equally to profits, and some orders may even reduce net profits. Thus, saying no (i.e., not accepting an order) may be a necessary condition for net profits growth. For understanding the impact of rejecting orders on profitability, we propose an order acceptance and scheduling problem (OAS). Although the OAS has extensively been studied in the literature, there is still some gap between these papers and real-life problems in industry. In an attempt to close that gap, the OAS we propose considers orders revenues, machines costs, holding costs and tardiness costs. We develop a mixed integer linear programming (MILP) model for solving this problem. Since the complexity of the problem makes it impossible for the MILP to solver large-scale instances, we also propose a metaheuristic algorithm. Numerical experiments show that the metaheuristic finds good quality solutions in short computational times. In the last part of the paper we confirm some managerial insights: higher holding and tardiness costs imply a lower acceptance of orders, forcing production has a concave negative impact on net profits, and accurately estimating costs is essential for good planning.

As a consequence of globalization, interactions among countries, companies, people, etc, have been increased during recent decades. The basic mathematical support structure for modeling such interactions is a network. Thus, Network Design plays an important role for facilitating the interactions. Nevertheless, %Network Design Problems have been studied since the interest of modelling the interaction between a set of individuals became to gain importance. Nevertheless, the majority of Network Design problems are difficult to solve. Our goal is to study them from the Combinatorial Optimization point of view to find exact and metaheuristic \mbox{approaches} that improve the process of getting optimal ,or at least good, solutions for practical applications. In this thesis, we study some Network Design problems, which can be grouped into two large classes detailed below, according to the main feature of each one. In all the problems it is considered that the demand is given by a set of pairs of origin-destination points. That is, each demand has to move from an origin-node to a destination-node. Another feature in common is the existence of an alternative network that can be used by the demand set. In this situation, the possible existing competition between the network to be designed and the already actual alternative network has been highlighted. On the one hand, Chapters 2, 3 and 4 deal with Covering Network Design \mbox{problems}. These problems seek to design a network in such a way that the proportion of demand covered is maximized or exceeds a certain percentage of the total. Particularly, the third chapter shows a practical application for Network Design in the transportation area. On the other hand, Chapter 5 extends the existing notions in Facility Location Theory of $\lambda$-Cent-Dian and Generalized-Center to the area of Network Design. The problems in this chapter are focused on designing a network that minimizes the maximum distance of a known set of origi, Doctorat en Sciences, info:eu-repo/semantics/nonPublished

The aim of this paper is to introduce the Flexible Periodic Vehicle Routing Problem with Heterogeneous Fleet, a variant of the Periodic Vehicle Routing Problem. Flexibility is introduced in service schedules and delivered quantities, heterogeneity comes from different vehicles capacities and speeds. Three Mixed-Integer Linear Programming formulations and a matheuristic, based on Kernel Search, are proposed. Computational tests are made to evaluate the performance of the three formulations and to assess the quality of the solutions provided by the matheuristic.

The aim of this paper is to introduce the Flexible Periodic Vehicle Routing Problem with Heterogeneous Fleet, a variant of the Periodic Vehicle Routing Problem. Flexibility is introduced in service schedules and delivered quantities, heterogeneity comes from different vehicles capacities and speeds. Three Mixed-Integer Linear Programming formulations and a matheuristic, based on Kernel Search, are proposed. Computational tests are made to evaluate the performance of the three formulations and to assess the quality of the solutions provided by the matheuristic.

The aim of this paper is to introduce the Flexible Periodic Vehicle Routing Problem with Heterogeneous Fleet, a variant of the Periodic Vehicle Routing Problem. Flexibility is introduced in service schedules and delivered quantities, heterogeneity comes from different vehicles capacities and speeds. Three Mixed-Integer Linear Programming formulations and a matheuristic, based on Kernel Search, are proposed. Computational tests are made to evaluate the performance of the three formulations and to assess the quality of the solutions provided by the matheuristic.

[ES] En el presente trabajo se aborda la optimización de la secuenciación de la producción en una empresa del sector de los aerosoles; concretamente, de su línea de productos para el hogar. Se trata de una situación real y no de un caso de estudio. La empresa necesita planificar la secuenciación de las órdenes de producción que se reciben diariamente, de modo que se reduzcan los tiempos de transición. El trabajo comprende tanto la modelización matemática del problema como la elaboración de una solución informática que permita obtener una secuencia de producción óptima. Asimismo, se evalúa la eficiencia y el ahorro de coste de esta metodología comparando los resultados que esta ofrece frente a datos reales de producción. Por último, se evalúa la capacidad de la solución informática desarrollada para abordar problemas de mayor tamaño, desde el punto de vista de la cantidad de trabajos a secuenciar., [EN] In this Project, production sequencing optimization in an aerosol sector company is approached, specifically in its home care products line. It is actually a real case found during my internship at a company, not a study case. The company needs to plan the sequence of the production orders daily received, in a way that transition times are reduced. The project involves mathematical modelling as well as the development of a software solution that enables to obtain an optimal production sequence. Moreover, the efficiency and cost saving of this methodology is evaluated comparing the results it offers with the real production data. Finally, the capacity of the software solution developed is evaluated for bigger size problems, from a number of jobs to sequence point of view.

[ES] En el presente trabajo se aborda la optimización de la secuenciación de la producción en una empresa del sector de los aerosoles; concretamente, de su línea de productos para el hogar. Se trata de una situación real y no de un caso de estudio. La empresa necesita planificar la secuenciación de las órdenes de producción que se reciben diariamente, de modo que se reduzcan los tiempos de transición. El trabajo comprende tanto la modelización matemática del problema como la elaboración de una solución informática que permita obtener una secuencia de producción óptima. Asimismo, se evalúa la eficiencia y el ahorro de coste de esta metodología comparando los resultados que esta ofrece frente a datos reales de producción. Por último, se evalúa la capacidad de la solución informática desarrollada para abordar problemas de mayor tamaño, desde el punto de vista de la cantidad de trabajos a secuenciar., [EN] In this Project, production sequencing optimization in an aerosol sector company is approached, specifically in its home care products line. It is actually a real case found during my internship at a company, not a study case. The company needs to plan the sequence of the production orders daily received, in a way that transition times are reduced. The project involves mathematical modelling as well as the development of a software solution that enables to obtain an optimal production sequence. Moreover, the efficiency and cost saving of this methodology is evaluated comparing the results it offers with the real production data. Finally, the capacity of the software solution developed is evaluated for bigger size problems, from a number of jobs to sequence point of view.

[ES] En el presente trabajo se aborda la optimización de la secuenciación de la producción en una empresa del sector de los aerosoles; concretamente, de su línea de productos para el hogar. Se trata de una situación real y no de un caso de estudio. La empresa necesita planificar la secuenciación de las órdenes de producción que se reciben diariamente, de modo que se reduzcan los tiempos de transición. El trabajo comprende tanto la modelización matemática del problema como la elaboración de una solución informática que permita obtener una secuencia de producción óptima. Asimismo, se evalúa la eficiencia y el ahorro de coste de esta metodología comparando los resultados que esta ofrece frente a datos reales de producción. Por último, se evalúa la capacidad de la solución informática desarrollada para abordar problemas de mayor tamaño, desde el punto de vista de la cantidad de trabajos a secuenciar., [EN] In this Project, production sequencing optimization in an aerosol sector company is approached, specifically in its home care products line. It is actually a real case found during my internship at a company, not a study case. The company needs to plan the sequence of the production orders daily received, in a way that transition times are reduced. The project involves mathematical modelling as well as the development of a software solution that enables to obtain an optimal production sequence. Moreover, the efficiency and cost saving of this methodology is evaluated comparing the results it offers with the real production data. Finally, the capacity of the software solution developed is evaluated for bigger size problems, from a number of jobs to sequence point of view.

[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, [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'anal, [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 accoun

[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, [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'anal, [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 accoun

[ES] En el presente trabajo se aborda la optimización de la secuenciación de la producción en una empresa del sector de los aerosoles; concretamente, de su línea de productos para el hogar. Se trata de una situación real y no de un caso de estudio. La empresa necesita planificar la secuenciación de las órdenes de producción que se reciben diariamente, de modo que se reduzcan los tiempos de transición. El trabajo comprende tanto la modelización matemática del problema como la elaboración de una solución informática que permita obtener una secuencia de producción óptima. Asimismo, se evalúa la eficiencia y el ahorro de coste de esta metodología comparando los resultados que esta ofrece frente a datos reales de producción. Por último, se evalúa la capacidad de la solución informática desarrollada para abordar problemas de mayor tamaño, desde el punto de vista de la cantidad de trabajos a secuenciar., [EN] In this Project, production sequencing optimization in an aerosol sector company is approached, specifically in its home care products line. It is actually a real case found during my internship at a company, not a study case. The company needs to plan the sequence of the production orders daily received, in a way that transition times are reduced. The project involves mathematical modelling as well as the development of a software solution that enables to obtain an optimal production sequence. Moreover, the efficiency and cost saving of this methodology is evaluated comparing the results it offers with the real production data. Finally, the capacity of the software solution developed is evaluated for bigger size problems, from a number of jobs to sequence point of view.

[ES] En este trabajo se pretende resolver el problema de secuenciación de máquinas paralelas no relacionadas con ajustes entre trabajos y recursos limitados adicionales. El objetivo del problema es minimizar el tiempo de finalización del último trabajo en ser procesado (makespan). Este makespan puede ser determinante para cualquier empresa con una cadena de producción a la hora de cumplir plazos de entrega o mejorar la productividad. Para abordar este problema se diseñarán e implementarán heurísticas que estarán formadas por dos fases: una fase constructiva donde se obtendrá una primera solución del problema, y una fase de reparación donde se arreglará la solución obtenida en la fase anterior si se supera el número de recursos permitidos. Además, para conseguir una mayor diversidad de soluciones, se aleatorizará parte de la fase constructiva, convirtiendo las heurísticas en metaheurísticas. Más adelante se realizará una extensa fase de experimentos y posterior análisis, en el que se probarán diferentes versiones de las heurísticas y metaheurísticas variando diferentes factores. A continuación, se compararán los resultados obtenidos por los algoritmos propuestos, con los logrados previamente para el mismo problema por un modelo de programación lineal entera (MILP, por sus siglas en inglés Mixed Integer Linear Program). La conclusión principal de estos experimentos es que, con un tiempo de proceso muy inferior, se pueden casi igualar y en algunos casos mejorar los resultados de este modelo utilizando los algoritmos heurísticos y metaheurísticos propuestos., [EN] This project aims to solve the unrelated parallel machines scheduling problem with adjustments between jobs and additional limited resources. The goal of this problem is to minimize the completion time of the last job (makespan). This makespan can be decisive for any business with production chains when it comes to respect deadlines or improving productivity. To engage this problem, design and implementation of heuristics and metaheuristics will be done, and they will be split in two phases: a constructive phase where a first solution will be obtained, and a repair phase where this solution will be fixed in case of exceeding the resources limit. Furthermore, to achieve a major diversity of solutions, part of the construction phase will be randomized, transforming heuristics into metaheuristics. Later, an extensive experiments phase will be done with a proper analysis, where different versions of the heuristics and metaheuristics will be tested varying different factors. Next, the results obtained will be compared with the ones achieved for the same problem by an integer linear programming model (MILP). The main conclusion of these experiments is that, with much less processing time, the results obtained with the model are similar or in some instances even worse, compared to the ones achieved with the proposed heuristic and metaheuristic algorithms., [CA] En aquest treball es tracta de resoldre el problema de seqüenciació de màquines paral·leles no relacionades amb ajustos entre treballs i recursos limitats adicionals. L’objectiu del problema es minimitzar el temps de finalització de l’últim treball a ser processat (makespan). Este makespan pot ser determinant per a qualsevol empresa amb una cadena de producció a l’hora de complir terminis de lliurament o millorar la productivitat. Per a abordar aquest problema es dissenyaran e implementaran heurístiques que estaran formades per dues fases: una fase constructiva on s’obtindrà una primera solució del problema, i una fase de reparació on s’arreglarà la solució obtinguda en la fase anterior si es supera el nombre de recursos permitits. A més, per a aconseguir una major diversitat de solucions, s’aleatoritzarà part de la fase construcitva, convertint les heurístiques en metaheurístiques. Més endavant es realitzarà una extensa fase d’experiments i posterior anàlisi, en el qual es provaran diferents versions de les heurístiques i metaheurístiques variant diferents factors. A continuació, es compararan els resultats obtinguts pels algorismes proposats, amb els reeixits prèviament per al mateix problema obtinguts amb un model de programació lineal sencera (MILP, per les seues sigles en anglés Mixed Integer Linear Program). La conclusió principal d’aquests experiments és que, amb un temps de procés molt inferior, es poden quasi igualar i en alguns casos millorar els resultats d’aquest model utilitzant els algorismes heurístics i metaheurístics proposats.

[EN] In this paper we analyze the computational complexity of transportation infrastructure network design problems, in the presence of a competing transportation mode. Some of these problems have previously been introduced in the literature. All problems studied have a common objective: the maximization of the number of travelers using the new network to be built. The differences between them are due to two factors. The first one is the constraints that the new network should satisfy: (1) budget constraint, (2) no-cycle constraint, (3) both constraints. The second factor is the topology of the network formed by the feasible links and stations: (1) a general network, (2) a forest. By combining these two factors, in total we analyze six problems, five of them are shown to be NP-hard, the sixth being trivial. Due to the NP-hardness of these problems, a genetic algorithm is proposed. Computational experiments show the applicability of this algorithm.

[EN] In this paper we analyze the computational complexity of transportation infrastructure network design problems, in the presence of a competing transportation mode. Some of these problems have previously been introduced in the literature. All problems studied have a common objective: the maximization of the number of travelers using the new network to be built. The differences between them are due to two factors. The first one is the constraints that the new network should satisfy: (1) budget constraint, (2) no-cycle constraint, (3) both constraints. The second factor is the topology of the network formed by the feasible links and stations: (1) a general network, (2) a forest. By combining these two factors, in total we analyze six problems, five of them are shown to be NP-hard, the sixth being trivial. Due to the NP-hardness of these problems, a genetic algorithm is proposed. Computational experiments show the applicability of this algorithm.

[ES] En este trabajo se pretende resolver el problema de secuenciación de máquinas paralelas no relacionadas con ajustes entre trabajos y recursos limitados adicionales. El objetivo del problema es minimizar el tiempo de finalización del último trabajo en ser procesado (makespan). Este makespan puede ser determinante para cualquier empresa con una cadena de producción a la hora de cumplir plazos de entrega o mejorar la productividad. Para abordar este problema se diseñarán e implementarán heurísticas que estarán formadas por dos fases: una fase constructiva donde se obtendrá una primera solución del problema, y una fase de reparación donde se arreglará la solución obtenida en la fase anterior si se supera el número de recursos permitidos. Además, para conseguir una mayor diversidad de soluciones, se aleatorizará parte de la fase constructiva, convirtiendo las heurísticas en metaheurísticas. Más adelante se realizará una extensa fase de experimentos y posterior análisis, en el que se probarán diferentes versiones de las heurísticas y metaheurísticas variando diferentes factores. A continuación, se compararán los resultados obtenidos por los algoritmos propuestos, con los logrados previamente para el mismo problema por un modelo de programación lineal entera (MILP, por sus siglas en inglés Mixed Integer Linear Program). La conclusión principal de estos experimentos es que, con un tiempo de proceso muy inferior, se pueden casi igualar y en algunos casos mejorar los resultados de este modelo utilizando los algoritmos heurísticos y metaheurísticos propuestos., [EN] This project aims to solve the unrelated parallel machines scheduling problem with adjustments between jobs and additional limited resources. The goal of this problem is to minimize the completion time of the last job (makespan). This makespan can be decisive for any business with production chains when it comes to respect deadlines or improving productivity. To engage this problem, design and implementation of heuristics and metaheuristics will be done, and they will be split in two phases: a constructive phase where a first solution will be obtained, and a repair phase where this solution will be fixed in case of exceeding the resources limit. Furthermore, to achieve a major diversity of solutions, part of the construction phase will be randomized, transforming heuristics into metaheuristics. Later, an extensive experiments phase will be done with a proper analysis, where different versions of the heuristics and metaheuristics will be tested varying different factors. Next, the results obtained will be compared with the ones achieved for the same problem by an integer linear programming model (MILP). The main conclusion of these experiments is that, with much less processing time, the results obtained with the model are similar or in some instances even worse, compared to the ones achieved with the proposed heuristic and metaheuristic algorithms., [CA] En aquest treball es tracta de resoldre el problema de seqüenciació de màquines paral·leles no relacionades amb ajustos entre treballs i recursos limitats adicionals. L’objectiu del problema es minimitzar el temps de finalització de l’últim treball a ser processat (makespan). Este makespan pot ser determinant per a qualsevol empresa amb una cadena de producció a l’hora de complir terminis de lliurament o millorar la productivitat. Per a abordar aquest problema es dissenyaran e implementaran heurístiques que estaran formades per dues fases: una fase constructiva on s’obtindrà una primera solució del problema, i una fase de reparació on s’arreglarà la solució obtinguda en la fase anterior si es supera el nombre de recursos permitits. A més, per a aconseguir una major diversitat de solucions, s’aleatoritzarà part de la fase construcitva, convertint les heurístiques en metaheurístiques. Més endavant es realitzarà una extensa fase d’experiments i posterior anàlisi, en el qual es provaran diferents versions de les heurístiques i metaheurístiques variant diferents factors. A continuació, es compararan els resultats obtinguts pels algorismes proposats, amb els reeixits prèviament per al mateix problema obtinguts amb un model de programació lineal sencera (MILP, per les seues sigles en anglés Mixed Integer Linear Program). La conclusió principal d’aquests experiments és que, amb un temps de procés molt inferior, es poden quasi igualar i en alguns casos millorar els resultats d’aquest model utilitzant els algorismes heurístics i metaheurístics proposats.

[ES] En este trabajo se pretende resolver el problema de secuenciación de máquinas paralelas no relacionadas con ajustes entre trabajos y recursos limitados adicionales. El objetivo del problema es minimizar el tiempo de finalización del último trabajo en ser procesado (makespan). Este makespan puede ser determinante para cualquier empresa con una cadena de producción a la hora de cumplir plazos de entrega o mejorar la productividad. Para abordar este problema se diseñarán e implementarán heurísticas que estarán formadas por dos fases: una fase constructiva donde se obtendrá una primera solución del problema, y una fase de reparación donde se arreglará la solución obtenida en la fase anterior si se supera el número de recursos permitidos. Además, para conseguir una mayor diversidad de soluciones, se aleatorizará parte de la fase constructiva, convirtiendo las heurísticas en metaheurísticas. Más adelante se realizará una extensa fase de experimentos y posterior análisis, en el que se probarán diferentes versiones de las heurísticas y metaheurísticas variando diferentes factores. A continuación, se compararán los resultados obtenidos por los algoritmos propuestos, con los logrados previamente para el mismo problema por un modelo de programación lineal entera (MILP, por sus siglas en inglés Mixed Integer Linear Program). La conclusión principal de estos experimentos es que, con un tiempo de proceso muy inferior, se pueden casi igualar y en algunos casos mejorar los resultados de este modelo utilizando los algoritmos heurísticos y metaheurísticos propuestos., [EN] This project aims to solve the unrelated parallel machines scheduling problem with adjustments between jobs and additional limited resources. The goal of this problem is to minimize the completion time of the last job (makespan). This makespan can be decisive for any business with production chains when it comes to respect deadlines or improving productivity. To engage this problem, design and implementation of heuristics and metaheuristics will be done, and they will be split in two phases: a constructive phase where a first solution will be obtained, and a repair phase where this solution will be fixed in case of exceeding the resources limit. Furthermore, to achieve a major diversity of solutions, part of the construction phase will be randomized, transforming heuristics into metaheuristics. Later, an extensive experiments phase will be done with a proper analysis, where different versions of the heuristics and metaheuristics will be tested varying different factors. Next, the results obtained will be compared with the ones achieved for the same problem by an integer linear programming model (MILP). The main conclusion of these experiments is that, with much less processing time, the results obtained with the model are similar or in some instances even worse, compared to the ones achieved with the proposed heuristic and metaheuristic algorithms., [CA] En aquest treball es tracta de resoldre el problema de seqüenciació de màquines paral·leles no relacionades amb ajustos entre treballs i recursos limitats adicionals. L’objectiu del problema es minimitzar el temps de finalització de l’últim treball a ser processat (makespan). Este makespan pot ser determinant per a qualsevol empresa amb una cadena de producció a l’hora de complir terminis de lliurament o millorar la productivitat. Per a abordar aquest problema es dissenyaran e implementaran heurístiques que estaran formades per dues fases: una fase constructiva on s’obtindrà una primera solució del problema, i una fase de reparació on s’arreglarà la solució obtinguda en la fase anterior si es supera el nombre de recursos permitits. A més, per a aconseguir una major diversitat de solucions, s’aleatoritzarà part de la fase construcitva, convertint les heurístiques en metaheurístiques. Més endavant es realitzarà una extensa fase d’experiments i posterior anàlisi, en el qual es provaran diferents versions de les heurístiques i metaheurístiques variant diferents factors. A continuació, es compararan els resultats obtinguts pels algorismes proposats, amb els reeixits prèviament per al mateix problema obtinguts amb un model de programació lineal sencera (MILP, per les seues sigles en anglés Mixed Integer Linear Program). La conclusió principal d’aquests experiments és que, amb un temps de procés molt inferior, es poden quasi igualar i en alguns casos millorar els resultats d’aquest model utilitzant els algorismes heurístics i metaheurístics proposats.

[EN] This paper provides practitioners with new approaches for solving realistic scheduling problems that consider additional resources, which can be implemented on expert and intelligent systems and help decision making in realistic settings. More specifically, we study the unrelated parallel machine scheduling problem with setup times and additional limited resources in the setups (UPMSR-S), with makespan minimization criterion. This is a more realistic extension of the traditional problem, in which the setups are assumed to be done without using additional resources (e.g. workers). We propose three metaheuristics following two approaches: a first approach that ignores the information about additional resources in the constructive phase, and a second approach that takes into account this information about the resources. Computational experiments are carried out over a benchmark of small and large instances. After the computational analysis we conclude that the second approach shows an excellent performance, overcoming the first approach.

[EN] This paper provides practitioners with new approaches for solving realistic scheduling problems that consider additional resources, which can be implemented on expert and intelligent systems and help decision making in realistic settings. More specifically, we study the unrelated parallel machine scheduling problem with setup times and additional limited resources in the setups (UPMSR-S), with makespan minimization criterion. This is a more realistic extension of the traditional problem, in which the setups are assumed to be done without using additional resources (e.g. workers). We propose three metaheuristics following two approaches: a first approach that ignores the information about additional resources in the constructive phase, and a second approach that takes into account this information about the resources. Computational experiments are carried out over a benchmark of small and large instances. After the computational analysis we conclude that the second approach shows an excellent performance, overcoming the first approach.

[EN] This paper introduces a row and column generation algorithm for finding the nucleolus, based on a linear programming model proposed in an earlier research. Since this approach cannot return an allocation for large games, we also propose a heuristic approach, which is based on sampling the coalitions space. Experiments over medium sized games show that the proposed heuristic finds allocations which are close to the true nucleolus, in a reasonable amount of time. Experiments over 100-player games show that the proposed heuristic can be applied to games of large size.

[EN] Parallel machine scheduling problems have many practical and industrial applications. In this paper we study a generalization which is the unrelated parallel machine scheduling problem with machine and job sequence setup times (UPMS) with makespan minimization criterion. We propose new mixed integer linear programs and a mathematical programming based algorithm. These new models and algorithms are tested and compared with the existing ones in an extensive and comprehensive computational campaign. The performance of two popular commercial solvers (CPLEX and Gurobi) is also compared in the experiments. Results show that the proposed methods significantly improve on existing methods and are able to obtain solutions for extremely large instances of up to 1000 jobs and eight machines with relative deviations from lower bounds below 0.8%.

[EN] This paper introduces a row and column generation algorithm for finding the nucleolus, based on a linear programming model proposed in an earlier research. Since this approach cannot return an allocation for large games, we also propose a heuristic approach, which is based on sampling the coalitions space. Experiments over medium sized games show that the proposed heuristic finds allocations which are close to the true nucleolus, in a reasonable amount of time. Experiments over 100-player games show that the proposed heuristic can be applied to games of large size.

El problema presentado es bien conocido en la literatura, y está clasificado como NP-duro. Por ello, se hacen necesarios algoritmos eficientes para su resolución. En este trabajo se proponen diferentes algoritmos matheurísticos, que combinan técnicas heurísticas con un modelo de programación lineal entera propuesto en una investigación anterior. Se realizarán experimentos computacionales para validar la calidad de la solución obtenida, así como la eficiencia de los algoritmos propuestos.

[EN] In this paper, we characterize minimax and Pareto-optimal security payoff vectors for general multicriteria zero-sum matrix games, using properties similar to the ones that have been used in the single criterion case. Our results show that these two solution concepts are rather similar, since they can be characterized with nearly the same sets of properties. Their main difference is the form of consistency that each solution concept satisfies. We also prove that both solution concepts can transform into each other, in their corresponding domains. (C) 2017 Elsevier Inc. All rights reserved.

[EN] In this paper, we characterize minimax and Pareto-optimal security payoff vectors for general multicriteria zero-sum matrix games, using properties similar to the ones that have been used in the single criterion case. Our results show that these two solution concepts are rather similar, since they can be characterized with nearly the same sets of properties. Their main difference is the form of consistency that each solution concept satisfies. We also prove that both solution concepts can transform into each other, in their corresponding domains. (C) 2017 Elsevier Inc. All rights reserved.

El problema presentado es bien conocido en la literatura, y está clasificado como NP-duro. Por ello, se hacen necesarios algoritmos eficientes para su resolución. En este trabajo se proponen diferentes algoritmos matheurísticos, que combinan técnicas heurísticas con un modelo de programación lineal entera propuesto en una investigación anterior. Se realizarán experimentos computacionales para validar la calidad de la solución obtenida, así como la eficiencia de los algoritmos propuestos.

El problema presentado es bien conocido en la literatura, y está clasificado como NP-duro. Por ello, se hacen necesarios algoritmos eficientes para su resolución. En este trabajo se proponen diferentes algoritmos matheurísticos, que combinan técnicas heurísticas con un modelo de programación lineal entera propuesto en una investigación anterior. Se realizarán experimentos computacionales para validar la calidad de la solución obtenida, así como la eficiencia de los algoritmos propuestos.

En este trabajo el alumno aborda un problema de secuenciación de máquinas paralelas no relacionadas con tiempos de ajuste entre trabajos. Los tiempos de ajuste dependen tanto de la máquina como de la secuencia de trabajos procesados. Además, dichos ajustes necesitan utilizar una cantidad de recursos adicionales, que también depende tanto de la máquina como de la secuencia. Este recurso es limitado y renovable. Este problema apenas ha sido tratado en la literatura científica, y se puede clasificar como NP-difícil. Dado la complejidad del problema, se propondrán técnicas metaheurísticas para su resolución en un tiempo de computación razonable. La calidad de la solución obtenida se comparará con aquélla que se obtenga mediante un modelo de programación lineal entera, para instancias de tamaño pequeño.

[EN] The problem studied in this paper takes as input data a set of lines forming a railway network, and an origin¿destination (OD) matrix. The OD pairs may use either the railway network or an alternative transportation mode. The objective is to determine the frequency/headway of each line as well as its number of carriages, so that the net profit of the railway network is maximized. We propose a mixed integer non-linear programming formulation for this problem. Because of the computational intractability of this model, we develop four algorithms: a mixed integer linear programming (MIP) model, a MIP-based iterative algorithm, a shortest-path based algorithm, and a local search. These four algorithms are tested and compared over a set of randomly generated instances. An application over a case study shows that only the local search heuristic is capable of dealing with large instances.

[EN] The problem studied in this paper takes as input data a set of lines forming a railway network, and an origin¿destination (OD) matrix. The OD pairs may use either the railway network or an alternative transportation mode. The objective is to determine the frequency/headway of each line as well as its number of carriages, so that the net profit of the railway network is maximized. We propose a mixed integer non-linear programming formulation for this problem. Because of the computational intractability of this model, we develop four algorithms: a mixed integer linear programming (MIP) model, a MIP-based iterative algorithm, a shortest-path based algorithm, and a local search. These four algorithms are tested and compared over a set of randomly generated instances. An application over a case study shows that only the local search heuristic is capable of dealing with large instances.

En este trabajo el alumno aborda un problema de secuenciación de máquinas paralelas no relacionadas con tiempos de ajuste entre trabajos. Los tiempos de ajuste dependen tanto de la máquina como de la secuencia de trabajos procesados. Además, dichos ajustes necesitan utilizar una cantidad de recursos adicionales, que también depende tanto de la máquina como de la secuencia. Este recurso es limitado y renovable. Este problema apenas ha sido tratado en la literatura científica, y se puede clasificar como NP-difícil. Dado la complejidad del problema, se propondrán técnicas metaheurísticas para su resolución en un tiempo de computación razonable. La calidad de la solución obtenida se comparará con aquélla que se obtenga mediante un modelo de programación lineal entera, para instancias de tamaño pequeño.

En este trabajo el alumno aborda un problema de secuenciación de máquinas paralelas no relacionadas con tiempos de ajuste entre trabajos. Los tiempos de ajuste dependen tanto de la máquina como de la secuencia de trabajos procesados. Además, dichos ajustes necesitan utilizar una cantidad de recursos adicionales, que también depende tanto de la máquina como de la secuencia. Este recurso es limitado y renovable. Este problema apenas ha sido tratado en la literatura científica, y se puede clasificar como NP-difícil. Dado la complejidad del problema, se propondrán técnicas metaheurísticas para su resolución en un tiempo de computación razonable. La calidad de la solución obtenida se comparará con aquélla que se obtenga mediante un modelo de programación lineal entera, para instancias de tamaño pequeño.

El diseño de redes de ferrocarril en competencia con modos de transporte alternativo (RND por sus siglas en inglés) se puede modelar como un problema de optimización combinatoria sobre un grafo dirigido. El objetivo del RND es diseñar una red de ferrocarril que atraiga al mayor número de pasajeros posible, suponiendo una restricción presupuestaria. Estudios previos han demostrado que este problema es NP-duro. Además de esa justificación teórica, trabajos publicados en la literatura científica han demostrado que los modelos matemáticos para el RND no son aplicables a instancias de este problema de tamaño real. Por todo ello, la investigación sobre algoritmos que ofrezcan una solución en un tiempo de cómputo razonable está justificada. En este trabajo se propondrán nuevos algoritmos metaheurísticos para una resolución eficiente del RND. Dichos algoritmos se compararán con otros propuestos con anterioridad en la literatura científica mediante la resolución de instancias del RND.

En este trabajo el alumno aborda un problema de secuenciación de máquinas paralelas no relacionadas con tiempos de ajuste entre trabajos. Los tiempos de ajuste dependen tanto de la máquina como de la secuencia de trabajos procesados. Además, dichos ajustes necesitan utilizar una cantidad de recursos adicionales, que también depende tanto de la máquina como de la secuencia. Este recurso es limitado y renovable. Este problema apenas ha sido tratado en la literatura científica, y se puede clasificar como NP-difícil. Dado la complejidad del problema, se propondrán técnicas metaheurísticas para su resolución en un tiempo de computación razonable. La calidad de la solución obtenida se comparará con aquélla que se obtenga mediante un modelo de programación lineal entera, para instancias de tamaño pequeño.

El diseño de redes de ferrocarril en competencia con modos de transporte alternativo (RND por sus siglas en inglés) se puede modelar como un problema de optimización combinatoria sobre un grafo dirigido. El objetivo del RND es diseñar una red de ferrocarril que atraiga al mayor número de pasajeros posible, suponiendo una restricción presupuestaria. Estudios previos han demostrado que este problema es NP-duro. Además de esa justificación teórica, trabajos publicados en la literatura científica han demostrado que los modelos matemáticos para el RND no son aplicables a instancias de este problema de tamaño real. Por todo ello, la investigación sobre algoritmos que ofrezcan una solución en un tiempo de cómputo razonable está justificada. En este trabajo se propondrán nuevos algoritmos metaheurísticos para una resolución eficiente del RND. Dichos algoritmos se compararán con otros propuestos con anterioridad en la literatura científica mediante la resolución de instancias del RND.

[EN] In this paper we analyze a parallel machine scheduling problem in which the processing of jobs on the machines requires a number of units of a scarce resource. This number depends both on the job and on the machine. The availability of resources is limited and fixed throughout the production horizon. The ob- jective considered is the minimization of the makespan. We model this problem by means of two integer linear programming problems. One of them is based on a model previously proposed in the literature. The other one, which is based on the resemblance to strip packing problems, is an original contribution of this paper. As the models presented are incapable of solving medium-sized instances to optimality, we propose three matheuristic strategies for each of these two models. The algorithms proposed are tested over an extensive computational experience. Results show that the matheuristic strategies significantly outperform the mathematical models.

[EN] In this paper we analyze a parallel machine scheduling problem in which the processing of jobs on the machines requires a number of units of a scarce resource. This number depends both on the job and on the machine. The availability of resources is limited and fixed throughout the production horizon. The ob- jective considered is the minimization of the makespan. We model this problem by means of two integer linear programming problems. One of them is based on a model previously proposed in the literature. The other one, which is based on the resemblance to strip packing problems, is an original contribution of this paper. As the models presented are incapable of solving medium-sized instances to optimality, we propose three matheuristic strategies for each of these two models. The algorithms proposed are tested over an extensive computational experience. Results show that the matheuristic strategies significantly outperform the mathematical models.

[EN] This work presents an unrelated parallel machine problem, solved by an ILP model with 5 contraint sets, which is compared to a model that uses lagrangian relaxation on one of its constraints, in this case, the resource constraints which indicates there is a limited resource which is needed for the jobs process., [ES] El trabajo presenta un problema de máquinas paralelas no relacionadas resuelto con un modelo ILP con cinco sets de restricciones, el cual es comprobado con un modelo que utiliza relajación lagrangiana en una de sus restricciones, en este caso,la restricción relajada corresponde a un recurso limitado que es necesario para el proceso de los trabajos.

[EN] This work presents an unrelated parallel machine problem, solved by an ILP model with 5 contraint sets, which is compared to a model that uses lagrangian relaxation on one of its constraints, in this case, the resource constraints which indicates there is a limited resource which is needed for the jobs process., [ES] El trabajo presenta un problema de máquinas paralelas no relacionadas resuelto con un modelo ILP con cinco sets de restricciones, el cual es comprobado con un modelo que utiliza relajación lagrangiana en una de sus restricciones, en este caso,la restricción relajada corresponde a un recurso limitado que es necesario para el proceso de los trabajos.

[EN] This work presents an unrelated parallel machine problem, solved by an ILP model with 5 contraint sets, which is compared to a model that uses lagrangian relaxation on one of its constraints, in this case, the resource constraints which indicates there is a limited resource which is needed for the jobs process., [ES] El trabajo presenta un problema de máquinas paralelas no relacionadas resuelto con un modelo ILP con cinco sets de restricciones, el cual es comprobado con un modelo que utiliza relajación lagrangiana en una de sus restricciones, en este caso,la restricción relajada corresponde a un recurso limitado que es necesario para el proceso de los trabajos.

Refereeing of this contribution was handled by T. Vladimirova, [EN] This paper deals with the swath acquisition planning problem for multisatellite Earth observation missions. Given a set of satellites and a mission time frame, the problem we solve consists of selecting a set of acquisitions from the satellites in order to cover a given region of interest during the requested time frame, optimizing a certain objective function. We show that the planning problem can be modeled as a set covering problem, using basic tools of mathematical programming. The formulation of the model requires the solution of a complex computational geometry problem, and therefore the use of heuristics and metaheuristics applies. In this paper, we discuss the efficiency of the constructive phase of a greedy randomized adaptive search procedure algorithm. Computational results comparing the heuristic algorithms with the exact approach are presented.