Pasar al contenido principal

TECNICAS INTELIGENTES PARA LA OBTENCION DE SOLUCIONES ROBUSTAS Y EFICIENTES ENERGETICAMENTE EN SCHEDULING: APLICACION AL TRANSPORTE::UPV

TIN2013-46511-C2-1-P

•
Nombre agencia financiadora Ministerio de Economía y Competitividad
Acrónimo agencia financiadora MINECO
Programa Programa Estatal de Fomento de la Investigación Científica y Técnica de Excelencia
Subprograma Subprograma Estatal de Generación de Conocimiento
Convocatoria Proyectos de I+D (Excelencia / Generación de Conocimiento)
Año convocatoria 2013
Plan Estatal 2013-2016 Plan Estatal de Investigación Científica y Técnica y de Innovación
Unidad de gestión Secretaría de Estado de Educación, Formación Profesional y Universidades
Centro beneficiario UNIVERSITAT POLITÈCNICA DE VALÈNCIA
Identificador persistente http://dx.doi.org/10.13039/501100003329

Resultados relacionados

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

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

A Dual Scheduling Model for Optimizing Robustness and Energy Consumption in Manufacturing Systems

  • Escamilla-Fuster, Joan
  • Miguel A. Salido|||0000-0002-4835-4057
[EN] Manufacturing systems involve a huge number of combinatorial problems that must be optimized in an efficient way. One of these problems is related to task scheduling problems. These problems are NP-hard, so most of the complete techniques are not able to obtain an optimal solution in an efficient way. Furthermore, most of real manufacturing problems are dynamic, so the main objective is not only to obtain an optimized solution in terms of makespan, tardiness, and so on but also to obtain a solution able to absorb minor incidences/disruptions presented in any daily process. Most of these industries are also focused on improving the energy efficiency of their industrial processes. In this article, we propose a knowledge-based model to analyse previous incidences occurred in the machines with the aim of modelling the problem to obtain robust and energy-aware solutions. The resultant model (called dual model) will protect the more dynamic and disrupted tasks by assigning buffer times. These buffers will be used to absorb incidences during execution and to reduce the machine rate to minimize energy consumption. This model is solved by a memetic algorithm which combines a genetic algorithm with a local search to obtain robust and energy-aware solutions able to absorb further disruptions. The proposed dual model has been proven to be efficient in terms of energy consumption, robustness and stability in different and well-known benchmarks., The author(s) disclosed receipt of the following financial support for the research, authorship, and/or publication of this article: This research has been supported by the Spanish Government under research project TIN2013-46511-C2-1 for the Spanish government and the TETRACOM EU project FP7-ICT-2013-10-No 609491.
RiuNet. Repositorio Institucional de la Universitat Politécnica de Valéncia
Publicación Artículo científico (JournalArticle)

Energy-efficient dynamic scheduling for a flexible flow shop using an improved particle swarm optimization

  • Tang, Dunbing
  • Dai, Min
  • Miguel A. Salido|||0000-0002-4835-4057
  • Giret Boggino, Adriana Susana|||0000-0002-2311-0785
Due to increasing energy requirements and associated environmental impacts, nowadays manufacturing companies are facing the emergent challenges to meet the demand of sustainable manufacturing. Most existing research on reducing energy consumption in production scheduling problems has focused on static scheduling models. However, there exist many unexpected disruptions like new job arrivals and machine breakdown in a real-world production scheduling. In this paper, it is proposed an approach to address the dynamic scheduling problem reducing energy consumption and makespan for a flexible flow shop scheduling. Since the problem is strongly NP-hard, a novel algorithm based on an improved particle swarm optimization is adopted to search for the Pareto optimal solution in dynamic flexible flow shop scheduling problems. Finally, numerical experiments are carried out to evaluate the performance and efficiency of the proposed approach., This research was carried out as a part of the CASES project which is supported by the 7th European Community Framework Programme under the grant agreement No. 294931 and the grant TIN2013-46511-C2-1-P by the Spanish Government. This research was also supported by National Natural Science Foundation of China (No. 51175262), Jiangsu Province Science Foundation for Excellent Youths (No. BK2012032).
RiuNet. Repositorio Institucional de la Universitat Politécnica de Valéncia
Publicación Artículo científico (JournalArticle)

A Genetic Algorithm for Energy-Efficiency in Job-Shop Scheduling

  • Miguel A. Salido|||0000-0002-4835-4057
  • Escamilla-Fuster, Joan
  • Giret Boggino, Adriana Susana|||0000-0002-2311-0785
  • Barber, Federico|||0000-0002-3966-5742
Many real-world scheduling problems are solved to obtain optimal solutions in term of processing time, cost, and quality as optimization objectives. Currently, energyefficiency is also taken into consideration in these problems. However, this problem is NP-hard, so many search techniques are not able to obtain a solution in a reasonable time. In this paper, a genetic algorithm is developed to solve an extended version of the Job-shop Scheduling Problem in which machines can consume different amounts of energy to process tasks at different rates (speed scaling). This problem represents an extension of the classical jobshop scheduling problem, where each operation has to be executed by one machine and this machine can work at different speeds. The evaluation section shows that a powerful commercial tool for solving scheduling problems was not able to solve large instances in a reasonable time, meanwhile our genetic algorithm was able to solve all instances with a good solution quality., This research has been supported by the Spanish Government under research project MINECO TIN2013-46511-C2-1 and the CASES project supported by a Marie Curie International Research Staff Exchange Scheme Fellowship within the 7th European Community Framework Programme under the grant agreement No 294931. We would like to thanks Philippe Laborie (IBM ILOG CPLEX) for validating the CP Optimizer model for this problem. We also appreciate the significant efforts made by all the reviewers to improve this paper.
RiuNet. Repositorio Institucional de la Universitat Politécnica de Valéncia
Publicación Artículo científico (JournalArticle)

PSPLIB-ENERGY: Una extension de la libreria PSPLIB para la evaluacion de la optimizacion energetica en el RCPSP

  • Morillo Torres, Daniel
  • Barber, Federico|||0000-0002-3966-5742
  • Miguel A. Salido|||0000-0002-4835-4057
[EN] Scheduling problems is one of the core areas in the planning and development of any project, with a wide applicability to real-world situations. Due to the high complexity of these problems, the solving process is often based on metaheuristics techniques, so that the evaluation of these methods is empirical. Therefore benchmarks, which provide a set of test cases to assess the behavior of algorithms, are generated. This paper extends the PSPLIB library. This extension incorporates to each instance of RCPSP (Resource Constrained Project Scheduling Problem), a realistic mathematical model of energy consumption. This proposal provides an alternative to the current trend in the feld of optimization and manufacturing that requires the inclusion of components and methods that reduce the environmental impact in the process of decision making. Finally a new optimality criterion is proposed to compare dierent search techniques. The PSPLIB-ENERGY is available at http://gps.webs.upv.es/psplib-energy/, [ES] Los problemas de scheduling constituyen una de las ´areas centrales en la planificaci´on y desarrollo de cualquier proyecto, con una gran aplicabilidad a situaciones del mundo real. Debido a la gran complejidad que habitualmente presentan estos problemas, su resoluci´on suele basarse en m´etodos metaheur´ısticos de optimizaci´on, de forma que la evaluaci´on de estos m´etodos es emp´ırica. Por esta raz´on se generan benchmarks, que proveen de un conjunto de casos de prueba que permiten evaluar el comportamiento de los algoritmos que se desarrollan. En este art´ıculo se extiende la librer´ıa PSPLIB. Esta extensi´on consiste en incorporar a cada instancia del RCPSP (Resource Constrained Project Scheduling Problem), un modelo matem´atico realista de consumo de energ´ıa. Esta propuesta brinda una alternativa a la tendencia actual en el campo de la optimizaci´on y la manufactura que demanda la inclusi´on de componentes y m´etodos que reduzcan el impacto ambiental en el proceso de toma de decisiones. Finalmente se propone un nuevo criterio de optimalidad para comparar las diferentes t´ecnicas de b´usqueda. La PSPLIB-ENERGY est´a disponible en http://gps.webs.upv.es/psplib-energy/., Este trabajo ha sido parcialmente financiado por el proyecto de Investigación TIN2013-46511-C2-1-P.
RiuNet. Repositorio Institucional de la Universitat Politécnica de Valéncia
Publicación Artículo científico (JournalArticle)

Mode-Based versus Activity-Based Search for a Nonredundant Resolution of the Multimode Resource-Constrained Project Scheduling Problem

  • Morillo-Torres, Daniel
  • Barber, Federico|||0000-0002-3966-5742
  • Miguel A. Salido|||0000-0002-4835-4057
[EN] This paper addresses an energy-based extension of the Multimode Resource-Constrained Project Scheduling Problem (MRCPSP) called MRCPSP-ENERGY. This extension considers the energy consumption as an additional resource that leads to different execution modes (and durations) of the activities. Consequently, different schedules can be obtained. The objective is to maximize the efficiency of the project, which takes into account the minimization of both makespan and energy consumption. This is a well-known NP-hard problem, such that the application of metaheuristic techniques is necessary to address real-size problems in a reasonable time. This paper shows that the Activity List representation, commonly used in metaheuristics, can lead to obtaining many redundant solutions, that is, solutions that have different representations but are in fact the same. This is a serious disadvantage for a search procedure. We propose a genetic algorithm(GA) for solving the MRCPSP-ENERGY, trying to avoid redundant solutions by focusing the search on the execution modes, by using the Mode List representation. The proposed GA is evaluated on different instances of the PSPLIB-ENERGY library and compared to the results obtained by both exact methods and approximate methods reported in the literature. This library is an extension of the well-known PSPLIB library, which contains MRCPSP-ENERGY test cases., This paper has been partially supported by the Spanish Research Projects TIN2013-46511-C2-1-P and TIN2016-80856-R.
RiuNet. Repositorio Institucional de la Universitat Politécnica de Valéncia
Publicación Artículo científico (JournalArticle)

Energy efficiency, robustness, and makespan optimality in job-shop scheduling problems

  • Miguel A. Salido|||0000-0002-4835-4057
  • Escamilla-Fuster, Joan
  • Barber, Federico|||0000-0002-3966-5742
  • Giret Boggino, Adriana Susana|||0000-0002-2311-0785
  • Tang, Dunbing
  • Dai, Min
[EN] Many real-world problems are known as planning and scheduling problems, where resources must be allocated so as to optimize overall performance objectives. The traditional scheduling models consider performance indicators such as processing time, cost, and quality as optimization objectives. However, most of them do not take into account energy consumption and robustness. We focus our attention in a job-shop scheduling problem where machines can work at different speeds. It represents an extension of the classical job-shop scheduling problem, where each operation has to be executed by one machine and this machine can work at different speeds. The main goal of the paper is focused on the analysis of three important objectives (energy efficiency, robustness, and makespan) and the relationship among them. We present some analytical formulas to estimate the ratio/relationship between these parameters. It can be observed that there exists a clear relationship between robustness and energy efficiency and a clear trade-off between robustness/energy efficiency and makespan. It represents an advance in the state of the art of production scheduling, so obtaining energy-efficient solutions also supposes obtaining robust solutions, and vice versa., This research has been supported by the Spanish Government under research project MICINN TIN2013-46511-C2-1-P, the European CASES project (No. 294931) supported by a Marie Curie International Research Staff Exchange Scheme Fellowship within the FP7, and the European TETRACOM project (No. 609491) supported by FP7-ICT-2013-10. This research was also supported by the National Science Foundation of China (No. 51175262) and the Jiangsu Province Science Foundation for Excellent Youths under Grant BK2012032.
RiuNet. Repositorio Institucional de la Universitat Politécnica de Valéncia
Publicación Artículo científico (JournalArticle)

Uncertainty in Dynamic Constraint Satisfaction Problems

  • Climent, Laura
  • Wallace, Richard J.
  • Miguel A. Salido|||0000-0002-4835-4057
  • Barber, Federico|||0000-0002-3966-5742
Many real life problems that can be modeled as Constraint Satisfaction Problems (CSPs) come from uncertain and dynamic environments, so the original solution found might become invalid after changes. Here, we study the problem of finding robust solutions for CSPs under the assumptions that domains are significantly ordered and that changes take the form of restrictions or relaxations at the borders of the solution space of the CSPs., This work was supported by the FPU and the project TIN2013-46511-C2-1-P (MINECO, Spain).
RiuNet. Repositorio Institucional de la Universitat Politécnica de Valéncia
Publicación Artículo científico (JournalArticle)

Robust scheduling for Berth Allocation and Quay Crane Assignment Problem

  • Rodríguez Molins, Mario
  • Miguel A. Salido|||0000-0002-4835-4057
  • Barber, Federico|||0000-0002-3966-5742
[EN] Decision makers must face the dynamism and uncertainty of real-world environments when they need to solve the scheduling problems. Different incidences or breakdowns, for example, initial data could change or some resources could become unavailable, may eventually cause the infeasibility of the obtained schedule. To overcome this issue, a robust model and a proactive approach are presented for scheduling problems without any previous knowledge about incidences. This paper is based on proportionally distributing operational buffers among the tasks. In this paper, we consider the berth allocation problem and the quay crane assignment problem as a representative example of scheduling problems. The dynamism and uncertainty are managed by assessing the robustness of the schedules. The robustness is introduced by means of operational buffer times to absorb those unknown incidences or breakdowns. Therefore, this problem becomes a multiobjective combinatorial optimization problem that aims to minimize the total service time, to maximize the buffer times, and to minimize the standard deviation of the buffer times. To this end, a mathematical model and a new hybrid multiobjective metaheuristic is presented and compared with two well-known multiobjective genetic algorithms: NSGAII and SPEA2+., This work has been partially supported by by the Spanish Government under research project MINECO TIN2013-46511-C2-1-P, the project PIRSES-GA-2011-294931 (FP7-PEOPLE-2011-IRSES), and the predoctoral FPU fellowship (AP2010-4405).
RiuNet. Repositorio Institucional de la Universitat Politécnica de Valéncia
Publicación Artículo científico (JournalArticle)

Robustness, stability, recoverability, and reliability in constraint satisfaction problems

  • Barber, Federico|||0000-0002-3966-5742
  • Miguel A. Salido|||0000-0002-4835-4057
Many real-world problems in Artificial Intelligence (AI) as well as in other areas of computer science and engineering can be efficiently modeled and solved using constraint programming techniques. In many real-world scenarios the problem is partially known, imprecise and dynamic such that some effects of actions are undesired and/or several un-foreseen incidences or changes can occur. Whereas expressivity, efficiency and optimality have been the typical goals in the area, there are several issues regarding robustness that have a clear relevance in dynamic Constraint Satisfaction Problems (CSP). However, there is still no clear and common definition of robustness-related concepts in CSPs. In this paper, we propose two clearly differentiated definitions for robustness and stability in CSP solutions. We also introduce the concepts of recoverability and reliability, which arise in temporal CSPs. All these definitions are based on related well-known concepts, which are addressed in engineering and other related areas., This work has been partially supported by the research project TIN2013-46511-C2-1 (MINECO, Spain). We would also thank the reviewers for their efforts and helpful comments.
RiuNet. Repositorio Institucional de la Universitat Politécnica de Valéncia
Publicación Artículo científico (JournalArticle)

A new model and metaheuristic approach for the energy-based resource-constrained scheduling problem

  • Morillo-Torres, Daniel
  • Barber, Federico|||0000-0002-3966-5742
  • Miguel A. Salido|||0000-0002-4835-4057
[EN] This article focuses on obtaining sustainable and energy-efficient solutions for limited resource programming problems. To this end, a model for integrating makespan and energy consumption objectives in multi-mode resource-constrained project scheduling problems (MRCPSP-ENERGY) is proposed. In addition, a metaheuristic approach for the efficient resolution of these problems is developed. In order to assess the appropriateness of theses proposals, the well-known Project Scheduling Problem Library is extended (called PSPLIB-ENERGY) to include energy consumption to each Resource-Constrained Project Scheduling Problem instance through a realistic mathematical model. This extension provides an alternative to the current trend of numerous research works about optimization and the manufacturing field, which require the inclusion of components to reduce the environmental impact on the decision-making process. PSPLIB-ENERGY is available at http://gps.webs.upv.es/psplib-energy/., The author(s) disclosed receipt of the following financial support for the research, authorship, and/or publication of this article: This research was supported by the Spanish Government under the research projects TIN2013-46511-C2-1 and TIN2016-80856-R.