This paper presents a technique for symmetry, reduction that adaptively assigns a prefix of variables in a system of constraints so that the generated prefix-assignments are pairwise nonisomorphic under the action of ...
详细信息
This paper presents a technique for symmetry, reduction that adaptively assigns a prefix of variables in a system of constraints so that the generated prefix-assignments are pairwise nonisomorphic under the action of the symmetry group of the system. The technique is based on McKay's canonical extension framework (McKay, 1998). Among key features of the technique are (i) adaptability-the prefix sequence can be user-prescribed and truncated for compatibility with the group of symmetries;(ii) parallelizability prefix-assignments can be processed in parallel independently of each other;(iii) versatility-the method is applicable whenever the group of symmetries can be concisely represented as the automorphism group of a vertex-colored graph;and (iv) implementability-the method can be implemented relying on a canonical labeling map for vertex-colored graphs as the only nontrivial subroutine. To demonstrate the practical applicability of our technique, we have prepared an experimental open-source implementation of the technique and carry out a set of experiments that demonstrate ability to reduce symmetry on hard instances. Furthermore, we demonstrate that the implementation effectively parallelizes to compute clusters with multiple nodes via a message-passing interface. (C) 2019 The Authors. Published by Elsevier Ltd.
The QoS-based service selection in a highly dynamical environment is becoming a challenging issue. In practice, the QoS fluctuations of a service composition entail major difficulties in measuring the degree to which ...
详细信息
The QoS-based service selection in a highly dynamical environment is becoming a challenging issue. In practice, the QoS fluctuations of a service composition entail major difficulties in measuring the degree to which the user requirements are satisfied. In addition, the search space of feasible compositions (i.e., the solutions that preserve the requirements) is generally large and cannot be explored in a limited time;therefore, we need an approach that not only copes with the presence of uncertainty but also ensures a pertinent search with a reduced computational cost. To tackle this problem, we propose a constraint programming framework and a set of ranking heuristics that both reduce the search space and ensure a set of reliable compositions. The conducted experiments show that the ranking heuristics, termed 'fuzzy dominance' and 'probabilistic skyline', outperform almost all existing state-of-the-art methods.
This paper introduces a new practical scheduling problem called the resource-constrained project scheduling problem under multiple time constraints, which involves a duration constraint of activity, temporal constrain...
详细信息
This paper introduces a new practical scheduling problem called the resource-constrained project scheduling problem under multiple time constraints, which involves a duration constraint of activity, temporal constraint, and resource calendar constraint. The duration constraint of the activity exists widely in real-life projects, and it is first proposed as a resource-constrained project scheduling problem in this paper. We prove the defects of the traditional temporal constraint and improve it. The new problem combines three types of time constraints for the first time, which makes it closer to the actual scheduling problem. We developed a constraint programming optimization model for the new problem and used the IBM ILOG CPLEX-CP version 12.9.0 optimizer to solve it. Computational experiments are carried out to show that the CP optimizer is fast and provides a near-optimum solution to the new problem for projects with hundreds of activities within minutes compared to other metaheuristic methods. The results reported in this paper can be used as a benchmark for other researchers to compare and improve. The new problem contributes to developing a practical decision support system for resolving real-life constraints in projects.
constraint programming (CP) is a powerful declarative programming paradigm where inference and search are interleaved to find feasible and optimal solutions to various type of constraint systems. However, handling log...
详细信息
constraint programming (CP) is a powerful declarative programming paradigm where inference and search are interleaved to find feasible and optimal solutions to various type of constraint systems. However, handling logical connectors with constructive information in CP is notoriously difficult. This paper presents If Then Else (ITE), a lightweight implementation of stratified constructive reasoning for logical connectives. Stratification is introduced to cope with the risk of combinatorial explosion of constructing information from nested and combined logical operators. ITE is an open-source library built on top of SICStus Prolog clpfd, which proposes various operators, including constructive disjunction and negation, constructive implication and conditional. These operators can be used to express global constraints and to benefit from constructive reasoning for more domain pruning during constraint filtering. Even though ITE is not competitive with specialized filtering algorithms available in some global constraints implementations, its expressiveness allows users to easily define well-tuned constraints with powerful deduction capabilities. Our extended experimental results show that ITE is more efficient than available generic approaches that handle logical constraint systems over finite domains.
With the growing demand for more efficient hardware accelerators for streaming applications, a novel Coarse-Grained Reconfigurable Architecture (CGRA) that uses a Distributed Two-Level Control (D2LC) system has been p...
详细信息
ISBN:
(纸本)9783981926361
With the growing demand for more efficient hardware accelerators for streaming applications, a novel Coarse-Grained Reconfigurable Architecture (CGRA) that uses a Distributed Two-Level Control (D2LC) system has been proposed in the literature. Even though the highly distributed and parallel structure makes it fast and energy-efficient, the single-issue instruction channel between the level-1 and level-2 controller in each D2LC cell becomes the bottleneck of its performance. In this paper, we improve its design to mimic a multi-issued architecture by inserting shadow instruction buffers between the level-1 and level-2 controllers. Together with a zero-overhead hardware loop, the improved D2LC architecture can enable efficient overlap between loop iterations. We also propose a complete constraint programming based instruction scheduling algorithm to support the above hardware features. The experiment result shows that the improved D2LC architecture can achieve up to 25% of reduction on the instruction execution cycles and 35% reduction on the energy-delay product.
Cooperation among constraint solvers is difficult because different solving paradigms have different theoretical foundations. Recent works have shown that abstract interpretation can provide a unifying theory for vari...
详细信息
Cooperation among constraint solvers is difficult because different solving paradigms have different theoretical foundations. Recent works have shown that abstract interpretation can provide a unifying theory for various constraint solvers. In particular, it relies on abstract domains which capture constraint languages as ordered structures. The key insight of this paper is viewing cooperation schemes as abstract domains combinations. We propose a modular framework in which solvers and cooperation schemes can be seamlessly added and combined. This differs from existing approaches such as SMT where the cooperation scheme is usually fixed (e.g., Nelson-Oppen). We contribute to two new cooperation schemes: (i)interval propagators completionthat allows abstract domains to exchange bound constraints, and (ii)delayed productwhich exchanges over-approximations of constraints between two abstract domains. Moreover, the delayed product is based on delayed goal of logic programming, and it shows that abstract domains can also capture control aspects of constraint solving. Finally, to achieve modularity, we propose theshared productto combine abstract domains and cooperation schemes. Our approach has been fully implemented, and we provide various examples on the flexible job shop scheduling problem.
With the advent of industry-4.0 era, industrial production are evolving towards high flexibility, diversity, customisation, and dynamism. We address a realistic scenario of a smart manufacturing system, which concerns...
详细信息
With the advent of industry-4.0 era, industrial production are evolving towards high flexibility, diversity, customisation, and dynamism. We address a realistic scenario of a smart manufacturing system, which concerns the production scheduling of complex multi-level products under a dynamic flexible job shop environment with shop floor disruptions incorporated. The products are assembled from multiple basic parts, whose fabrication processes are highly flexible, involving alternative process plans, alternative machines and alternative processing sequences of operations. We aim at providing Pareto solutions, with consideration of three typical optimisation objectives, including makespan, maximum machine workload, and total tardiness. A hybrid MPGA-CP approach is designed for the problem. To the best our knowledge, this is the first attempt to embed an exact optimisation technique into a meta-heuristic algorithm in the domain of production scheduling. Compared with other alternative approaches, its efficiency and performance are proven to be outstanding in solving medium-to-large scale problems, covering the largest proportion of Pareto solutions among all tested approaches. Furthermore, we constructed a simulation model of a real-time production scheduling control system, in which our approach is embedded as the kernel algorithm, to study the impacts of some uncertainties that are concerned in practice. Based on the results of simulation experiments and sensitivity analysis, meaningful managerial insights have been provided.
作者：
Winter, FelixMusliu, NysretTU Wien
DBAI Inst Log & Computat Christian Doppler Lab Artificial Intelligence & O Favoritenstr 9 Vienna Austria
Factories in the automotive supply industry paint a large number of items requested by car manufacturing companies on a daily basis. As these factories face numerous constraints and optimization objectives, finding a ...
详细信息
Factories in the automotive supply industry paint a large number of items requested by car manufacturing companies on a daily basis. As these factories face numerous constraints and optimization objectives, finding a good schedule becomes a challenging task in practice, and full-time employees are expected to manually create feasible production plans. In this study, we propose novel constraint programming models for a real-life paint shop scheduling problem. We evaluate and compare our models experimentally by performing a series of benchmark experiments using real-life instances in the industry. We also show that the decision variant of the paint shop scheduling problem is NP-complete.
This survey covers the basic principles and related works addressing the time-triggered scheduling of periodic tasks with deadlines. The wide range of applications and the increasing complexity of modern real-time sys...
详细信息
This survey covers the basic principles and related works addressing the time-triggered scheduling of periodic tasks with deadlines. The wide range of applications and the increasing complexity of modern real-time systems result in the continually growing interest in this topic. However, the articles in this field appear without systematic notation. To address it, we extend the three-field Graham notation to cover periodic scheduling. Moreover, we formally define three example periodic scheduling problems (PSPs) and provide straightforward implementations of these examples in the Satisfiability Modulo Theories formalism with source codes. Then, we present a summary of the complexity results containing existing polynomially solvable PSPs. We also provide an overview of simple state-of-the-art methods and tricks to solve the PSPs efficiently in terms of time. Next, we survey the existing works on PSP according to the resource environment: scheduling on a single resource, on parallel identical resources, and on dedicated resources. In the survey, we indicate which works propose solution methods for more general PSPs. Finally, we present related problems that are not periodic by nature to provide inspiration for the PSP solution.
Cooperation among constraint solvers is difficult because different solving paradigms have different theoretical foundations. Recent works have shown that abstract interpretation can provide a unifying theory for vari...
详细信息
Cooperation among constraint solvers is difficult because different solving paradigms have different theoretical foundations. Recent works have shown that abstract interpretation can provide a unifying theory for various constraint solvers. In particular, it relies on abstract domains which capture constraint languages as ordered structures. The key insight of this paper is viewing cooperation schemes as abstract domains combinations. We propose a modular framework in which solvers and cooperation schemes can be seamlessly added and combined. This differs from existing approaches such as SMT where the cooperation scheme is usually fixed (e.g., Nelson-Oppen). We contribute to two new cooperation schemes: (i)interval propagators completionthat allows abstract domains to exchange bound constraints, and (ii)delayed productwhich exchanges over-approximations of constraints between two abstract domains. Moreover, the delayed product is based on delayed goal of logic programming, and it shows that abstract domains can also capture control aspects of constraint solving. Finally, to achieve modularity, we propose theshared productto combine abstract domains and cooperation schemes. Our approach has been fully implemented, and we provide various examples on the flexible job shop scheduling problem.
暂无评论