Pasar al contenido principal

TECNICAS PARA LA EVALUACION Y OBTENCION DE SOLUCIONES ESTABLES Y ROBUSTAS EN PROBLEMAS DE OPTIMIZACION Y SATISFACCION DE RESTRICCIONES

TIN2010-20976-C02-01

•
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 2010
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): 12
Encontrada(s) 1 página(s)

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

Finding robust solutions for constraint satisfaction problems with discrete and ordered domains by coverings

  • Climent Aunes, Laura Isabel
  • Miguel A. Salido|||0000-0002-4835-4057
  • Barber, Federico|||0000-0002-3966-5742
  • Wallace, Richard J.
Constraint programming is a paradigm wherein relations between variables are stated in the form of constraints. Many real life problems come from uncertain and dynamic environments, where the initial constraints and domains may change during its execution. Thus, the solution found for the problem may become invalid. The search forrobustsolutions for constraint satisfaction problems (CSPs) has become an important issue in the ¿eld of constraint programming. In some cases, there exists knowledge about the uncertain and dynamic environment. In other cases, this information is unknown or hard to obtain. In this paper, we consider CSPs with discrete and ordered domains where changes only involve restrictions or expansions of domains or constraints. To this end, we model CSPs as weighted CSPs (WCSPs) by assigning weights to each valid tuple of the problem constraints and domains. The weight of each valid tuple is based on its distance from the borders of the space of valid tuples in the corresponding constraint/domain. This distance is estimated by a new concept introduced in this paper: coverings. Thus, the best solution for the modeled WCSP can be considered as a most robust solution for the original CSP according to these assumptions, This work has been partially supported by the research projects TIN2010-20976-C02-01 (Min. de Ciencia e Innovacion, Spain) and P19/08 (Min. de Fomento, Spain-FEDER), and the fellowship program FPU.
RiuNet. Repositorio Institucional de la Universitat Politécnica de Valéncia
Publicación Artículo científico (JournalArticle)

Robustness in Dynamic Constraint Satisfaction Problems

  • Climent Aunes, Laura Isabel
  • Miguel A. Salido|||0000-0002-4835-4057
  • Barber, Federico|||0000-0002-3966-5742
[EN] Constraint programming is a successful technology for solving combinatorial problems modeled as constraint satisfaction problems (CSPs). Many real life problems are dynamic, which means that the initial description of the problem may change during its execution. These problems can be modeled as dynamic constraint satisfaction problems (DynCSPs), which are an important extension of the CSPs. In this paper, we focus our attention on the concept of robustness. Our aim is to find robust solutions which have a high probability of remaining valid faced with possible future changes in the constraints of the problem. We introduce the informed DynCSPs, proposing an approach to solve them by the weighted CSP (WCSP) modeling. Thus, the best solution for the modeled WCSP will be a robust solution for the original DynCSP. Furthermore, this technique has been evaluated in order to analyze the robustness of the solutions obtained., This work has been partially supported by the research projects TIN2010-20976-C02-01 (Min. de Ciencia e Innovación, Spain) and P19/08 (Min. de Fomento, Spain-FEDER), and the fellowship program FPU.
RiuNet. Repositorio Institucional de la Universitat Politécnica de Valéncia
Publicación Artículo científico (JournalArticle)

A decision support system for managing combinatorial problems in container terminals

  • Miguel A. Salido|||0000-0002-4835-4057
  • Barber, Federico|||0000-0002-3966-5742
  • Rodríguez Molins, Mario
[EN] A container terminal is a facility where cargo containers are transshipped between different transport vehicles. We focus our attention on the transshipment between vessels and land vehicles, in which case the terminal is described as a maritime container terminal. In these container terminals, many combinatorial related problems appear and the solution of one of the problems may affect to the solution of other related problems. For instance, the berth allocation problem can affect to the crane assignment problem and both could also affect to the Container Stacking Problem. Thus, terminal operators normally demand all containers to be loaded into an incoming vessel should be ready and easily accessible in the yard before vessel's arrival. Similarly, customers (i.e., vessel owners) expect prompt berthing of their vessels upon arrival. However the efficiency of the loading/unloading tasks of containers in a vessel depends on the number of assigned cranes and the efficiency of the container yard logistic. In this paper, we present a decision support system to guide the operators in the development of these typical tasks. Due to some of these problems are combinatorial, some analytical formulas are presented to estimate the behavior of the container terminal. © 2011 Elsevier B.V. All rights reserved., This work has been partially supported by the research projects TIN2010-20976-C02-01 (Min. de Educacion y Ciencia, Spain-FEDER), P19/08 (Min. de Fomento, Spain-FEDER), and the VALi+d Program of the Conselleria d'Educacio (Generalitat Valenciana), as well as with the collaboration of the maritime container terminal MSC (Mediterranean Shipping Company S.A.).
RiuNet. Repositorio Institucional de la Universitat Politécnica de Valéncia
Publicación Artículo científico (JournalArticle)

A Fine-grained Arc-consistency Algorithm for Non-Normalized Constraint Satisfaction Problems

  • Arangú Lobig, Marlene Alicia
  • Miguel A. Salido|||0000-0002-4835-4057
Constraint programming is a powerful software technology for solving numerous real-life problems. Many of these problems can be modeled as Constraint Satisfaction Problems (CSPs) and solved using constraint programming techniques. However, solving a CSP is NP-complete so filtering techniques to reduce the search space are still necessary. Arc-consistency algorithms are widely used to prune the search space. The concept of arc-consistency is bidirectional, i.e., it must be ensured in both directions of the constraint (direct and inverse constraints). Two of the most well-known and frequently used arc-consistency algorithms for filtering CSPs are AC3 and AC4. These algorithms repeatedly carry out revisions and require support checks for identifying and deleting all unsupported values from the domains. Nevertheless, many revisions are ineffective, i.e., they cannot delete any value and consume a lot of checks and time. In this paper, we present AC4-OP, an optimized version of AC4 that manages the binary and non-normalized constraints in only one direction, storing the inverse founded supports for their later evaluation. Thus, it reduces the propagation phase avoiding unnecessary or ineffective checking. The use of AC4-OP reduces the number of constraint checks by 50% while pruning the same search space as AC4. The evaluation section shows the improvement of AC4-OP over AC4, AC6 and AC7 in random and non-normalized instances., This work has been partially supported by the research projects TIN2010-20976-C02-01 (Ministry of Science and Innovation, Spain) and P19/08 (Ministry of Development, Spain, FEDER).
RiuNet. Repositorio Institucional de la Universitat Politécnica de Valéncia
Publicación Artículo científico (JournalArticle)

Robustness and Stability in Constraint Programming under Dynamism and Uncertainty

  • Climent Aunes, Laura Isabel
  • Miguel A. Salido|||0000-0002-4835-4057
  • Barber, Federico|||0000-0002-3966-5742
  • Wallace, Richard
[EN] Many real life problems that can be solved by constraint programming, come from uncertain and dynamic environments. Because of the dynamism, the original problem may change over time, and thus the solution found for the original problem may become invalid. For this reason, dealing with such problems has become an important issue in the fields of constraint programming. In some cases, there is extant knowledge about the uncertain and dynamic environment. In other cases, this information is fragmentary or unknown. In this paper, we extend the concept of robustness and stability for Constraint Satisfaction Problems (CSPs) with ordered domains, where only limited assumptions need to be made as to possible changes. We present a search algorithm that searches for both robust and stable solutions for CSPs of this nature. It is well-known that meeting both criteria simultaneously is a desirable objective for constraint solving in uncertain and dynamic environments. We also present compelling evidence that our search algorithm outperforms other general-purpose algorithms for dynamic CSPs using random instances and benchmarks derived from real life problems., This work has been partially supported by the research project TIN2010-20976-C02-01 and FPU program fellowship (Min. de Ciencia e Innovacion, Spain). We wish to thank Dr. Christophe Lecoutre and Dr. Diarmuid Grimes for their assistance.
RiuNet. Repositorio Institucional de la Universitat Politécnica de Valéncia
Publicación Artículo científico (JournalArticle)

A FILTERING TECHNIQUE TO ACHIEVE 2-CONSISTENCY IN CONSTRAINT SATISFACTION PROBLEMS

  • Arangú Lobig, Marlene Alicia
  • Miguel A. Salido|||0000-0002-4835-4057
  • Barber, Federico|||0000-0002-3966-5742
[EN] Arc-Consistency algorithms are the most commonly used ltering techniques to prune the search space in Constraint Satisfaction Problems (CSPs). 2-consistency is a similar technique that guarantees that any instantiation of a value to a variable can be consistently extended to any second variable. Thus, 2-consistency can be stronger than arc-consistency in binary CSPs. In this work we present a new algorithm to achieve 2- consistency called 2-C4. This algorithm is a reformulation of AC4 algorithm that is able to reduce unnecessary checking and prune more search space than AC4. The experimental results show that 2-C4 was able to prune more search space than arc-consistency algo- rithms in non-normalized instances. Furthermore, 2-C4 was more efficient than other 2-consistency algorithms presented in the literature., This work has been partially supported by the research project TIN2010- 20976-C02-01 (Min. de Educacion y Ciencia, Spain-FEDER).
RiuNet. Repositorio Institucional de la Universitat Politécnica de Valéncia
Publicación Artículo científico (JournalArticle)

Robustness for a single railway line: Analytical and simulation methods

  • Miguel A. Salido|||0000-0002-4835-4057
  • Barber, Federico|||0000-0002-3966-5742
  • Ingolotti Hetter, Laura Paola
[EN] Railway scheduling has been a significant issue in the railway industry. Over the last few years, numerous approaches and tools have been developed to compute railway scheduling. However, robust solutions are necessary to absorb short disruptions. In this paper, we present the robustness problem from the point of view of railway operators and we propose analytical and simulation methods to measure robustness in a single railway line. In the analytical approach, we have developed some formulas to measure robustness based on the study of railway line infrastructure topology and buffer times. In the simulation approach, we have developed a software tool to assess the robustness for a given schedule. These methods have been inserted in MOM (More information can be found at the MOM web page http://www.dsic.upv.es/users/ia/gps/MOM), which is a project in collaboration with the Spanish Railway Infrastructure Manager (ADIF). © 2012 Elsevier Ltd. All rights reserved., This work has been partially supported by the research project TIN2010-20976-C02-01 (Min. de Economia y Competitividad, Spain) and project PIRSES-GA-2011-294931 (FP7-PEOPLE-2011-IRSES).
RiuNet. Repositorio Institucional de la Universitat Politécnica de Valéncia
Publicación Artículo científico (JournalArticle)

Energy-efficient scheduling for a flexible flow shop using an improved genetic-simulated annealing algorithm

  • Dai, Min
  • Tang, Dunbing
  • Li, W.D.
  • Giret Boggino, Adriana Susana|||0000-0002-2311-0785
  • Miguel A. Salido|||0000-0002-4835-4057
[EN] The traditional production scheduling problem considers performance indicators such as processing time, cost and quality as optimization objectives in manufacturing systems; however, it does not take energy consumption and environmental impacts into account completely. Therefore, this paper proposes an energy-efficient model for flexible flow-shop scheduling (FFS). First, a mathematical model for a FFS problem, which is based on an energy-efficient mechanism, is described to solve multi-objective optimization. Since FFS is well known as the NPhard problem, an improved genetic-simulated annealing algorithm is adopted to make a significant trade-off between the makespan and the total energy consumption for implementing a feasible scheduling. Finally, a case study of production scheduling problem for metalworking workshop in a plant is simulated. The experimental results show the relationship between the makespan and the energy consumption is conflicting apparently. Moreover, an energy saving decision is performed in a feasible scheduling. Using the decision method, there can be a significant potential to minimize energy consumption while complying with the conflicting relationship, This research was carried out as a part of the CASES project which is supported by a Marie Curie International Research Staff Exchange Scheme Fellowship within the 7th European Community Framework Program under the Grant agreement no 294931. This research was also supported by National Science Foundation of China (No. 51175262), Jiangsu Province Science Foundation for Excellent Youths (No. BK201210111), Jiangsu Province Industry-Academy-Research Grant (No. BY201220116), the NUAA Fundamental Research Fund (No. NS2013053), the Project Funded by Priority Academic Program Development of Jiangsu Higher Education Institutions (PAPD), and the research project TIN2010-20976-C02-01 (Ministry of Science and Innovation, Spain).
RiuNet. Repositorio Institucional de la Universitat Politécnica de Valéncia
Publicación Artículo científico (JournalArticle)

Solving the job shop scheduling problem with operators by depth-first heuristic search enhanced with global pruning rules

  • Mencia, Carlos
  • Sierra, María R.
  • Varela, Ramiro
  • Miguel A. Salido|||0000-0002-4835-4057
  • Escamilla-Fuster, Joan
The job shop scheduling problem with an additional resource type has been recently proposed to model the situation where each operation in a job shop has to be assisted by one of a limited set of human operators. We confront this problem with the objective of minimizing the total flow time, which makes the problem more interesting from a practical point of view and harder to solve than the version with makespan minimization. To solve this problem we propose an enhanced dept-first search algorithm. This algorithm exploits a schedule generation schema termed OG&T, two admissible heuristics and some powerful pruning rules. In order to diversify the search, we also consider a variant of this algorithm with restarts. We have conducted an experimental study across several benchmarks. The results of this study show that the global pruning rules are really effective and that the proposed algorithms are quite competent for solving this problem., We are grateful to the anonymous referees for their comments and suggestions, that made it possible to improve this paper. This research has been supported by the Spanish Government under projects MEC-FEDER TIN-20976-C02-01 and TIN-20976-C02-02 and by the Principality of Asturias under Grant FICYT-BP09105.
RiuNet. Repositorio Institucional de la Universitat Politécnica de Valéncia
Publicación Artículo científico (JournalArticle)

Intelligent planning for allocating containers in maritime terminals

  • Rodríguez Molins, Mario
  • Miguel A. Salido|||0000-0002-4835-4057
  • Barber, Federico|||0000-0002-3966-5742
Maritime container terminals are facilities where cargo containers are transshipped between ships or between ships and land vehicles (tucks or trains). These terminals involve a large number of complex and combinatorial problems. One of them is related to the Container Stacking Problem. A container yard is a type of temporary store where containers await further transport by truck, train or vessel. The main efficiency problem for an individual stack is to ensure easy access to containers at the expected time of transfer. Stacks are 'last-in, first-out' storage structures where containers are stocked in the order they arrive. But they should be retrieved from the stack in the order (usually different) they should be shipped. This retrieval operation should be efficiently performed, since berthing time of vessels and the terminal operations should be optimized. To do this, cranes can relocate containers in the stacks to minimize the rearrangements required to meet the expected order of demand for containers. In this paper, we present a domain-dependent heuristically guided planner for obtaining the optimized reshuffling plan, given a stacking state and a container demand. The planner can also be used for finding the best allocation of containers in a yard-bay in order to minimize the number of reshuffles as well as to be used for simulation tasks and obtaining conclusions about possible yard configurations. © 2011 Elsevier Ltd. All rights reserved., This work has been partially supported by the research projects TIN2010-20976-C02-01 (Min. de Ciencia e Innovacion, Spain), P19/08 (Min. de Fomento, Spain-FEDER) and the VALi+d Program of the Conselleria d'Educacio (Generalitat Valenciana), as well as with the collaboration of the maritime container terminal MSC (Mediterranean Shipping Company S.A.).
RiuNet. Repositorio Institucional de la Universitat Politécnica de Valéncia
Publicación Artículo científico (JournalArticle)

A genetic algorithm for robust berth allocation and quay crane assignment

  • Rodríguez Molins, Mario
  • Ingolotti Hetter, Laura Paola
  • Sierra, María R.
  • Puente, Jorge
  • Barber, Federico|||0000-0002-3966-5742
  • Miguel A. Salido|||0000-0002-4835-4057
[EN] Scheduling problems usually obtain the optimal solutions assuming that the environment is deterministic. However, actually the environment is dynamic and uncertain. Thus, the initial data could change and the initial schedule obtained might be unfeasible. To overcome this issue, a proactive approach is presented for scheduling problems without any previous knowledge about the incidences that can occur. In this paper, we consider the berth allocation problem and the quay crane assignment problem as a representative example of scheduling problems where a typical objective is to minimize the service time. The robustness is introduced within this problem by means of buffer times that should be maximized to absorb possible incidences or breakdowns. Therefore, this problem becomes a multi-objective optimization problem with two opposite objectives: minimizing the total service time and maximizing the robustness or buffer times., This research was supported by the Spanish Government under research projects TIN2010-20976-C02-01 and TIN2010-20976-C02-02 (Min. de Ciencia e Innovación, Spain), 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)

A GRASP-based metaheuristic for the Berth Allocation Problem and the Quay Crane Assignment Problem by managing vessel cargo holds

  • Rodríguez Molins, Mario
  • Miguel A. Salido|||0000-0002-4835-4057
  • Barber, Federico|||0000-0002-3966-5742
Container terminals are open systems that generally serve as a transshipment zone between vessels and land vehicles. These terminals carry out a large number of planning and scheduling tasks. In this paper, we consider the problem of scheduling a number of incoming vessels by assigning a berthing position, a berthing time, and a number of Quay Cranes to each vessel. This problem is known as the Berth Allocation Problem and the Quay Crane Assignment Problem. Holds of vessels are also managed in order to obtain a more realistic approach. Our aim is to minimize the total waiting time elapsed to serve all these vessels. In this paper, we deal with the above problems and propose an innovative metaheuristic approach. The results are compared against other allocation methods., This work has been partially supported by the research projects TIN2010-20976-C02-01 (Ministerio de Ciencia e Innovacion, Spain) the fellowship program FPU (AP2010-4405), and also with the collaboration of the maritime container terminal MSC (Mediterranean Shipping Company S.A.).