Pasar al contenido principal

SMPA: SECUENCIACION MULTIOBJETIVO PARALELA AVANZADA: AVANCES TEORICOS Y PRACTICOS

DPI2008-03511

•
Nombre agencia financiadora Ministerio de Ciencia e Innovación
Acrónimo agencia financiadora MICINN
Programa Programa Nacional de Proyectos de Investigación Fundamental
Subprograma Subprograma de Proyectos de Investigación Fundamental no Orientada
Convocatoria Proyectos I+D
Año convocatoria 2008
Plan Estatal 2008-2011 Plan Nacional de Investigación Científica, Desarrollo e Innovación Tecnológica
Unidad de gestión Subdirección General de Proyectos de Investigación
Centro beneficiario UNIVERSITAT POLITÈCNICA DE VALÈNCIA
Identificador persistente http://dx.doi.org/10.13039/501100004837

Resultados relacionados

Resultados totales (Incluyendo duplicados): 11
Encontrada(s) 1 página(s)

RiuNet. Repositorio Institucional de la Universitat Politécnica de Valéncia
Publicación Artículo científico (JournalArticle)

Multi-objective sequence dependent setup times permutation flowshop: A new algorithm and a comprehensive study

  • Ciavotta, Michele
  • Minella, Gerardo Gabriel
  • Ruiz García, Rubén
The permutation flowshop scheduling problem has been thoroughly studied in recent decades, both from single objective as well as from multi-objective perspectives. To the best of our knowledge, little has been done regarding the multi-objective flowshop with Pareto approach when sequence dependent setup times are considered. As setup times and multi-criteria problems are important in industry, we must focus on this area. We propose a simple, yet powerful algorithm for the sequence dependent setup times flowshop problem with several criteria. The presented method is referred to as Restarted Iterated Pareto Greedy or RIPG and is compared against the best performing approaches from the relevant literature. Comprehensive computational and statistical analyses are carried out in order to demonstrate that the proposed RIPG method clearly outperforms all other algorithms and, as a consequence, it is a state-of- art method for this important and practical scheduling problem, The authors thank the anonymous referees for their careful and detailed comments which have helped improve this manuscript considerably. This work is partially financed by the Spanish Ministry of Science and Innovation, under the projects "SMPA-Advanced Parallel Multiobjective Sequencing: Practical and Theorerical Advances" with reference DPI2008-03511/DPI and "RESULT-Realistic Extended Scheduling Using Light Techniques" with reference DPI2012-36243-C02-01 and by the Small and Medium Industry of the Generalitat Valenciana (IMPIVA) and by the European Union through the European Regional Development Fund (FEDER) inside the R+D program "Ayudas dirigidas a Institutos Tecnologicos de la Red IMPIVA" during the year 2011, with project numbers IMDEEA/2011/142 and IMDEEA/2012/143.
RiuNet. Repositorio Institucional de la Universitat Politécnica de Valéncia
Publicación Artículo científico (JournalArticle)

A comprehensive review and evaluation of permutation flowshop heuristics to minimize flowtime

  • Pan, Quan-Ke
  • Ruiz García, Rubén
[EN] In recent years, a large number of heuristics have been proposed for the minimization of the total or mean flowtime/completion time of the well-known permutation flowshop scheduling problem. Although some literature reviews and comparisons have been made, they do not include the latest available heuristics and results are hard to compare as no common benchmarks and computing platforms have been employed. Furthermore, existing partial comparisons lack the application of powerful statistical tools. The result is that it is not clear which heuristics, especially among the recent ones, are the best. This paper presents a comprehensive review and computational evaluation as well as a statistical assessment of 22 existing heuristics. From the knowledge obtained after such a detailed comparison, five new heuristics are presented. Careful designs of experiments and analyses of variance (ANOVA) techniques are applied to guarantee sound conclusions. The comparison results identify the best existing methods and show that the five newly presented heuristics are competitive or better than the best performing ones in the literature for the permutation flowshop problem with the total completion time criterion, This research is partially supported by National Science Foundation of China (60874075, 61174187), and Science Foundation of Shandong Province, China (BS2010DX005), and Postdoctoral Science Foundation of China (20100480897). Ruben Ruiz is partially funded by the Spanish Ministry of Science and Innovation, under the project "SMPA-Advanced Parallel Multiobjective Sequencing: Practical and Theorerical Advances" with reference DPI2008-03511/DPI and by the Small and Medium Industry of the Generalitat Valenciana (IMPIVA) and by the European Union through the European Regional Development Fund (FEDER) inside the R+D program "Ayudas dirigidas a Institutos Tecnologicos de la Red IMPIVA" during the year 2011, with project number IMDEEA/2011/142.
RiuNet. Repositorio Institucional de la Universitat Politécnica de Valéncia
Publicación Artículo científico (JournalArticle)

A genetic algorithm for the unrelated parallel machine scheduling problemwith sequence dependent setup times

  • Vallada Regalado, Eva|||0000-0003-3918-1788
  • Ruiz García, Rubén
In this work a genetic algorithm is presented for the unrelated parallel machine scheduling problem in which machine and job sequence dependent setup times are considered. The proposed genetic algorithm includes a fast local search and a local search enhanced crossover operator. Two versions of the algorithm are obtained after extensive calibrations using the Design of Experiments (DOE) approach. We review, evaluate and compare the proposed algorithm against the best methods known from the literature. We also develop a benchmark of small and large instances to carry out the computational experiments. After an exhaustive computational and statistical analysis we can conclude that the proposed method shows an excellent performance overcoming the rest of the evaluated methods in a comprehensive benchmark set of instances., The authors are indebted to the referees and editor for the many constructive comments that have significantly improved the paper. This work is partially funded by the Spanish Ministry of Science and Innovation, under the project "SMPA - Advanced Parallel Multiobjective Sequencing: Practical and Theoretical Advances" with reference DPI2008-03511/DPI. The authors should also thank the IMPIVA - Institute for the Small and Medium Valencian Enterprise, for the project OSC with references IMIDIC/2008/137, IMIDIC/2009/198 and IMIDIC/2010/175 and the Polytechnic University of Valencia, for the project PPAR with reference 3147. Eva Vallada is also partly funded by the Government of Comunitat Valenciana under a grant (BEST 2009). The authors are also indebted with Dario Diotallevi for his help in coding some of the re-implemented methods from the literature used in the tests.
RiuNet. Repositorio Institucional de la Universitat Politécnica de Valéncia
Publicación Artículo científico (JournalArticle)

Local search methods for the flowshop scheduling problem with flowtime minimization

  • Quan-Ke Pan
  • Ruiz García, Rubén
Flowshop scheduling is a very active research area. This problem still attracts a considerable amount of interest despite the sheer amount of available results. Total flowtime minimization of a flowshop has been actively studied and many effective algorithms have been proposed in the last few years. New best solutions have been found for common benchmarks at a rapid pace. However, these improvements many times come at the cost of sophisticated algorithms. Complex methods hinder potential applications and are difficult to extend to small problem variations. Replicability of results is also a challenge. In this paper, we examine simple and easy to implement methods that at the same time result in state-of-the-art performance. The first two proposed methods are based on the well known Iterated Local Search (ILS) and Iterated Greedy (IG) frameworks, which have been applied with great success to other flowshop problems. Additionally, we present extensions of these methods that work over populations, something that we refer to as population-based ILS (pILS) and population-based IG (pIGA), respectively. We calibrate the presented algorithms by means of the Design of Experiments (DOE) approach. Extensive comparative evaluations are carried out against the most recent techniques for the considered problem in the literature. The results of a comprehensive computational and statistical analysis show that the presented algorithms are very effective. Furthermore, we show that, despite their simplicity, the presented methods are able to improve 12 out of 120 best known solutions of Taillard¿s flowshop benchmark with total flowtime criterion., This research is partially supported by National Science Foundation of China under Grants 61174187, 60874075, and Basic scientific research foundation of Northeast University under Grant N110208001, and Science Foundation of Shandong Province, China (BS2010DX005). Ruben Ruiz is partially funded by the Spanish Ministry of Science and Innovation, under the project "SMPA - Advanced Parallel Multiobjective Sequencing: Practical and Theoretical Advances" with reference DPI2008-03511/DPI, by the Small and Medium Industry of the Generalitat Valenciana (IMPIVA) and by the European Union through the European Regional Development Fund (FEDER) inside the R + D program "Programa de I + D para Institutos Tecnologicos de la Red IMPIVA" during the year 2010, with Project Number IMDEEA/2011/142.
RiuNet. Repositorio Institucional de la Universitat Politécnica de Valéncia
Publicación Artículo científico (JournalArticle)

An estimation of distribution algorithm for lot-streaming flow shop problems with setup times

  • Pan, Quan-Ke
  • Ruiz García, Rubén
Lot-streaming flow shops have important applications in different industries including textile, plastic, chemical, semiconductor and many others. This paper considers an n-job m-machine lot-streaming flow shop scheduling problem with sequence-dependent setup times under both the idling and noidling production cases. The objective is to minimize the maximum completion time or makespan. To solve this important practical problem, a novel estimation of distribution algorithm (EDA) is proposed with a job permutation based representation. In the proposed EDA, an efficient initialization scheme based on the NEH heuristic is presented to construct an initial population with a certain level of quality and diversity. An estimation of a probabilistic model is constructed to direct the algorithm search towards good solutions by taking into account both job permutation and similar blocks of jobs. A simple but effective local search is added to enhance the intensification capability. A diversity controlling mechanism is applied to maintain the diversity of the population. In addition, a speed-up method is presented to reduce the computational effort needed for the local search technique and the NEH-based heuristics. A comparative evaluation is carried out with the best performing algorithms from the literature. The results show that the proposed EDA is very effective in comparison after comprehensive computational and statistical analyses., This research is partially supported by the National Science Foundation of China (60874075, 70871065), and Science Foundation of Shandong Province in China under Grant BS2010DX005, and Postdoctoral Science Foundation of China under Grant 20100480897. Ruben Ruiz is partially funded by the Spanish Ministry of Science and Innovation, under the project "SMPA-Advanced Parallel Multiobjective Sequencing: Practical and Theoretical Advances" with reference DPI2008-03511/DPI and by the IMPIVA-Institute for the Small and Medium Valencian Enterprise, for the project OSC with references IMIDIC/2008/137, IMIDIC/2009/198 and IMIDIC/2010/175.
RiuNet. Repositorio Institucional de la Universitat Politécnica de Valéncia
Publicación Artículo científico (JournalArticle)

A study on the effect of the asymmetry on real capacitated vehicle routing problems

  • Rodríguez Villalobos, Alejandro|||0000-0003-1079-6121
  • Ruiz García, Rubén
Matrices with distances between pairs of locations are essential for solving vehicle routing problems like the Capacitated Vehicle Routing Problem (CVRP), Traveling Salesman Problem (TSP) and others. This work deals with the complex reality of transportation networks and asymmetry. Through a series of comprehensive and thorough computational and statistical experiments we study the effect that many factors like asymmetry, geographical location of the depot and clients, demand, territory and maximum vehicle capacity have in the solution of CVRP instances. We examine both classical heuristics as well as current state-of-the-art metaheuristics and show that these methods are seriously affected by the studied factors from a solution time and quality of solutions perspective. We systematically compare the solutions obtained in the symmetric scenario with those obtained in the real asymmetric case at a quantitative as well as a qualitative level, with the objective of carefully measuring and understanding the differences between both cases. © 2011 Elsevier Ltd., The authors are indebted to Keld Helsgaun, Stefan Ropke and especially to Yuichi Nagata for their kind help, collaboration and for facilitating the binaries of their algorithms. This work is partially funded by the Spanish Ministry of Science and Innovation, under the project "SMPA-Advanced Parallel Multiobjective Sequencing: Practical and Theoretical Advances" with reference DPI2008-03511/DPI. The authors should also thank the IMPIVA-Institute for the Small and Medium Valencian Enterprise, for the project TASER with reference IMDEEA/2011/142.
RiuNet. Repositorio Institucional de la Universitat Politécnica de Valéncia
Publicación Artículo científico (JournalArticle)

Scheduling unrelated parallel machines with resource-assignable sequence-dependent setup times

  • Ruiz García, Rubén
  • Andrés Romano, Carlos|||0000-0003-4453-4891
[EN] A novel scheduling problem that results from the addition of resource-assignable setups is presented in this paper. We consider an unrelated parallel machine problem with machine and job sequence-dependent setup times. The new characteristic is that the amount of setup time does not only depend on the machine and job sequence but also on the amount of resources assigned, which can vary between a minimum and a maximum. The aim is to give solution to real problems arising in several industries where frequent setup operations in production lines have to be carried out. These operations are indeed setups whose length can be reduced or extended according to the amount of resources assigned to them. The objective function considered is a linear combination of total completion time and the total amount of resources assigned. We present a mixed integer program (MIP) model and some fast dispatching heuristics. We carry out careful and comprehensive statistical analyses to study what characteristics of the problem affect the MIP model performance. We also study the effectiveness of the different heuristics proposed. © 2011 Springer-Verlag London Limited., The authors are indebted to the referees and editor for a close examination of the paper, which has increased its quality and presentation. This work is partially funded by the Spanish Ministry of Science and Innovation, under the project "SMPA-Advanced Parallel Multiobjective Sequencing: Practical and Theoretical Advances" with reference DPI2008-03511/DPI. The authors should also thank the IMPIVA-Institute for the Small and Medium Valencian Enterprise, for the project OSC with references IMIDIC/2008/137, IMIDIC/2009/198, and IMIDIC/2010/175.
RiuNet. Repositorio Institucional de la Universitat Politécnica de Valéncia
Publicación Artículo científico (JournalArticle)

Scheduling unrelated parallel machines with optional machines and jobs selection

  • Fanjul Peyró, Luis
  • Ruiz García, Rubén
[EN] In this paper we study two generalizations of the well known unrelated parallel machines scheduling problem under makespan (Cmax) minimization. First, a situation in which not every available parallel machine should be used and it is desirable to employ only a subset of the parallel machines. This is referred to as Not All Machines or NAM in short. This environment applies frequently in production shops where capacity exceeds demand or when production capacity can be lent to third companies. Also, NAM can be used to increase production capacity and it is not clear how many additional machines should be acquired. The second studied generalization has been referred to as Not All Jobs or NAJ. Here, there is no obligation to process all available jobs. We propose Mixed Integer Programming mathematical formulations for both NAM and NAJ, and it is shown that the latter can be effectively solved with modern commercial solvers. We also present three algorithms to solve the NAM problem. These algorithms are compared with the proposed MIP formulation when solved with IBM ILOG CPLEX 12.1. Comprehensive computational and statistical experiments prove that our proposed algorithms significantly improve the results given by the solver. © 2011 Elsevier Ltd. All rights reserved., The authors would like to thank the anonymous referees for their careful and detailed comments which have helped to improve this manuscript considerably. This work is partially funded by the Spanish Ministry of Science and Innovation, under the project ‘‘SMPA—Advanced Parallel Multiobjective Sequencing: Practical and Theoretical Advances’’ with reference DPI2008-03511/DPI. The authors should also thank the IMPIVA—Institute for the Small and Medium Valencian Enterprise, under the project ‘‘OSC’’ with references IMIDIC/2008/137, IMIDIC/2009/198 and IMIDIC/2010/175 and the Polytechnic University of Valencia, under the project ‘‘PPAR— Production Programming in Highly Constrained Environments: New Algorithms and Computational Advances’’ with reference 3147.
RiuNet. Repositorio Institucional de la Universitat Politécnica de Valéncia
Publicación Artículo científico (JournalArticle)

Restarted Iterated Pareto Greedy algorithm for multi-objective flowshop scheduling problems

  • Minella, Gerardo Gabriel
  • Ruiz García, Rubén
  • Ciavotta, Michele
Multi-objective optimisation problems have seen a large impulse in the last decades. Many new techniques for solving distinct variants of multi-objective problems have been proposed. Production scheduling, as with other operations management fields, is no different. The flowshop problem is among the most widely studied scheduling settings. Recently, the Iterated Greedy methodology for solving the single-objective version of the flowshop problem has produced state-of-the-art results. This paper proposes a new algorithm based on Iterated Greedy technique for solving the multi-objective permutation flowshop problem. This algorithm is characterised by an effective initialisation of the population, management of the Pareto front, and a specially tailored local search, among other things. The proposed multi-objective Iterated Greedy method is shown to outperform other recent approaches in comprehensive computational and statistical tests that comprise a large number of instances with objectives involving makespan, tardiness and flowtime. Lastly, we use a novel graphical tool to compare the performances of stochastic Pareto fronts based on Empirical Attainment Functions. © 2011 Elsevier Ltd., The authors are indebted to the anonymous referees for their helpful comments which have helped in improving an earlier version of this manuscript. This work is partially funded by the Spanish Ministry of Science and Innovation, under the projects "SMPA - Advanced Parallel Multiobjective Sequencing: Practical and Theoretical Advances" with reference DPI2008-03511/DPI. The authors should also thank the IMPIVA - Institute for the Small and Medium Valencian Enterprise, for the project OSC with references IMIDIC/2008/137, IMIDIC/2009/198 and IMIDIC/2010/175 and the Polytechnic University of Valencia, for the project PPAR with reference 3147.
RiuNet. Repositorio Institucional de la Universitat Politécnica de Valéncia
Publicación Artículo científico (JournalArticle)

Size-reduction heuristics for the unrelated parallel machines scheduling problem

  • Fanjul Peyró, Luis
  • Ruiz García, Rubén
[EN] In this paper we study the unrelated parallel machines problem where n independent jobs must be assigned to one out of m parallel machines and the processing time of each job differs from machine to machine. We deal with the objective of the minimisation of the maximum completion time of the jobs, usually referred to as makespan or Cmax. This is a type of assignment problem that has been frequently studied in the scienti¿c literature due to its many potential applications. We propose a set of metaheuristics based on a size-reduction of the original assignment problem that produce solutions of very good quality in a short amount of time. The underlying idea is to consider only a few of the best possible machine assignments for the jobs and not all of them. The results are simple, yet powerful methods. We test the proposed algorithms with a large benchmark of instances and compare them with current state-of-the-art methods. In most cases, the proposed size-reduction algorithms produce results that are statistically proven to be better by a signi¿cant margin. & 2010 Elsevier Ltd. All rights reserved, This work is partially funded by the Spanish Ministry of Science and Innovation, under the project ‘‘SMPA—Advanced Parallel Multiobjective Sequencing: Practical and Theoretical Advances’’ with references number DPI2008-03511/DPI. The authors should also thank the IMPIVA—Institute for the Small and Medium Valencian Enterprise, for the project OSC with reference IMIDIC/2008/137 and the Polytechnic University of Valencia, for the project PPAR with reference 3147.
RiuNet. Repositorio Institucional de la Universitat Politécnica de Valéncia
Publicación Artículo científico (JournalArticle)

The effect of the asymmetry of road transportation networks on the traveling salesman problem

  • Rodríguez Villalobos, Alejandro|||0000-0003-1079-6121
  • Ruiz García, Rubén
The routing of vehicles on road transportation networks is an area of great importance to transportation planners within scientific literature. This field includes well known and studied problems like traveling salesman problems or TSP or the more realistic asymmetric variant or ATSP, whose applications extend to other areas of transport and operations research. This work studies the effect that the asymmetry of road transportation networks, geographical location and territory have over TSP and ATSP methods. We conduct comprehensive experiments in order to assess the effects that these factors have on some of the best known algorithms for the TSP/ATSP. We demonstrate that all these factors have a significant influence in solution time and quality. Furthermore, we show that the solutions obtained with Euclidean matrices and those obtained with real distance matrices differ significantly. © 2011 Elsevier Ltd. All rights reserved., The authors would like to warmly thank Prof. Keld Helsgaun, Prof. Yuichi Nagata, Profs. Boris Goldengorin and Gerold Jager, and especially Prof. Matteo Fischetti, for facilitating the code of their great algorithms. This work is partially funded by the Spanish Ministry of Science and Innovation, under the project "SMPA Advanced Parallel Multiobjective Sequencing: Practical and Theoretical Advances" with reference DPI2008-03511/DPI. The authors should also thank the IMPIVA-Institute for the Small and Medium Valencian Enterprise, for the project OSC with references IMIDIC/2008/137, IMIDIC/2009/198 and 175 and the Polytechnic University of Valencia, for the project PPAR with reference 3147.