Search

The urgent need for sustainable development is imposing radical changes in the way manufacturing systems are designed and implemented. The overall sustainability in industrial activities of manufacturing companies must be achieved at the same time that they face unprecedented levels of global competition. Therefore, there is a well-known need for tools and methods that can support the design and implementation of these systems in an effective way. This paper proposes an engineering method that helps researchers to design sustainable intelligent manufacturing systems. The approach is focused on the identification of the manufacturing components and the design and integration of sustainability-oriented mechanisms in the system specification, providing specific development guidelines and tools with built-in support for sustainable features. Besides, a set of case studies is presented in order to assess the proposed method. [ABSTRACT FROM AUTHOR]

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. [ABSTRACT FROM AUTHOR]

Abstract: 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). [Copyright &y& Elsevier]

Abstract: 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. [Copyright &y& Elsevier]

Abstract: Maritime container terminals are facilities where cargo containers are transshipped between ships or between ships and land vehicles (trucks or trains). These terminals involve a large number of complex and combinatorial problems. Two important problems are the container stacking problem and the berth allocation problem. Both problems are generally managed and solved independently but there exist a relationship that must be taken into account to optimize the whole process. The terminal operator normally demands all containers bound for an incoming vessel to be ready in the terminal before its arrival. Similarly, customers (i.e., vessel owners) expect prompt berthing of their vessels upon arrival. This is particularly important for vessels from priority customers who may have been guaranteed berth-on-arrival service in their contract with the terminal operator. To this end, both problems must be interrelated. In this paper, a set of artificial intelligence based-techniques for solving both problems is presented. We develop a planning technique for solving the container stacking problem and a set of optimized allocation algorithms for solving the berth allocation problem independently. Finally we have developed an architecture to solve both problems in an integrated way. Thus, an algorithm for solving the berth allocation problem generates an optimized order of vessels to be served meanwhile our container stacking problem heuristics calculate the minimum number of reshuffles needed to allocate the containers in the appropriate place for the obtained ordering of vessels. Thus combined optimal solutions can be calculated and the terminal operator could decide which solution is more appropriate in each case. These techniques will minimize disruptions and facilitate planning in container terminals. [Copyright &y& Elsevier]

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. [ABSTRACT FROM AUTHOR]

Abstract: Many problems of theoretical and practical interest can be formulated as Constraint Satisfaction Problems (CSPs). Solving a general CSP is known to be NP-complete; however, distributed models may take advantage of dividing the problem into a set of simpler inter-connected sub-problems which can be more easily solved. The purpose of this paper is three-fold: first, we present a technique to distribute the constraint network by means of selection of tree structures. Thus, the CSP is represented as a meta-tree CSP structure that is used as a hierarchy of communication by our distributed algorithm. Then, a distributed and asynchronous search algorithm (DTS) is presented. DTS is committed to solving the meta-tree CSP structure in a depth-first search tree. Finally, an intra-agent search algorithm is presented. This algorithm takes into account the Nogood_message to prune the search space. We have focused our research on the railway scheduling problem which can be distributed by tree structures. We show that our distributed algorithm outperforms well-known centralized algorithms. [Copyright &y& Elsevier]

Abstract: A distributed constraint satisfaction problem (DisCSP) is a CSP in which variables and constraints are distributed among multiple automated agents. Many researchers have developed techniques for solving DisCSPs. They assume for simplicity that each agent has exactly one variable. For real planning and scheduling problems, these techniques require a large number of messages passing among agents, so these problems are very difficult to solve. In this paper, we present a general distributed model for solving real-life scheduling problems. This distributed model is based on the idea of holonic systems. Furthermore, we propose some guidelines for distributing large-scale problems. Finally, we present two case studies in which two scheduling problems are distributed by using our model. [Copyright &y& Elsevier]

Abstract: The areas of Artificial Intelligence (AI) planning and scheduling have seen important advances thanks to the application of constraint satisfaction models and techniques. Most real-world problems are typically known as highly coupled planning and scheduling problems, where resources must be allocated so as to optimize overall performance objectives. Therefore, solving these problems requires an adequate mixture of planning, scheduling and resource allocation to competing goal activities over time in the presence of complex state-dependent constraints; i.e., solutions to these problems must integrate resource allocation and plan synthesis capabilities, which can be efficiently managed by using constraint techniques. This special issue of Engineering Applications of Artificial Intelligence on “Constraint Satisfaction Techniques for Planning and Scheduling Problems” compiles a selection of papers of COPLAS’07: the joint CP/ICAPS-2007 workshop of the same name and presents novel issues on planning, scheduling, constraint programming/constraint satisfaction problems (CSPs) and many other common areas that exist among them. On the whole, this issue mainly focus on managing complex problems where planning, scheduling and constraint satisfaction must be combined and/or interrelated, which entails an enormous potential for practical applications and future research. [Copyright &y& Elsevier]

Abstract: Nowadays many real problems can be modelled as constraint satisfaction problems (CSPs). A search algorithm for constraint programming requires an order in which variables and values should to be considered. Choosing the right order of variables and values can noticeably improve the efficiency of constraint satisfaction. Furthermore, the order in which constraints are studied can improve efficiency, particularly in problems with non-binary constraints. In this paper, we present a preprocess heuristic called constraint ordering heuristic (COH) that studies the constrainedness of the scheduling problem and mainly classifies the constraints so that the tightest ones are studied first. Thus, constrainedness can be known in advance and overall inconsistencies can be found earlier and the number of constraint checks can significantly be reduced. [Copyright &y& Elsevier]

Abstract: Nowadays, many real problems in artificial intelligence can be modelled as constraint satisfaction problems (CSPs). A general CSP is known to be NP-complete. Nevertheless, distributed models may reduce the exponential complexity by partitioning the problem into a set of subproblems. In this paper, we present a preprocess technique to break a single large problem into a set of smaller loosely connected ones. These semi-independent CSPs can be efficiently solved and, furthermore, they can be solved concurrently. [Copyright &y& Elsevier]

Nowadays, many real problems can be modelled as Constraint Satisfaction Problems (CSPs). Some CSPs are considered non-binary disjunctive CSPs. Many researchers study the problems of deciding consistency for Disjunctive Linear Relations (DLRs). In this paper, we propose a new class of constraints called Extended DLRs consisting of disjunctions of linear inequalities, linear disequations and non-linear disequations. This new class of constraints extends the class of DLRs. We propose a heuristic algorithm called DPOLYSA that solves Extended DLRs, as a non-binary disjunctive CSP solver. This proposal works on a polyhedron whose vertices are also polyhedra that represent the nondisjunctive problems. We also present a statistical preprocessing step which translates the disjunctive problem into a non-disjunctive and ordered one in each step. [Copyright &y& Elsevier]

Manufacturing industries are faced with environmental challenges, so their industrial processes must be optimized in terms of both profitability and sustainability. Since most of these processes are dynamic, the previously obtained solutions cannot be valid after disruptions. This paper focuses on recovery in dynamic job-shop scheduling problems where machines can work at different rates. Machine speed scaling is an alternative framework to the on/off control framework for production scheduling. Thus, given a disruption, the main goal is to recover the original solution by rescheduling the minimum number of tasks. To this end, a new match-up technique is developed to determine the rescheduling zone and a feasible reschedule. Then, a memetic algorithm is proposed for finding a schedule that minimizes the energy consumption within the rescheduling zone but that also maintains the makespan constraint. An extensive study is carried out to analyze the behavior of our algorithms to recover the original solution and minimize the energy reduction in different benchmarks, which are taken from the OR-Library. The energy consumption and processing time of the tasks involved in the rescheduling zone will play an important role in determining the best match-up point and the optimized rescheduling. Upon a disruption, different rescheduling solutions can be obtained, all of which comply with the requirements but that have different values of energy consumption. The results proposed in this paper may be useful for application in real industries for energy-efficient production rescheduling. [ABSTRACT FROM AUTHOR]

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. [ABSTRACT FROM AUTHOR]

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. [ABSTRACT FROM AUTHOR]

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. [ABSTRACT FROM AUTHOR]

In recent decades, research on supply chain management (SCM) has enabled companies to improve their environmental, social, and economic performance. This paper presents an industrial application of logistics that can be classified as an inventory-route problem. The problem consists of assigning orders to the available warehouses. The orders are composed of items that must be loaded within a week. The warehouses provide an inventory of the number of items available for each day of the week, so the objective is to minimize the total transportation costs and the costs of producing extra stock to satisfy the weekly demand. To solve this problem a formal mathematical model is proposed. Then a hybrid approach that involves two metaheuristics: a greedy randomized adaptive search procedure (GRASP) and a genetic algorithm (GA) is proposed. Additionally, a meta-learning tuning method is incorporated into our hybridized approach, which yields better results but with a longer computation time. Thus, the trade-off of using it is analyzed. An extensive evaluation was carried out over realistic instances provided by an industrial partner. The proposed technique was evaluated and compared with several complete and incomplete solvers from the state of the art (CP Optimizer, Yuck, OR-Tools, etc.). The results showed that our hybrid metaheuristic outperformed the behavior of these well-known solvers, mainly in large-scale instances (2000 orders per week). This hybrid algorithm provides the company with a powerful tool to solve its supply chain management problem, delivering significant economic benefits every week. [ABSTRACT FROM AUTHOR]

• A new optimization method called Search and Rescue optimization algorithm (SAR) is proposed. • SAR is tested on 13 constrained benchmark functions and CEC2010 benchmark functions. • Experiment results show superiority of SAR compared with other optimization methods. • SAR is also used for solving 7 engineering optimization problems. • The results on the engineering problems prove the performance of SAR in practice. A new optimization method namely the Search and Rescue optimization algorithm (SAR) is presented here to solve constrained engineering optimization problems. This metaheuristic algorithm imitates the explorations behavior of humans during search and rescue operations. The ε-constrained method is utilized as a constraint-handling technique. Besides, a restart strategy is proposed to avoid local infeasible minima in some complex constrained optimization problems. SAR is applied to solve 18 benchmark constraint functions presented in CEC 2010, 13 benchmark constraint functions, and 7 constrained engineering design problems reported in the specialized literature. The performance of SAR is compared with some state-of-the-art optimization algorithms. According to the statistical comparison results, the performance of SAR is better or highly competitive against the compared algorithms on most of the studied problems. [ABSTRACT FROM AUTHOR]

In this paper, a new optimization algorithm called the search and rescue optimization algorithm (SAR) is proposed for solving single-objective continuous optimization problems. SAR is inspired by the explorations carried out by humans during search and rescue operations. The performance of SAR was evaluated on fifty-five optimization functions including a set of classic benchmark functions and a set of modern CEC 2013 benchmark functions from the literature. The obtained results were compared with twelve optimization algorithms including well-known optimization algorithms, recent variants of GA, DE, CMA-ES, and PSO, and recent metaheuristic algorithms. The Wilcoxon signed-rank test was used for some of the comparisons, and the convergence behavior of SAR was investigated. The statistical results indicated SAR is highly competitive with the compared algorithms. Also, in order to evaluate the application of SAR on real-world optimization problems, it was applied to three engineering design problems, and the results revealed that SAR is able to find more accurate solutions with fewer function evaluations in comparison with the other existing algorithms. Thus, the proposed algorithm can be considered an efficient optimization method for real-world optimization problems. [ABSTRACT FROM AUTHOR]

Abstract: Analyzing the state of the art in a given field in order to tackle a new problem is always a mandatory task. Literature provides surveys based on summaries of previous studies, which are often based on theoretical descriptions of the methods. An engineer, however, requires some evidence from experimental evaluations in order to make the appropriate decision when selecting a technique for a problem. This is what we have done in this paper: experimentally analyzed a set of representative state-of-the-art techniques in the problem we are dealing with, namely, the road passenger transportation problem. This is an optimization problem in which drivers should be assigned to transport services, fulfilling some constraints and minimizing some function cost. The experimental results have provided us with good knowledge of the properties of several methods, such as modeling expressiveness, anytime behavior, computational time, memory requirements, parameters, and free downloadable tools. Based on our experience, we are able to choose a technique to solve our problem. We hope that this analysis is also helpful for other engineers facing a similar problem. [Copyright &y& Elsevier]

This paper presents an improved watermarking scheme for soft Intellectual Property (IP) -Cores using Genetic Algorithms (GAs). For this purpose, a watermark signature and an IP-Core behavioral description are translated into Finite State Machines (FSMs). Both FSMs are merged in a single one containing a watermarked IP-Core without disrupting its original functionality. Therefore, we tackle NP-completeness of the subgraph isomorphism problem found during FSMs merging process via a tailored GA. However, not deeply embedded states are a key problem that may ease watermark's removal. To overcome this issue, a FSM reduction algorithm is also considered in the proposed watermarking scheme. Moreover, the proposed scheme also targets transitions regrouping which impact the amount of hardware resources usage and a mechanism for selecting the best watermarked FSM. A thorough empirical assessment shows a significant improvement in terms of reduction and watermark embedding strength. • A novel IP cores watermarking scheme using genetic algorithms. • Watermarking process works at behavioral IP Cores level. • Two NP-complete problems are tackled: FSMs merging and reduction. • Removal attacks resistance and minimal resources overheard are accomplished. • Full functionality recoverability, robustness and strong authorship are achieved. [ABSTRACT FROM AUTHOR]