In this article, we propose an integrated formulation of the combined production and material handling scheduling problems. Traditionally, scheduling problems consider the production machines as the only constraining ...
详细信息
In this article, we propose an integrated formulation of the combined production and material handling scheduling problems. Traditionally, scheduling problems consider the production machines as the only constraining resource. This is however no longer true as material handling vehicles are becoming more and more valuable resources requiring important investments. Their operations should be optimized and above all synchronized with machine operations. In the problem addressed in this paper, a job shop context is considered. Machines and vehicles are both considered as constraining resources. The integrated scheduling problem is formulated as a mathematical programming model and as a constraint programming model which are compared for optimally solving a series of test problems. A commercial software (ILOG OPLStudio) was used for modeling and testing both models. (c) 2005 Elsevier B.V. All rights reserved.
As underlying infrastructure of cloud computing platform, datacenter is seriously underutilized, however, its operating costs is high. In this paper, we implement virtual machines placement algorithm in CloudSim using...
详细信息
In 2004, Jean-Francois Puget presented [2] an analysis of the "simplicity of Use" of constraint programming from which he articulated a series of challenges to make constraint programming systems accessible ...
详细信息
Block modeling has been used extensively in many domains including social science, spatial temporal data analysis and even medical imaging. Original formulations of the problem modeled it as a mixed integer programmin...
详细信息
Block modeling has been used extensively in many domains including social science, spatial temporal data analysis and even medical imaging. Original formulations of the problem modeled it as a mixed integer programming problem, but were not scalable. Subsequent work relaxed the discrete optimization requirement, and showed that adding constraints is not straightforward in existing approaches. In this work, we present a new approach based on constraint programming, allowing discrete optimization of block modeling in a manner that is not only scalable, but also allows the easy incorporation of constraints. We introduce a new constraint filtering algorithm that outperforms earlier approaches, in both constrained and unconstrained settings, for an exhaustive search and for a type of local search called Large Neighborhood Search. We show its use in the analysis of real datasets. Finally, we show an application of the CP framework for model selection using the Minimum Description Length principle.
A key feature of modem optimal planners such as GRAPHPLAN and BLACKBOX is their ability to prune large parts of the search space. Previous Partial Order Causal Link (POCL) planners provide an alternative branching sch...
详细信息
A key feature of modem optimal planners such as GRAPHPLAN and BLACKBOX is their ability to prune large parts of the search space. Previous Partial Order Causal Link (POCL) planners provide an alternative branching scheme but lacking comparable pruning mechanisms do not perform as well. In this paper, a domain-independent formulation of temporal planning based on constraint programming is introduced that successfully combines a POCL branching scheme with powerful and sound pruning rules. The key novelty in the formulation is the ability to reason about supports, precedences, and causal links involving actions that are not in the plan. Experiments over a wide range of benchmarks show that the resulting optimal temporal planner is much faster than current ones and is competitive with the best parallel planners in the special case in which actions have all the same duration.(1) (c) 2005 Elsevier B.V. All rights reserved.
The team orienteering problem with time windows (TOPTW) is a well-known variant of the orienteering problem (OP) originated from the sports game of orienteering. Since the TOPTW has many applications in the real world...
详细信息
The team orienteering problem with time windows (TOPTW) is a well-known variant of the orienteering problem (OP) originated from the sports game of orienteering. Since the TOPTW has many applications in the real world such as disaster relief routing and home fuel delivery, it has been studied extensively. In the classical TOPTW, only one profit is associated with each checkpoint while in many practical applications each checkpoint can be evaluated from different aspects, which results in multiple profits. In this study, the multi-objective team orienteering problem with time windows (MOTOPTW), where checkpoints with multiple profits are considered, is introduced to find the set of Pareto optimal solutions to support decision making. Moreover, a multi-objective evolutionary algorithm based on decomposition and constraint programming (CPMOEA/D) is developed to solve the MOTOPTW. The advantages of decomposition approaches to handle multi-objective optimization problems and those of the constraint programming to deal with combinatorial optimization problems have been integrated in CPMOEA/D. Finally, the proposed algorithm is applied to solve public benchmark instances. The results are compared with the best-known solutions from the literature and show more improvement. (C) 2018 Elsevier B.V. All rights reserved.
Context: The use of Business Process Management Systems (BPMS) has emerged in the IT arena for the automation of business processes. In the majority of cases, the issue of security is overlooked by default in these sy...
详细信息
Context: The use of Business Process Management Systems (BPMS) has emerged in the IT arena for the automation of business processes. In the majority of cases, the issue of security is overlooked by default in these systems, and hence the potential cost and consequences of the materialization of threats could produce catastrophic loss for organizations. Therefore, the early selection of security controls that mitigate risks is a real and important necessity. Nevertheless, there exists an enormous range of IT security controls and their configuration is a human, manual, time-consuming and error-prone task. Furthermore, configurations are carried out separately from the organization perspective and involve many security stakeholders. This separation makes difficult to ensure the effectiveness of the configuration with regard to organizational requirements. Objective: In this paper, we strive to provide security stakeholders with automated tools for the optimal selection of IT security configurations in accordance with a range of business process scenarios and organizational multi-criteria. Method: An approach based on feature model analysis and constraint programming techniques is presented, which enable the automated analysis and selection of optimal security configurations. Results: A catalogue of feature models is determined by analyzing typical IT security controls for BPMSs for the enforcement of the standard goals of security: integrity, confidentiality, availability, authorization, and authentication. These feature models have been implemented through constraint programs, and constraint programming techniques based on optimized and non-optimized searches are used to automate the selection and generation of configurations. In order to compare the results of the determination of configuration a comparative analysis is given. Conclusion: In this paper, we present innovative tools based on feature models, constraint programming and multi-objective techniques that en
This paper presents constraint programming models that aim to solve scheduling and tool assignment problems in parallel machine environments. There are a number of jobs to be processed on parallel machines. Each job r...
详细信息
This paper presents constraint programming models that aim to solve scheduling and tool assignment problems in parallel machine environments. There are a number of jobs to be processed on parallel machines. Each job requires a set of tools, but limited number of tools are available in the system due to economic restrictions. The problem is to assign the jobs and the required tools to machines and to determine the schedule so that the makespan is minimised. Three constraint programming models are developed and compared with existing methods described in the literature.
作者：
Jaulin, LucOSM
IHSEV LabSTICC 2 Rue Francois Verny F-29806 Brest France
This paper deals with the simultaneous localization and mapping problem (SLAM) for a robot. The robot has to build a map of its environment while localizing itself using a partially built map. It is assumed that (i) t...
详细信息
This paper deals with the simultaneous localization and mapping problem (SLAM) for a robot. The robot has to build a map of its environment while localizing itself using a partially built map. It is assumed that (i) the map is made of point landmarks, (ii) the landmarks are indistinguishable, (iii) the only exteroceptive measurements correspond to the distance between the robot and the landmarks. This paper shows that SLAM can be cast into a constraint network the variables of which being trajectories, digraphs and subsets of Then, we show how constraint propagation can be extended to deal with such generalized constraint networks. As a result, due to the redundancy of measurements of SLAM, we demonstrate that a constraint-based approach provides an efficient backtrack-free algorithm able to solve our SLAM problem in a guaranteed way.
Context: Testing highly-configurable software systems is challenging due to a large number of test configurations that have to be carefully selected in order to reduce the testing effort as much as possible, while mai...
详细信息
Context: Testing highly-configurable software systems is challenging due to a large number of test configurations that have to be carefully selected in order to reduce the testing effort as much as possible, while maintaining high software quality. Finding the smallest set of valid test configurations that ensure sufficient coverage of the system's feature interactions is thus the objective of validation engineers, especially when the execution of test configurations is costly or time-consuming. However, this problem is NP-hard in general and approximation algorithms have often been used to address it in practice. Objective: In this paper, we explore an alternative exact approach based on constraint programming that will allow engineers to increase the effectiveness of configuration testing while keeping the number of configurations as low as possible. Method: Our approach consists in using a (time-aware) minimization algorithm based on constraint programming. Given the amount of time, our solution generates a minimized set of valid test configurations that ensure coverage of all pairs of feature values (a.k.a. pairwise coverage). The approach has been implemented in a tool called PACOGEN. Results: PACOGEN was evaluated on 224 feature models in comparison with the two existing tools that are based on a greedy algorithm. For 79% of 224 feature models, PACOGEN generated up to 60% fewer test configurations than the competitor tools. We further evaluated PACOGEN in the case study of an industrial video conferencing product line with a feature model of 169 features, and found 60% fewer configurations compared with the manual approach followed by test engineers. The set of test configurations generated by PACOGEN decreased the time required by test engineers in manual test configuration by 85%, increasing the feature-pairs coverage at the same time. Conclusion: Our experimental evaluation concluded that optimal time-aware minimization of pairwise-covering test configurati
暂无评论