solve machine learning problems, we have developed a method to identify closed sets of common features of objects (patterns) of the training sample. The novelty of the method lies in the fact that it is implemented wi...
详细信息
solve machine learning problems, we have developed a method to identify closed sets of common features of objects (patterns) of the training sample. The novelty of the method lies in the fact that it is implemented within the concept of constraint programming and uses a new type of table constraints-compressed tables of the D-type-for internal representation and processing of the training sample. Search reduction is achieved by applying the proposed method of branching the search tree and using partial order relations on sets of objects (features) to prune unpromising branches. The method has a computational complexity estimate that for some types of input data is better than the estimates obtained for the studied prototypes.
In simple assembly line balancing problems, it is assumed that the resources required to perform the tasks are available at the relevant station for task assignment. However, each task may need different resource type...
详细信息
In simple assembly line balancing problems, it is assumed that the resources required to perform the tasks are available at the relevant station for task assignment. However, each task may need different resource types depending on the difficulty, complexity and technical requirements of the tasks in real life. For this reason, tasks and resources belonging to these tasks must be assigned to the relevant station while balancing the line. In this study, the resource-constrained U-shaped assembly line balancing problem (U-GRCALBP) is discussed. According to the literature research, there is no study dealing with U-GRCALBP. Two different constraint programming (CP) models that define the resource constraints as "and/or" constraint types with concurrent resource types have been developed. In these models, the sum of resource usage costs and station opening cost minimization is aimed. The models are explained with an illustrative example and the efficiency of the models is tested by deriving new resource constraints on five different data set each taking into account four different cycle times and the number of two and four resource types. The number of stations obtained, the total number of resources used, total station opening and resource usage costs, and CPU time are used as performance criteria The results are compared with the traditional U-type assembly line balancing problem results. The proposed CP models give superior performance on all data sets, especially in terms of total cost. The numerical results show that both CP models are effective in solving the problem. Furthermore, some managerial implications are presented to be useful for professionals, organizations, and society.
This paper presents a framework taking advantage of the capabilities of current constraint solvers to plan the work on construction sites. It combines different constraints under a common framework to facilitate the d...
详细信息
This paper presents a framework taking advantage of the capabilities of current constraint solvers to plan the work on construction sites. It combines different constraints under a common framework to facilitate the definition of temporal relations between different tasks and provides a user-friendly web interface, which facilitates the planning of construction sites. Even though the framework uses complex mathematical models, the users do not need to know the underlying theoretical framework. Another important feature of the framework is, in contrast to usual static planning, that solutions can be dynamically adapted to take into account delays happening during the actual construction process. In order to show the applicability of the methodology, the paperspaper shows how a real construction project can be planned by using the framework.
NoC technology is composed of packet-based interconnections, where the communication resources are distributed across the network. Therefore, the optimal resource utilization is a crucial consideration for efficient a...
详细信息
NoC technology is composed of packet-based interconnections, where the communication resources are distributed across the network. Therefore, the optimal resource utilization is a crucial consideration for efficient architectural designs. This paper studies the practicality of the constraint programming (CP) models for NoC architecture designs that effectively use a regular mesh with wormhole switching and the XY routing. The complexity of the CP models is compared with the earlier Mixed Integer programming (MIP) models. Practical CP-based mapping and scheduling models are developed and results are reported on the benchmark datasets. Results indicate that mapping and scheduling problems can be solved at near optimality even under relatively shorter run-time limits as compared to those required by the MIP models.
Qualitative modelling is a technique integrating the fields of theoretical computer science, artificial intelligence and the physical and biological sciences. The aim is to be able to model the behaviour of systems wi...
详细信息
Qualitative modelling is a technique integrating the fields of theoretical computer science, artificial intelligence and the physical and biological sciences. The aim is to be able to model the behaviour of systems without estimating parameter values and fixing the exact quantitative dynamics. Traditional applications are the study of the dynamics of physical and biological systems at a higher level of abstraction than that obtained by estimation of numerical parameter values for a fixed quantitative model. Qualitative modelling has been studied and implemented to varying degrees of sophistication in Petri nets, process calculi and constraint programming. In this paper we reflect on the strengths and weaknesses of existing frameworks, we demonstrate how recent advances in constraint programming can be leveraged to produce high quality qualitative models, and we describe the advances in theory and technology that would be needed to make constraint programming the best option for scientific investigation in the broadest sense.
This contribution presents an integrated constraint programming (CP) model to tackle the problems of tool allocation, machine loading, part routing. and scheduling in a flexible manufacturing system (FMS) The formulat...
详细信息
This contribution presents an integrated constraint programming (CP) model to tackle the problems of tool allocation, machine loading, part routing. and scheduling in a flexible manufacturing system (FMS) The formulation, Which is able to take into account a variety of constraints found in industrial environments, as well as several objective functions. has been Successfully applied to the Solution of various case studies of different sizes. Though some of the problem instances have bigger sizes than the examples reported to date in literature, very good-quality Solutions were reached in quite reasonable CPU times. This good computational performance is due to two essential characteristics of the proposed model. The most significant one IS the use of two sets of two-index variables to capture manufacturing activities instead of having Just one set of four indexes. Thus, dimensionality is greatly reduced. The other relevant feature is the fact that the model relies oil an Indirect representation of tool needs by means of tool types. thus avoiding the consideration of tool copies. (C) 2009 Elsevier Ltd. All rights reserved
Various criteria have been considered in the literature for selection of optimal sensor networks. Amongst these, maximization of network reliability is an important criterion. While there are several approaches for de...
详细信息
Various criteria have been considered in the literature for selection of optimal sensor networks. Amongst these, maximization of network reliability is an important criterion. While there are several approaches for designing maximum reliability networks, uncertainty in the available sensor reliability data has not been considered in these designs. In this article we present two novel formulations that incorporate robustness to uncertainties in the reliability data. Towards this end the sensor network design problem for maximizing reliability is formulated as explicit-optimization (MINLP) problem using failure rates of sensors which have better scaling properties instead of sensor reliabilities. constraint programming (CP) has been used for solving the resulting optimization problems. Use of CP also enables easy generation of pareto front characterizing trade-offs between performance, cost and robustness for various uncertainty scenarios. The utility of the proposed approach is demonstrated on a case study taken from the literature. (C) 2008 Elsevier Ltd. All rights reserved.
The quorumcast routing problem is a generalization of multicasting which arises in many distributed applications. It consists of finding a minimum cost tree that spans the source node r and at least q out of m specifi...
详细信息
The quorumcast routing problem is a generalization of multicasting which arises in many distributed applications. It consists of finding a minimum cost tree that spans the source node r and at least q out of m specified nodes on a given undirected weighted graph. This paper proposes a complete and an incomplete approach, both based on the same constraint programming (CP) model, but with two different specific search heuristics based on shortest paths. Experimental results show the efficiency of the two proposed approaches. Our complete approach (CP model + complete search) is better than the state of the art complete algorithm and our incomplete approach (CP model + incomplete search) is better than the state of the art incomplete algorithm. Moreover, the proposed complete search is better than the standard First-Fail search in the same CP model.
This paper presents the results of a research project aiming to optimise the scheduling of activities within a research laboratory of the 'Commissariat a l'Energie Atomique et aux Energies Alternatives (CEA)&#...
详细信息
This paper presents the results of a research project aiming to optimise the scheduling of activities within a research laboratory of the 'Commissariat a l'Energie Atomique et aux Energies Alternatives (CEA)'. To tackle this problem, we decompose every activity into a set of elementary tasks to apply standard scheduling methods. We model the problem as an extended version of the Multi-Skill Project Scheduling Problem (MSPSP). As a first approach, we propose a Multi-Skill Project Scheduling Problem with penalty for preemption, along with its mixed-integer/linear programming (MILP) formulation, where the preemption is allowed applying a penalty every time an activity is interrupted. However, the previous approach does not take into account all safety constraints at the facility, and a more accurate variant of the problem is needed. We propose then to integrate the concept of partial preemption to the MSPSP. This concept, that has not been yet studied in the scientific literature, implies that only a subset of resources is released during preemption periods. The resulting MSPSP with partial preemption (MSPSP-PP) is modelled using two methodologies: MILP and constraint programming. Regarding the industrial need of having good solutions in a short time, we also present a greedy algorithm for the MSPSP-PP.
Resource-constrained project scheduling with the objective of minimizing project duration (RCPSP) is one of the most studied scheduling problems. In this paper we consider the RCPSP with general temporal constraints a...
详细信息
Resource-constrained project scheduling with the objective of minimizing project duration (RCPSP) is one of the most studied scheduling problems. In this paper we consider the RCPSP with general temporal constraints and calendar constraints. Calendar constraints make some resources unavailable on certain days in the scheduling period and force activity execution to be delayed while resources are unavailable. They arise in practice from, e.g., unavailabilities of staff during public holidays and weekends. The resulting problems are challenging optimization problems. We develop not only six different constraint programming (CP) models to tackle the problem, but also a specialized propagator for the cumulative resource constraints taking the calendar constraints into account. This propagator includes the ability to explain its inferences so it can be used in a lazy clause generation solver. We compare these models, and different search strategies on a challenging set of benchmarks using the lazy clause generation solver chuffed and IBM CPLEX CP Optimizer, respectively. We close all but 8 of the open problems of the benchmark set, extend the benchmark set by instances with up to 500 activities, and show that CP solutions are highly competitive with existing Mip models of the problem.
暂无评论