Pasar al contenido principal

Resultados relacionados

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

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.