The use of techniques and system of constraint programming enables the implementation of precise, flexible, efficient, and extensible scheduling systems. It has been identified as a strategic direction and dominant fo...
详细信息
The use of techniques and system of constraint programming enables the implementation of precise, flexible, efficient, and extensible scheduling systems. It has been identified as a strategic direction and dominant form for the application into planning and scheduling of industrial production. This paper systematically introduces the constraint modeling and solving technology for production scheduling problems, including various real-world industrial applications based on the Chip system of Cosytec Company. We trend of some concrete technology, such as modeling, search, constraint propagation, consistency, and optimization of constraint programming for scheduling problems. As a result of the application analysis, a generic application framework for real-life scheduling based on commercial constraint propagation (CP) systems is proposed.
This paper presents constraint programming-based solution approaches for the three-dimensional loading capacitated vehicle routing problem (3l-CVRP) that consists of vehicle routing and three-dimensional loading probl...
详细信息
This paper presents constraint programming-based solution approaches for the three-dimensional loading capacitated vehicle routing problem (3l-CVRP) that consists of vehicle routing and three-dimensional loading problems in distribution logistics. Despite the practical benefits in the logistics world, the 3l-CVRP has not been extensively studied in the literature for its high combinatorial complexity. Therefore, we developed integrated and decomposed constraint programming-based solution methods in this study. The decomposed models outperformed the mixed-integer programming model proposed earlier in the literature for small-size problems. Furthermore, we solved the well-known benchmark problems with a decomposed model using constraint programming for the vehicle routing part of the problem and an evolutionary algorithm for the loading part. The computational study results show that the best-known results are improved in 36 of 93 problems.
constraint programming is well suited for the computational modeling of music theories and composition: its declarative and modular approach shares similarities with the way music theory is traditionally expressed, na...
详细信息
constraint programming is well suited for the computational modeling of music theories and composition: its declarative and modular approach shares similarities with the way music theory is traditionally expressed, namely by a set of rules which describe the intended result. Various music theory disciplines have been modeled, including counterpoint, harmony, rhythm, form, and instrumentation. Because modeling music theories "from scratch" is a complex task, generic music constraint programming systems have been proposed that predefine the required building blocks for modeling a range of music theories. After introducing the field and its problems in general, this survey compares these generic systems according to a number of criteria such as the range of music theories these systems support.
In this paper we propose a general integration scheme for a Multi-Criteria Decision Making model of the Multi-Attribute Utility Theory in constraint programming. We introduce the Choquet integral as a general aggregat...
详细信息
In this paper we propose a general integration scheme for a Multi-Criteria Decision Making model of the Multi-Attribute Utility Theory in constraint programming. We introduce the Choquet integral as a general aggregation function for multi-criteria optimization problems and define the Choquet global constraint that propagates this function during the Branch-and-Bound search. Finally the benefits of the propagation of the Emphasis Choquet constraint are evaluated on the examination timetabling problem.
Today many companies face the challenge of matching highly-skilled professionals to high-end positions in large organizations and human deployment agencies. Unlike traditional Workforce Management problems such as shi...
详细信息
ISBN:
(纸本)9781424411177
Today many companies face the challenge of matching highly-skilled professionals to high-end positions in large organizations and human deployment agencies. Unlike traditional Workforce Management problems such as shift scheduling, highly-skilled employees are professionally distinguishable from each other and hence non-interchangeable. Our work specifically focuses on the services industry, where much of the revenue comes from the assignment of highly professional workers. Here, non-accurate matches may result in significant monetary losses and other negative effects. We deal with very large pools of both positions and employees, where optimal decisions should be made rapidly in a dynamic environment. Since traditional Operations Research (OR) methods fail to answer this problem, we employ constraint programming (CP), a subfield of Artificial Intelligence with strong algorithmic foundations. Our CP model builds on new constraint propagators designed for this problem (but applicable elsewhere), as well as on information retrieval methods used for analyzing the complex text describing high-end professionals and positions. Optimatch, which is based on this technology and is being used by IBM services organizations, provides strong experimental results.
Alternative splicing is a key process in post-transcriptional regulation, by which different mature RNA can be obtained from the same premessenger RNA. The resulting combinatorial complexity contributes to biological ...
详细信息
Alternative splicing is a key process in post-transcriptional regulation, by which different mature RNA can be obtained from the same premessenger RNA. The resulting combinatorial complexity contributes to biological diversity, especially in the case of the human immunodeficiency virus HIV-1. Using a constraint programming approach, we develop a model of the alternative splicing regulation in HIV-1. Our model integrates different scales (single site vs. multiple sites), and thus allows us to exploit several types of experimental data available to us. (C) 2004 Elsevier B.V. All rights reserved.
Logistic planning and programming of construction machinery involves complex sets of objectives and constraints;therefore traditional approaches typically result in a large monolithic model that is difficult to solve,...
详细信息
ISBN:
(纸本)1424403170
Logistic planning and programming of construction machinery involves complex sets of objectives and constraints;therefore traditional approaches typically result in a large monolithic model that is difficult to solve, understand, and maintain. In order, to tackle large, particularly combinatorial, problems in logistic support for construction machinery, we design a constraint programming system, namely DISPDESK, which comprises a specification generator and its underlying domain-specific architecture, an algorithm library and its selector, a pre-defined solution library and a problem solver. The system features separation of concerns in specifications, little requirements for programming skills, domain-specific optimization, and semi-automatic generation of high-performance and reliable problem solvers.
With increasing implementation of off-site prefabrication and modular construction technologies, the complexity of material supply chain management on construction projects has grown substantially. However, research o...
详细信息
With increasing implementation of off-site prefabrication and modular construction technologies, the complexity of material supply chain management on construction projects has grown substantially. However, research on construction scheduling has yet to take dynamic material logistics as an explicit constraint in analytically deriving construction schedules and addressing impacts of uncertainties in material supply on project budget. This study proposes a two-step analytical approach to tackle the identified problem. First, a constraint programming-based scheduling optimization model is developed to derive project schedules subject to variable material delivery times and finite crew resource availability. The second step is to take advantage of the valid optimization model for evaluating the impact of different input settings of material logistics on project budget. An example project adapted from the literature is used to illustrate the effectiveness of the proposed optimization model in coping with variable material delivery times. Based on the same case, the delivery date of a particular material is singled out as the risk factor of interest in order to derive the complex relationship between material delivery date and total project cost. In addition, a case study based on a bridge girder fabrication project is presented to demonstrate the applicability of the proposed optimization model on projects of practical size. In conclusion, this study adds to the body of knowledge by developing an analytical methodology that factors material supply constraints into the resource-constrained scheduling optimization model so as to analyze the impact of uncertainties in material deliveries on project budget.
Motivation: Predicting the ground state of biopolymers is a notoriously hard problem in biocomputing, Model systems, such as lattice proteins, are simple tools and valuable to rest and improve new methods. Best known ...
详细信息
Motivation: Predicting the ground state of biopolymers is a notoriously hard problem in biocomputing, Model systems, such as lattice proteins, are simple tools and valuable to rest and improve new methods. Best known are models with sequences composted from a binary (hydrophobic and polar) alphabet. The major drawback is the degeneracy, i.e. the number of different ground state conformations. Results: We shaw how recently developed constraint programming techniques can be used to solve the structure prediction problem efficiently for a higher order alphabet. To our knowledge it is the first report of on exact and computationally feasible solution to model proteins of length lip to 36 and without resorting to maximally compact states, We further show that degeneracy is reduced by more than one order of magnitude and that ground state conformations are not necessarily compact. Therefore, more realistic protein simulations become feasible with our model.
This paper examines scheduling problem denoted as P|(seq), ser|C(max )in Graham's notation;in other words, scheduling of tasks on parallel identical machines (P) with sequence-dependent setups (seq) each performed...
详细信息
This paper examines scheduling problem denoted as P|(seq), ser|C(max )in Graham's notation;in other words, scheduling of tasks on parallel identical machines (P) with sequence-dependent setups (seq) each performed by one of the available servers (ser). The goal is to minimize the makespan (C-max). We propose a constraint programming (CP) model for finding the optimal solution and constructive heuristics suitable for large problem instances. These heuristics are also used to provide a feasible starting solution to the proposed CP model, significantly improving its efficiency. This combined approach constructs solutions for benchmark instances of up to 20 machines and 500 tasks in 10 s, with makespans 3 % to 115 % greater than the calculated lower bounds with a 5% average. The extensive experimental comparison also shows that our proposed approaches outperform the existing ones.
暂无评论