We present a generic exact method for minimizing the project duration of the resource-constrained project scheduling problem with generalized precedence relations (Rcpsp/max). This is a very general scheduling model w...
详细信息
We present a generic exact method for minimizing the project duration of the resource-constrained project scheduling problem with generalized precedence relations (Rcpsp/max). This is a very general scheduling model with applications areas such as project management and production planning. Our method uses lazy clause generation, i.e., a hybrid of finite domain and Boolean satisfiability solving, in order to apply no-good learning and conflict-driven search to the solution generation. Our experiments show the benefit of lazy clause generation for finding an optimal solution and proving its optimality in comparison to other state-of-the-art exact and non-exact methods. In comparison to other methods, our method is able to find better solutions faster on the Rcpsp/max benchmarks. Indeed, our method closes 573 open problem instances and generates better solutions in most of the remaining instances. Surprisingly, although ours is an exact method, it outperforms the published non-exact methods on these benchmarks in terms of the quality of solutions.
Computation techniques have provided designers with deeper understanding of the market niches that were neglected before. Usage contextual information has been studied in marketing research since the last century;howe...
详细信息
Computation techniques have provided designers with deeper understanding of the market niches that were neglected before. Usage contextual information has been studied in marketing research since the last century;however, little research in design engineering focuses on it. Therefore, in this paper, we analyzed the relations between usage context information and the design of products. A usage coverage model is established to integrate users and their expected usage scenarios into product family assessment. We map the user's individual capacity together with a given product into the usage context space. The overlapping between the required usage and feasible usage can be measured. Based on this mechanism, several usage coverage indices are proposed to assess the compliance of a given product family to the expected set of usage scenarios to be covered. The original method is demonstrated on a scale-based product family of jigsaws in a redesign context. constraint programming technique is applied to solve the physics-based causal loops that determine usage performances in a set-based design approach. Designers can rely on the results to eliminate redundant units in the family or modify the configuration of each product. The contribution of the paper is to provide an inter-disciplinary point of view to assessing the composition and configuration of a product family design.
This paper studies the interactions between crane handling and truck transportation in a maritime container terminal by addressing them simultaneously. Yard trucks are shared among different ships, which helps to redu...
详细信息
This paper studies the interactions between crane handling and truck transportation in a maritime container terminal by addressing them simultaneously. Yard trucks are shared among different ships, which helps to reduce empty truck trips in the terminal area. The problem is formulated as a constraint programming model and a three-stage algorithm is developed. At the first stage, crane schedules are generated by a heuristic method. At the second stage, the multiple-truck routing problem is solved based on the precedence relations of the transportation tasks derived from the first stage. At the last stage a complete solution is constructed by using a disjunctive graph. The three procedures are linked by an iterative structure, which facilitates the search for a good solution. The computational results indicate that the three-stage algorithm is effective for finding high-quality solutions and can efficiently solve large problems. (C) 2012 Elsevier B.V. All rights reserved.
Nowadays, a growing interest in aligning information systems in a process-oriented way exists as well as in the effective business process management (BPM). Since an instance of a business process (BP) is analogous to...
详细信息
Nowadays, a growing interest in aligning information systems in a process-oriented way exists as well as in the effective business process management (BPM). Since an instance of a business process (BP) is analogous to a plan which also includes allocation of resources, planning and scheduling (P&S) techniques can be very helpful for increasing the efficiency in BPM. In this work, innovative and rather relevant contributions related to constraint-based P&S approaches are proposed to optimize different stages of the BPM life cycle.
In order to be able to flexibly adjust a company's business processes (BPs) there is an increasing interest in flexible process-aware information systems (PAISs). This increasing flexibility, however, typically im...
详细信息
In order to be able to flexibly adjust a company's business processes (BPs) there is an increasing interest in flexible process-aware information systems (PAISs). This increasing flexibility, however, typically implies decreased user guidance by the PAIS and thus poses significant challenges to its users. As a major contribution of this work, we propose a recommendation system which assists users during process execution to optimize performance goals of the processes. The recommendation system is based on a constraint-based approach for planning and scheduling the BP activities and considers both the control-flow and the resource perspective. To evaluate the proposed constraint-based approach different algorithms are applied to a range of test models of varying complexity. The results indicate that, although the optimization of process execution is a highly constrained problem, the proposed approach produces a satisfactory number of suitable solutions. (c) 2013 Elsevier B.V. All rights reserved.
To model operational business processes in an accurate way, workflow models need to reference both the control flow and dataflow perspectives. Checking the correctness of such workflow models and giving precise feedba...
详细信息
To model operational business processes in an accurate way, workflow models need to reference both the control flow and dataflow perspectives. Checking the correctness of such workflow models and giving precise feedback in case of errors is challenging due to the interplay between these different perspectives. In this paper, we propose a fully automated approach for diagnosing correctness of semantic workflow models in which the semantics of activities are specified with pre and postconditions. The control flow and dataflow perspectives of a semantic workflow are modeled in an integrated way using Artificial Intelligence techniques (Integer programming and constraint programming). The approach has been implemented in the DiagFlow tool, which reads and diagnoses annotated XPDL models, using a state-of-the-art constraint solver as back end. Using this novel approach, complex semantic workflow models can be verified and diagnosed in an efficient way. (C) 2013 Elsevier B.V. All rights reserved.
Intentional islanding of a power system can be an emergency response for isolating failures that might propagate and lead to major disturbances. Some of the islanding techniques suggested previously do not consider th...
详细信息
Intentional islanding of a power system can be an emergency response for isolating failures that might propagate and lead to major disturbances. Some of the islanding techniques suggested previously do not consider the power flow model;others are designed to minimize load shedding only within the islands. Often these techniques are computationally expensive. We aim to find approaches to partition power grids into islands to minimize the load shedding not only in the region where the failures start, but also in the topological complement of the region. We propose a new constraint programming formulation for optimal islanding in power grid networks. This technique works efficiently for small networks but becomes expensive as size increases. To address the scalability problem, we propose two grid partitioning methods based on modularity, properly modified to take into account the power flow model. They are modifications of the Fast Greedy algorithm and the Bloom algorithm, and are polynomial in running time. We tested these methods on the available IEEE test systems. The Bloom type method is faster than the Fast Greedy type, and can potentially provide results in networks with thousands of nodes. Our methods provide solutions which retain at least 40-50% of the system load. Overall, our methods efficiently balance load shedding and scalability. (C) 2013 Elsevier B.V. All rights reserved.
Data-Flow models are attracting renewed attention because they lend themselves to efficient mapping on. multi-core architectures. The key problem of finding a maximum-throughput allocation and scheduling of Synchronou...
详细信息
Data-Flow models are attracting renewed attention because they lend themselves to efficient mapping on. multi-core architectures. The key problem of finding a maximum-throughput allocation and scheduling of Synchronous Data-Flow graphs (SDFGs) onto a multi-core architecture is NP-hard and has been traditionally solved by means of heuristic (incomplete) algorithms with no guarantee of global optimality. In this paper we propose an exact (complete) algorithm for the computation of a maximum-throughput mapping of applications specified as SDFG onto multi-core architectures. This is, to the best of our knowledge, the first complete algorithm for generic SDF graphs, including those with loops and a finite iteration bound. Our approach is based on constraint programming, it guarantees optimality and can handle realistic instances in terms of size and complexity. Extensive experiments on a large number of SDFGs demonstrate that our approach is effective and robust. (C) 2013 Elsevier Inc. All rights reserved.
We consider a scheduling problem arising in the mining industry. Ore from several mining sites must be transferred to ports to be loaded on ships in a timely manner. In doing so, several constraints must be met which ...
详细信息
We consider a scheduling problem arising in the mining industry. Ore from several mining sites must be transferred to ports to be loaded on ships in a timely manner. In doing so, several constraints must be met which involve transporting the ore and deadlines. These deadlines are two-fold: there is a preferred deadline by which the ships should be loaded and there is a final deadline by which time the ships must be loaded. Corresponding to the two types of deadlines, each task is associated with a soft and hard due time. The objective is to minimize the cumulative tardiness, measured using the soft due times, across all tasks. This problem can be formulated as a resource constrained job scheduling problem where several tasks must be scheduled on multiple machines satisfying precedence and resource constraints and an objective to minimize total weighted tardiness. For this problem we present hybrids of ant colony optimization, Beam search and constraint programming. These algorithms have previously shown to be effective on similar tightly-constrained combinatorial optimization problems. We show that the hybrid involving all three algorithms provides the best solutions, particularly with respect to feasibility. We also investigate alternative estimates for guiding the Beam search component of our algorithms and show that stochastic sampling is the most effective. (c) 2012 Elsevier B.V. All rights reserved.
This paper studies the redundancy properties of the constraints used when formulating the well known Latin Square problem. This problem is often formulated using either (N -aEuro parts per thousand 1)*N (2) binary dis...
详细信息
This paper studies the redundancy properties of the constraints used when formulating the well known Latin Square problem. This problem is often formulated using either (N -aEuro parts per thousand 1)*N (2) binary disequalities or 2*N all_different global constraints. Both formulations contain redundant constraints. A complete classification of all redundant sets of constraints, be they binary or global, is performed for any N.
暂无评论