Explore the vast range of titles available.

Many real-world scheduling problems are solved to obtain optimal solutions in term of processing time, cost, and quality as optimization objectives. Currently, energy-efficiency 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 job-shop 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.

Train 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. In this paper, we present a set of heuristics for a constraint-based train scheduling tool, which is a project in collaboration with the National Network of Spanish Railways (RENFE), Spain. We formulate train scheduling as constraint optimization problems. Three heuristics are developed to speed up and direct the search toward suboptimal solutions in periodic train scheduling problems. The feasibility of our problem-oriented heuristics is confirmed with experimentation using real-life data. The results show that these techniques enable MIP solvers such as LINGO and ILOG Concert Technology (CPLEX) to terminate earlier with good solutions.

Many real life problems can be modeled as a scheduling problem. The main objective of these problems is to obtain optimal solutions in terms of processing time, cost and quality. Nowadays, energy-efficiency is also taken into consideration. However, these problems are 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 classical job-shop scheduling problem. In the extended version, each operation has to be executed by one machine and this machine can work at different speed rates. The machines consume different amounts of energy to process tasks at different rates. The evaluation section shows that a powerful commercial tools 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.

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.

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 unforeseen 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 (CSPs). 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.

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 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.

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+.

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 exist 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.

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 for robust solutions for constraint satisfaction problems (CSPs) has become an important issue in the field 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.