Search

[ES] El objetivo principal de este trabajo final de Grado será el diseño de dos algoritmo genético capaces de proporcionar una solución al problema de programación de la producción de un taller de flujo con recursos adicionales mediante el uso de Visual Studio 2012 como entorno de programación, dado que será necesario desarrollar un programa a medida. Como segundo objetivo, para comparar la eficiencia de los algoritmos diseñados, se comparará con el algoritmo que utilizan otros paquetes comerciales e incluso se resolverán problemas que el producto comercial no será capaz de resolver por su tamaño y complejidad.

[ES] Este trabajo estudia el problema de secuenciación en máquinas paralelas no relacionadas con tiempos de cambio dependientes de la máquina y de la secuencia de proceso de los trabajos. Se estudiarán diversas soluciones al problema propuestas a lo largo del tiempo que incluyen modelos de programación lineal entera mixta, modelos heurísticos, matheurísticos y de programación por restricciones. Tras esto, se propondrá un modelo exacto que se comparará con los métodos exactos existentes más relevantes de la literatura. Para esto, se hará uso de un cluster de cómputo en el que se estudiará el desempeño de los diferentes modelos mediante conjuntos de datos extraídos de trabajos anteriores de la literatura. Se ha decidido incluir el modelo de programación por restricciones en la comparación debido a su creciente interés. Para ello, se ha trabajado con el entorno de desarrollo integrado (IDE) de CPLEX y con la librería CP enfocada a la programación por restricciones. Los resultados obtenidos se han comparado con los resultados de las técnicas basadas en modelos de programación entera mixta y reafirman las bondades del enfoque basado en programación por restricciones., [EN] This work studies the unrelated parallel machines scheduling problem (UPMS) with setup times for every job, which are machine and sequence dependent. It will cover some of the solutions proposed over the time for the problem, which includes models based on mixed integer linear programming, heuristics, matheuristics and constraint programming. After this, a new exact model is proposed. It will be compared with some of the most relevant state of the art exact models. To this end, a computational cluster will be used to test the performance of the different models by means of data instances extracted from previous works from the literature. Due to its growing interest, a constraint programming model has been included in this work. To this end, I have worked with the CPLEX integrated development environment (IDE) and the CP library, which is focused on constraint programming. The results from the constraint programming model have been compared with the ones of mixed integer linear programming and reaffirm the goodnesses of the constraint programming approach.

[EN] Operation of ports and their constant improvement of management is of vital importance for each economy of the country that has maritime connections. Today, with the expansion of multinational companies that transport their merchandise by sea, ports must face greater volumes of merchandise and offer the best conditions for the efficient operation of their port operations. Container terminals that process merchandise, faced with demand from suppliers, are forced to improve their technologies and be able to provide the best efficiency and lowest costs for companies. One of the important tools for the proper functioning of the container terminal is the terminal operating system (TOS) that it uses, as it provides modern management solutions. The objective of this bachelor thesis is to analyze the level of implementation of terminal operating systems in the ports of Spain and to observe their technological progress., [ES] Los sistemas operativos de terminal (Terminal Operating System, TOS, en inglés) son sistemas que controlan el funcionamiento de las terminales portuarias. Son una parte clave de una cadena de suministro y tienen como objetivo principal controlar el movimiento y el almacenamiento de varios tipos de carga dentro y alrededor de una terminal o puerto de contenedores . Los sistemas también permiten un mejor uso de activos, mano de obra y equipo, planificar la carga de trabajo y recibir información actualizada. Los sistemas operativos de terminal a menudo utilizan otras tecnologías como internet, procesamiento EDI , computadoras móviles, LAN inalámbricas e identificación por radiofrecuencia (RFID) para monitorear eficientemente el flujo de productos dentro, fuera y alrededor del terminal. El objetivo de un sistema operativo de terminal es proporcionar un conjunto de procedimientos computarizados para administrar la carga, las máquinas y las personas dentro de la instalación para permitir un enlace continuo para administrar la instalación de manera eficiente y efectiva. En el proyecto se busca estudiar, para los principales puertos españoles, y a poder ser, del mediterráneo, el nivel de penetración de los TOS y los tipos de TOS (y fabricantes) instalados, haciendo un estudio sectorial, de competencia, capacidades, precios y funcionalidades.

[ES] El problema de la planificación de la producción es uno de los retos a los que se enfrentan diariamente las empresas. Para solucionar dicho problema existen diversas técnicas, como por ejemplo la Planificación de Requerimientos de Materiales (MRP). Esta técnica en muchos casos puede resultar ineficiente. Es por este motivo, que surgen otras técnicas como algoritmos heurísticos y modelos matemáticos, capaces de resolver el problema de la planificación de la producción con mayor eficiencia. El presente trabajo tiene como objetivo diseñar un modelo matemático para la planificación de la producción con capacidades y fechas de entrega. Este modelo aúna la misma funcionalidad que tiene el algoritmo heurístico de un MRP desarrollado por la empresa GeInfor y que está en estudio para su implantación en varias empresas finalistas. Para formular dicho modelo, se parte del modelo estándar de la planificación de la producción y sobre este se crearán sucesivos modelos añadiendo nuevas variables y restricciones. La incorporación de más y más variables y restricciones hace que sea necesario emplear distintas herramientas de modelización, debido al aumento de la dimensión del problema. La finalidad será la de estudiar el proceso de formulación del modelo matemático y analizar las diferencias existentes entre las soluciones óptimas obtenidas., [EN] The production planning problem is one of the challenges that companies face on a daily basis. In order to solve this problem, there are varioustechniques such as the Materials Requirements Planning (MRP). This technique can be inefficient in many cases. Therefore, other techniques such as heuristic algorithms and mathematical models have emerged. As they are able to solve production planning problems more efficiently. The aim of the current work is to design a mathematical model for production planning with capacities and delivery dates. This model combines the same functionality as the MRP heuristic algorithm developed by the company GeInfor and which is under study to implement in several final companies. To formulate this model, we will start from the standard production planning model. From this one, successive models will be created with the addition of new variables and constraints. The inclusion of more and more variables and constraints makes it necessary to use different modelling tools, due to the increase in size of the problem. The purpose will be to study the formulation process, as well as, to analyse the differences between the optimal solutions obtained.

[ES] El Block Relocation Problem es un problema de gran interés en la logística actual. Este problema consiste en minimizar el número de recolocaciones necesarias para extraer un conjunto de bloques apilados en un orden determinado donde solo se pueden reubicar los bloques de mayor altura. Una de las principales aplicaciones aparece en las terminales portuarias. Aquí, los bloques son los contenedores que están apilados en los bloques. Optimizar la extracción supone un gran ahorro en el tiempo de grúa de patio y por tanto en eficiencia para la terminal. En este TFM se estudiará el Block Relocation Problem desde varios puntos de vista. Primero se tratará de encontrar el mejor modelo para la resolución de manera exacta en la bibliografía actual y se intentará mejorar. Después, veremos las limitaciones que presentan estos modelos a la hora de resolver casos reales y se propondrá como alternativa una heurística. Aquí se procederá de manera similar. Comenzando por comparar las mejores heurísticas propuestas en la actualidad e intentar mejorarlas., [EN] The Block Relocation Problem is a problem of great interest in current logistics. This problem consists of minimizing the number of relocations required to extract a set of blocks stacked in a certain order where only the taller blocks can be relocated. One of the main applications appears in port terminals. Here, the blocks are the containers that are stacked in the blocks. Optimizing extraction means a great saving in yard crane time and therefore in efficiency for the terminal. In this TFM the Block Relocation Problem will be studied from various points of view. First we will try to find the best model for the exact resolution in the current bibliography and we will try to improve. Later, we will see the limitations that these models present when solving real cases and a heuristic will be proposed as an alternative. Here we will proceed in a similar way. Starting by comparing the best heuristics currently proposed and trying to improve them.

[EN] In cloud computing, service providers rent heterogeneous servers from cloud providers, i.e., Infrastructure as a Service (IaaS), to meet requests of consumers. The heterogeneity of servers and impatience of consumers pose great challenges to service providers for profit maximization. In this article, we transform this problem into a multi-queue model where the optimal expected response time of each queue is theoretically analyzed. A multi-queue request scheduling algorithm framework is proposed to maximize the total profit of service providers, which consists of three components: request stream splitting, requests allocation, and server assignment. A request stream splitting algorithm is designed to split the arriving requests to minimize the response time in the multi-queue system. An allocation algorithm, which adopts a one-step improvement strategy, is developed to further optimize the response time of the requests. Furthermore, an algorithm is developed to determine the appropriate number of required servers of each queue. After statistically calibrating parameters and algorithm components over a comprehensive set of random instances, the proposed algorithms are compared with the state-of-the-art over both simulated and real-world instances. The results indicate that the proposed multi-queue request scheduling algorithm outperforms the other algorithms with acceptable computational time.

We focus on a simplified container stowage planning problem where containers of different size and weight must be loaded and unloaded at multiple ports while maintaining the stability of the ship. We initially investigate how the difficulty in solving the problem changes with and without the consideration of container sizes and weight constraints. For this purpose, we provide integer programming formulations for the general problem as well as some special cases with identical container size and/or identical weights and evaluate their performance in randomly generated small- and medium-scale instances. We develop a matheuristic procedure, namely, an insert-and-fix heuristic, exploiting the special structure of the proposed formulations. The Insert-and-Fix method, in combination with a constructive algorithm that gives the solver an initial solution in each iteration, provides solutions with a low number of rehandles for instances with up to 5000 TEUs., Spanish Ministry of Science, Innovation, and Universities, FPU Grant A-2015-12849 and under the project “OPTEP-Port Terminal Operations Optimization” (No. RTI2018-094940-B-I00) financed with FEDER, Spain funds. The second author acknowledges the partial support by Data-driven logistics, Spain (FWO-S007318N) and Internal Funds KU Leuven, Spain.

[ES] La empresa Roquette Laisa España S.A. se enfrenta a un problema de estimación de la demanda de varias materias primas que utiliza tanto en la producción de producto final como en procesos internos de limpieza de maquinaria. Actualmente emplea sistemas manuales y basados en la experiencia para realizar las previsiones de consumo y con ello el aprovisionamiento contra proveedor. En este trabajo de Fin de Máster se propone analizar las oportunidades de mejora resultantes del uso de técnicas de series temporales y sencillos métodos de planificación de la producción. Para ello se cuenta con cargas de datos reales que permitirán estudiar el alcance de las mejoras propuestas., [EN] The company Roquette Laisa España S.A. faces the problem of estimating the demand for various raw materials that it uses both in the production of the final products and in the internal processes for cleaning the machinery. It currently uses manual and experience-based systems to make consumption forecasts and to issue orders to its providers. In this master thesis, it is proposed to analyze the opportunities resulting from the use of time series techniques and simple production planning methods. For this purpose, real data is available that will allow the gauge the improvement opportunities from the proposed techniques.

[EN] The mixed no-idle flowshop scheduling problem arises in modern industries including integrated circuits, ceramic frit and steel production, among others, and where some machines are not allowed to remain idle between jobs. This paper describes an exact algorithm that uses Benders decomposition with a simple yet effective enhancement mechanism that entails the generation of additional cuts by using a referenced local search to help speed up convergence. Using only a single additional optimality cut at each iteration, and combined with combinatorial cuts, the algorithm can optimally solve instances with up to 500 jobs and 15 machines that are otherwise not within the reach of off-the-shelf optimization software, and can easily surpass ad-hoc existing metaheuristics. To the best of the authors' knowledge, the algorithm described here is the only exact method for solving the mixed no-idle permutation flowshop scheduling problem.

© 2020 IEEE. Personal use of this material is permitted. Permissíon from IEEE must be obtained for all other uses, in any current or future media, including reprinting/republishing this material for advertisíng or promotional purposes, creating new collective works, for resale or redistribution to servers or lists, or reuse of any copyrighted component of this work in other works., [EN] We investigate a workflow scheduling problem with stochastic task arrival times and fuzzy task processing times and due dates. The problem is common in many real-time and workflow-based applications, where tasks with fixed stage number and linearly dependency are executed on scalable cloud resources with multiple price options. The challenges lie in proposing effective, stable, and robust algorithms under stochastic and fuzzy tasks. A triangle fuzzy number-based model is formulated. Two metrics are explored: the cost and the degree of satisfaction. An iterated heuristic framework is proposed to periodically schedule tasks, which consists of a task collection and a fuzzy task scheduling phases. Two task collection strategies are presented and two task prioritization strategies are employed. In order to achieve a high satisfaction degree, deadline constraints are defined at both job and task levels. By designing delicate experiments and applying sophisticated statistical techniques, experimental results show that the proposed algorithm is more effective and robust than the two existing methods.

[EN] Cloud computing is a new resource provisioning mechanism, which represents a convenient way for users to access different computing resources. Periodical workflow applications commonly exist in scientific and business analysis, among many other fields. One of the most challenging problems is to determine the right amount of resources for multiple periodical workflow applications. In this paper, the periodical workflow applications scheduling problem with total renting cost minimization is considered. The novelty of this work relies precisely on this objective function, which is more realistic in practice than the more commonly considered makespan minimization. An integer programming model is constructed for the problem under study. A Precedence Tree based Heuristic (PTH) is developed which considers three types of initial schedule construction methods. Based on the initial schedule, two improvement procedures are presented. The proposed methods are compared with existing algorithms for the related makespan based multiple workflow scheduling problem. Experimental and statistical results demonstrate the effectiveness and efficiency of the proposed algorithm.

© 2020 IEEE. Personal use of this material is permitted. Permissíon from IEEE must be obtained for all other uses, in any current or future media, including reprinting/republishing this material for advertisíng or promotional purposes, creating new collective works, for resale or redistribution to servers or lists, or reuse of any copyrighted component of this work in other works., [EN] In this article, we consider the problem of selecting appropriate heterogeneous servers in cloud centers for stochastically arriving requests in order to obtain an optimal tradeoff between the expected response time and power consumption. Heterogeneous servers with uncertain setup times are far more common than homogenous ones. The heterogeneity of servers and stochastic requests pose great challenges in relation to the tradeoff between the two conflicting objectives. Using the Markov decision process, the expected response time of requests is analyzed in terms of a given number of available candidate servers. For a given system availability, a binary search method is presented to determine the number of servers selected from the candidates. An iterative improvement method is proposed to determine the best servers to select for the considered objectives. After evaluating the performance of the system parameters on the performance of algorithms using the analysis of variance, the proposed algorithm and three of its variants are compared over a large number of random and real instances. The results indicate that proposed algorithm is much more effective than the other four algorithms within acceptable CPU times.

[EN] The pre-marshalling problem has been extensively studied in recent years with the aim of minimizing the number of movements needed to rearrange a bay of containers. Time is a more realistic objective for measuring process efficiency, and we show that it does not correlate with the number of movements. As a result, we study the problem of minimizing crane times and develop two exact approaches to solve it: an integer linear model, and a branch and bound algorithm, with new upper and lower bounds, dominance criteria, and a heuristic procedure, to provide optimal solutions for problems of practical size

[EN] In semiconductor wafer fabrication (wafer fab), wafers go through hundreds of process steps on a variety of processing machines for electrical circuit building operations. One of the special features in the wafer fabs is that there exist batch processors (BPs) where several wafer lots are processed at the same time as a batch. The batch processors have a significant influence on system performance because the repetitive batching and de-batching activities in a reentrant product flow system lead to non-smooth product flows with high variability. Existing research on the BP control problems has mostly focused on the local performance, such as waiting time at the BP stations. This paper attempts to examine how much BP control policies affect the system-wide behavior of the wafer fabs. A simulation model is constructed with which experiments are performed to analyze the performance of BP control rules under various production environments. Some meaningful insights on BP control decisions are identified through simulation results.

[EN] Disasters are usually managed through a four-phase cycle including mitigation, preparedness, response and recovery. The first two phases happen before a disaster and the last two after it. This survey focuses on casualty management (CM), which is one of the actions taken in the response phase of a disaster. Right after a severe disaster strikes, we may be confronted with a large number of casualties in a very short period of time. These casualties are in need of urgent treatment and their survival depends on a rapid response. Therefore, managing resources in the first few hours after a disaster is critical and efficient CM can significantly increase the survival rate of casualties. Uncertainty in the location of a disaster, disruption to transportation networks, scarcity of resources and possible deaths of rescue and medical teams due to the disaster in such situations make it hard to manage casualties. In this survey, we focus on CM for disasters where the following five steps are taken, respectively: (i) Resource dispatching/search and rescue, (ii) on-site triage, (iii) on-site medical assistance, (iv) transportation to hospitals and (v) triage and comprehensive treatment. With a special focus on Operations Research (OR) techniques, we categorize the existing research papers and case studies in each of these steps. Then, by critically observing and investigating gaps, trends and the practicality of the extant research studies, we suggest future directions for academics and practitioners.

[EN] Industrial production scheduling problems are challenges that researchers have been trying to solve for decades. Many practical scheduling problems such as the hybrid flowshop are ATP-hard. As a result, researchers resort to metaheuristics to obtain effective and efficient solutions. The traditional design process of metaheuristics is mainly manual, often metaphor-based, biased by previous experience and prone to producing overly tailored methods that only work well on the tested problems and objectives. In this paper, we use an Automatic Algorithm Design (AAD) methodology to eliminate these limitations. AAD is capable of composing algorithms from components with minimal human intervention. We test the proposed MD for three different optimization objectives in the hybrid flowshop. Comprehensive computational and statistical testing demonstrates that automatically designed algorithms outperform specifically tailored state-of-the-art methods for the tested objectives in most cases.

[EN] Total profit is one of the most important factors to be considered from the perspective of resource providers. In this paper, an original MapReduce workflow scheduling with deadline and data locality is proposed to maximize total profit of resource providers. A new workflow conversion based on dynamic programming and ChainMap/ChainReduce is designed to decrease transmission times among MapReduce jobs of workflows. A new deadline division considering execution time, float time and job level is proposed to obtain better deadlines of MapReduce jobs in workflows. With the adapted replica strategy in MapReduce workflow, a new task scheduling is proposed to improve data locality which assigns tasks to servers with the earliest completion time in order to ensure resource providers obtain more profit. Experimental results show that the proposed heuristic results in larger total profit than other adopted algorithms.

[EN] Workers still perform the bulk of operations in the manufacturing industry. The consideration of the assignment of workers and the reduction of ergonomic risks in U-shaped assembly lines is of paramount importance. However, the objectives of efficient task and worker assignment and a reduction in ergonomic risks are not usually correlated. Moreover, there is limited research in the existing literature into multi-objective approaches in U-shaped assembly lines. We formulate a U-shaped assembly worker assignment and balancing problem to simultaneously minimize cycle times and ergonomic risks. In addition, and due to its simplicity and successful results in flow shop scheduling problems, a Restarted Iterated Pareto Greedy algorithm is designed to optimize both objectives. In this algorithm, a problem-specific heuristic-based initialization is extended to improve the initial solution. Two precedence-based greedy and local search phases are developed to exploit the space around the current solution. Finally, a restart mechanism is proposed to help the algorithm escape from local optima. Comprehensive computational results, supported by detailed statistical analyses, suggest that the proposed multi-objective algorithm outperforms existing methods on a large number of benchmark instances.

[EN] Breast cancer is currently the leading cause of death due to cancer in women, after lung cancer. For its diagnosis and staging, detection of metastatic tissue in axillary lymph nodes is occasionally used, since lymphatic spread is the main prognostic factor, especially in early stages. However, the pathologist¿s work in this diagnosis is considerably complex and tedious, so the need to automate this process arises. In the present work, a comparison of several models based on traditional machine learning techniques for the extraction of features and subsequent classification of sections of axillary lymph nodes stained in H&E is developed, to identify whether they contain tissue with metastasis or not. Furthermore, the results are compared with those obtained with other cutting-edge machine learning techniques, specifically with the Convolutional Neural Networks. In this way, alternatives with good enough results are proposed to be applied to the clinical reality of hospitals, with a computational cost and lower needs than the most sophisticated techniques., [ES] El cáncer de mama se impone en la actualidad como la principal causa de muerte por cáncer en mujeres, después del cáncer de pulmón. Para su diagnóstico y estadificación, en ocasiones se recurre a la detección de tejido metastásico en ganglios linfáticos axilares, ya que la diseminación linfática es el principal factor pronóstico, sobre todo en estadíos iniciales. Sin embargo, la labor del patólogo en este diagnóstico es considerablemente compleja y tediosa, por lo que nace la necesidad de automatizar este proceso. En el presente trabajo se desarrolla una comparativa de varios modelos basados en técnicas tradicionales de aprendizaje automático para la extracción de características y posterior clasificación de secciones de ganglios linfáticos axilares tintados en H&E, para identificar si contienen tejido con metástasis o no. Además, los resultados son comparados con los obtenidos con otras técnicas de vanguardia de aprendizaje automático, concretamente con las Redes Neuronales Convolucionales. De este modo, se proponen alternativas con resultados suficientemente buenos para ser aplicados a la realidad clínica de los hospitales, con un coste computacional y unas necesidades inferiores a las técnicas más sofisticadas., [CA] El càncer de mama s’imposa en l’actualitat com la principal causa de mort per càncer en dones, després del càncer de pulmó. Per al seu diagnòstic i estadificació, a vegades es recorre a la detecció de teixit metastàtic en ganglis limfàtics axil·lars, ja que la disseminació limfàtica és el principal factor pronòstic, sobretot en estadis inicials. No obstant això, la labor del patòleg en aquest diagnòstic és considerablement complexa i tediosa, pel que naix la necessitat d’automatitzar aquest procés. En el present treball es desenvolupa una comparativa de diversos models basats en tècniques tradicionals d’aprenentatge automàtic per a l’extracció de característiques i posterior classificació de seccions de ganglis limfàtics axil·lars tintats en H&E, per a identificar si contenen teixit amb metàstasi o no. A més, els resultats són comparats amb els obtinguts amb altres tècniques d’avantguarda d’aprenentatge automàtic, concretament amb les Xarxes Neuronals Convolucionals. D’aquesta manera, es proposen alternatives amb resultats prou bons per a ser aplicats a la realitat clínica dels hospitals, amb un cost computacional i unes necessitats inferiors a les tècniques més sofisticades.

[EN] To meet the dynamic workload requirements in widespread task-batch based workflow applications, it is important to design algorithms for DAG-based platforms (such as Dryad, Spark and Pegasus) to rent virtual machines from public clouds dynamically. In terms of depths and functionalities, tasks of different task-batches are merged into task-units. A unit-aware deadline division method is investigated for properly dividing workflow deadlines to task deadlines so as to minimize the utilization of rented intervals. A rule-based task scheduling method is presented for allocating tasks to time slots of rented Virtual Machines (VMs) with a task right shifting operation and a weighted priority composite rule. A Unit-aware Rule-based Heuristic (URH) is proposed for elastically provisioning VMs to task-batch based workflows to minimize the rental cost in DAG-based cloud platforms. Effectiveness of the proposed URH methods is verified by comparing them against two adapted existing algorithms for similar problems on some realistic workflows.

[EN] Relevant gene selection is crucial for analyzing cancer gene expression datasets including two types of tumors in cancer classification. Intrinsic interactions among selected genes cannot be fully identified by most existing gene selection methods. In this paper, we propose a weighted general group lasso (WGGL) model to select cancer genes in groups. A gene grouping heuristic method is presented based on weighted gene co-expression network analysis. To determine the importance of genes and groups, a method for calculating gene and group weights is presented in terms of joint mutual information. To implement the complex calculation process of WGGL, a gene selection algorithm is developed. Experimental results on both random and three cancer gene expression datasets demonstrate that the proposed model achieves better classification performance than two existing state-of-the-art gene selection methods.

[EN] The performance of shipping companies greatly depends on reduced berthing times. The trend towards bigger ships and shorter berthing times places severe stress on container terminals, which cannot simply increase the available cranes indefinitely. Therefore, the focus is on optimizing existing resources. An effective way of speeding up the loading/unloading operations of ships at the container terminal is to use the idle time before the arrival of a ship for sorting the stored containers in advance. The pre-marshalling problem consists in rearranging the containers placed in a bay in the order in which they will be required later, looking for a sequence with the minimum number of moves. With sorted bays, loading/unloading operations are significantly faster, as there is no longer a need to make unproductive moves in the bays once ships are berthed. In this paper, we address the pre-marshalling problem by developing and testing integer linear programming models. Two alternative families of models are proposed, as well as an iterative solution procedure that does not depend on a difficult to obtain upper bound. An extensive computational analysis has been carried out over several well-known datasets from the literature. This analysis has allowed us to test the performance of the models, and to conclude that the performance of the best proposed model is superior to that of previously published alternatives.

[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] The container pre-marshalling problem involves the sorting of containers in stacks so that there are no blocking containers and retrieval is carried out without additional movements. This sorting process should be carried out in as few container moves as possible. Despite recent advancements in solving real world sized problems to optimality, several classes of pre-marshalling problems remain difficult for exact approaches. We propose a branch and bound algorithm with new components for solving such difficult instances. We strengthen existing lower bounds and introduce two new lower bounds that use a relaxation of the pre-marshalling problem to provide tight bounds in specific situations. We introduce generalized dominance rules that help reduce the search space, and a memoization heuristic that finds feasible solutions quickly. We evaluate our approach on standard benchmarks of pre-marshalling instances, as well as on a new dataset to avoid overfitting to the available data. Overall, our approach optimally solves many more instances than previous work, and finds feasible solutions on nearly every problem it encounters in limited CPU times.

[EN] Large manufacturing firms operate more than one production center. As a result, in relation to scheduling problems, which factory manufactures which product is an important consideration. In this paper we study an extension of the well known permutation flowshop scheduling problem in which there is a set of identical factories, each one with a flowshop structure. The objective is to minimize the maximum completion time or makespan among all factories. The resulting problem is known as the distributed permutation flowshop and has attracted considerable interest over the last few years. Contrary to the recent trend in the scheduling literature, where complex nature-inspired or metaphor-based methods are often proposed, we present simple Iterated Greedy algorithms that have performed well in related problems. Improved initialization, construction and destruction procedures, along with a local search with a strong intensification are proposed. The result is a very effective algorithm with little problem-specific knowledge that is shown to provide demonstrably better solutions in a comprehensive and thorough computational and statistical campaign.

[EN] Facility location models are well established in various application areas with more than a century of history in academia. Since the 1970s the trend has been shifting from manufacturing to service industries. Due to their nature, service industries are frequently located in or near urban areas that results in additional assumptions, objectives and constraints other than those in more traditional manufacturing location models. This survey focuses on the location of service facilities in urban areas. We studied 110 research papers across different journals and disciplines. We have analyzed these papers on two levels. On the first, we take an Operations Research perspective to investigate the papers in terms of types of decisions, location space, main assumptions, input parameters, objective functions and constraints. On the second level, we compare and contrast the papers in each of these applications categories: (a) Waste management systems (WMS), (b) Large-scale disaster (LSD), (c) Small-scale emergency (SSE), (d) General service and infrastructure (GSI), (e) Non-emergency healthcare systems (NEH) and (f) Transportation systems and their infrastructure (TSI). Each of these categories is critically analyzed in terms of application, assumptions, decision variables, input parameters, constraints, objective functions and solution techniques. Gaps, research opportunities and trends are identified within each category. Finally, some general lessons learned based on the practicality of the models is synthesized to suggest avenues of future research.

[EN] The mixed no-wait flowshop problem with both wait and no-wait constraints has many potential real-life applications. The problem can be regarded as a generalization of the traditional permutation flowshop and the no-wait flowshop. In this paper, we study, for the first time, this scheduling setting with makespan minimization. We first propose a mathematical model and then we design a speed-up makespan calculation procedure. By introducing a varying number of destructed jobs, a modified iterated greedy algorithm is proposed for the considered problem which consists of four components: 1) initialization solution construction; 2) destruction; 3) reconstruction; and 4) local search. To further improve the intensification and efficiency of the proposal, insertion is performed on some neighbor jobs of the best position in a sequence during the initialization, solution construction, and reconstruction phases. After calibrating parameters and components, the proposal is compared with five existing algorithms for similar problems on adapted Taillard benchmark instances. Experimental results show that the proposal always obtains the best performance among the compared methods.

[EN] Workers with different levels of experience and knowledge have different effects on job processing times. By taking into account 1) the sum-of-processing-time; 2) the job-position; and 3) the experience of workers, a more general learning model is introduced for scheduling problems. We show that this model generalizes existing ones and brings the consideration of learning and forgetting effects closer to reality. We demonstrate that some single machine scheduling problems are polynomially solvable under this general model. Considering the forgetting effect caused by the idle time on the second machine, we construct a learning-forgetting model for the two-machine permutation flow shop scheduling problem with makespan minimization. A branch-and-bound method and four heuristics are presented to find optimal and approximate solutions, respectively. The proposed heuristics are evaluated over a large number of randomly generated instances. Experimental results show that the proposed heuristics are effective and efficient.

[EN] Allocating service capacities in cloud computing is based on the assumption that they are unlimited and can be used at any time. However, available service capacities change with workload and cannot satisfy users' requests at any time from the cloud provider's perspective because cloud services can be shared by multiple tasks. Cloud service providers provide available time slots for new user's requests based on available capacities. In this paper, we consider workflow scheduling with deadline and time slot availability in cloud computing. An iterated heuristic framework is presented for the problem under study which mainly consists of initial solution construction, improvement, and perturbation. Three initial solution construction strategies, two greedy-and fair-based improvement strategies and a perturbation strategy are proposed. Different strategies in the three phases result in several heuristics. Experimental results show that different initial solution and improvement strategies have different effects on solution qualities.

[EN] Big data applications usually need to rent a large number of virtual machines from Cloud computing providers. As a result of the policies employed by Cloud providers, the prices of spot virtual machine instances behavior stochastically. Spot prices (prices of spot instances) fluctuate greatly or have multiple regimes. Choosing virtual machines according to trends in prices is helpful in decreasing the resource rental cost. Existing price prediction methods are unable to accurately predict prices in these environments. As a result, a dynamic-ARIMA and two markov regime-switching autoregressive model based forecasting methods have been developed in this paper. Experimental results show that the proposals are better than the existing MonthAR in most scenarios. (C) 2017 Elsevier B.V. All rights reserved.

[EN] We consider a special workflow scheduling problem in a hybrid-cloud-based workflow management system in which tasks are linearly dependent, compute-intensive, stochastic, deadline-constrained and executed on elastic and distributed cloud resources. This kind of problems closely resemble many real-time and workflow-based applications. Three optimization objectives are explored: number, usage time and utilization of rented VMs. An iterated heuristic framework is presented to schedule jobs event by event which mainly consists of job collecting and event scheduling. Two job collecting strategies are proposed and two timetabling methods are developed. The proposed methods are calibrated through detailed designs of experiments and sound statistical techniques. With the calibrated components and parameters, the proposed algorithm is compared to existing methods for related problems. Experimental results show that the proposal is robust and effective for the problems under study.

[EN] Complex workflow applications are widely used in scientific computing and economic analysis, which commonly include both preemptive and non-preemptive tasks. Cloud computing provides a convenient way for users to access different resources based on the ¿pay-as-you-go¿ model. However, different resource renting alternatives (reserved, on-demand or spot) are usually provided by the service provider. The spot instances provide a dynamic and cheaper alternative comparing to the on-demand one. However, failures often occur due to the fluctuations of the price of the instance. It is a big challenge to determine the appropriate amount of spot and on-demand resources for workflow applications with both preemptive and non-preemptive tasks. In this paper, the workflow scheduling problem with both spot and on-demand instances is considered. The objective is to minimize the total renting cost under deadline constrains. An idle time block-based method is proposed for the considered problem. Different idle time block-based searing and improving strategies are developed to construct schedules for workflow applications. Schedules are improved by a forward and backward moving mechanism. Experimental and statistical results demonstrate the effectiveness of the proposed algorithm over a lot of tests with different sizes.

[EN] This paper addresses a sequence dependent setup times no-wait flowshop with learning and forgetting effects to minimize total flowtime. This problem is NP-hard and has never been considered before. A position-based learning and forgetting effects model is constructed. Processing times of operations change with the positions of corresponding jobs in a schedule. Objective increment properties are deduced and based on them three accelerated neighbourhood construction heuristics are presented. Because of the simplicity and excellent performance shown in flowshop scheduling problems, an iterated greedy heuristic is proposed. The proposed iterated greedy algorithm is compared with some existing algorithms for related problems on benchmark instances. Comprehensive computational and statistical tests show that the presented method obtains the best performance among the compared methods. (C) 2018 Elsevier Inc. All rights reserved.

[EN] The shortest path problems (SPPs) with learning effects (SPLEs) have many potential and interesting applications. However, at the same time they are very complex and have not been studied much in the literature. In this paper, we show that learning effects make SPLEs completely different from SPPs. An adapted A* (AA*) is proposed for the SPLE problem under study. Though global optimality implies local optimality in SPPs, it is not the case for SPLEs. As all subpaths of potential shortest solution paths need to be stored during the search process, a search graph is adopted by AA* rather than a search tree used by A*. Admissibility of AA* is proven. Monotonicity and consistency of the heuristic functions of AA* are redefined and the corresponding properties are analyzed. Consistency/monotonicity relationships between the heuristic functions of AA* and those of A* are explored. Their impacts on efficiency of searching procedures are theoretically analyzed and experimentally evaluated.

[EN] The resource constrained project scheduling problem (RCPSP) is widely studied in the literature and has a host of applications in practice. As a variant of the RCPSP, the resource availability cost problem (RACP), which has the aim of minimizing the availability costs of renewable resources in order to complete a project subject to a given deadline, is considered in this paper. We divide the RACP into two sub-problems: the sequencing problem and the resource decision problem, and propose a multi-start iterative search heuristic (MSIS) to solve it. For the sequencing problem, an iterative search framework is constructed to effectively search the activity sequences. A two stage resource adjustment procedure and a backward peak elimination procedure is developed for solving the resource decision problem. MSIS is compared with three existing algorithms on both PSPLib and RanGen data sets involving 1380 instances. A complete calibration of the different parameters and operators of MSIS by means of a design of experiments approach is given. Experimental and statistical results show that MSIS outperforms the other three algorithms in both effectiveness and efficiency by a significant margin. (C) 2016 Published by Elsevier B.V.