The problem studied is the selection of slabs from a slab yard for the hot rolling program in a steel company, with the objective of minimizing and balancing the incurred workload on the slab yard. A local search algo...
详细信息
The problem studied is the selection of slabs from a slab yard for the hot rolling program in a steel company, with the objective of minimizing and balancing the incurred workload on the slab yard. A local search algorithm in a constraint programming environment is developed. This local search has two iterative phases: descent into and escape from local optima. Computational experiments show savings of 40 percent and more compared to the currently used greedy search.
Two kinds of intertwined decisions: the routing decisions, which determine the set of sequences of stations visited by each tugger train’s route, and the scheduling decisions, which plan congestion-free movements of ...
详细信息
Two kinds of intertwined decisions: the routing decisions, which determine the set of sequences of stations visited by each tugger train’s route, and the scheduling decisions, which plan congestion-free movements of tugger train fleets, are considered. The problem under study can be seen as extension of the pick-up and delivery problem with time windows in which different profiles of separately executed delivery and pick-up operations are assumed. The NP-hard character of the problem considered follows from its roots derived from the vehicle routing and the deadlock-avoidance problems. In this regard, a constraint programming paradigm allowing the further integration of multi-period, multi-trip and multi-commodity flows with various customers’ demands as well as distribution network topology constraints is applied. Consequently, a recursive formulation of a well-known constraint satisfaction problem is proposed. The computer experiments provided illustrate the possibility of using the approach presented in systems of real-life scale.
This paper presents an integrated approach for the preliminary design of complex systems and for the generation of correct by construction system architectures with respect to the requirements to be satisfied. These r...
详细信息
This paper presents an integrated approach for the preliminary design of complex systems and for the generation of correct by construction system architectures with respect to the requirements to be satisfied. These requirements can be functional and/or non-functional (safety, sustainability ...). The approach presented is complementary to the usual approaches based on system analysis, performance evaluation and optimization. It focuses on the simultaneous consideration of functional and non-functional requirements such as environmental impact. The originality of the approach consists in modeling the design problem rather than the system and then solving the problem in such a way as to obtain necessarily admissible solutions. The DEPS (Design Problem Specification) language is used for modeling the problem. DEPS models are generic and reusable. The DEPS Studio environment is used to edit, compile, debug and solve problems expressed in DEPS. It integrates a mixed constraint programming solver. A case-study of a design of a mechanical power transmission system under functional and environmental requirements illustrates the approach. The DEPS modeling, the problem solving and the results obtained are detailed.
Abstract For a Carbon-ion therapy center in the design phase, patient recruitment is one of the most important challenges that involve healthcare laws and regulations, financial management, and technical concepts. Num...
详细信息
Abstract For a Carbon-ion therapy center in the design phase, patient recruitment is one of the most important challenges that involve healthcare laws and regulations, financial management, and technical concepts. Numerous constraints related to tumor treatment protocols, priority assignment, decision making and capacity analysis should be taken into account. The main objective of this research work is to identify better admission criteria that drive improved performance and optimized efficiency in the Carbon-ion therapy center. A decision support tool has been developed through constraint programming to optimize patient recruitment, which particularly belongs to online scheduling problems. Being given periodically a list of admission demands characterized by latest beginning day, treatment priority, and number of therapy sessions with their durations, this tool is capable to generate an optimized admission list according to capacity schedule and aiming at increasing economic efficiency. The generated admission list is useful not only for planning treatment activities in the center, but also for regulating both domestic and international demands.
constraint Satisfaction Problems allow one to expressively model problems. On the other hand, propositional satisfiability problem (SAT) solvers can handle huge SAT instances. We thus present a technique to expressive...
详细信息
constraint Satisfaction Problems allow one to expressively model problems. On the other hand, propositional satisfiability problem (SAT) solvers can handle huge SAT instances. We thus present a technique to expressively model set constraint problems and to encode them automatically into SAT instances. Our technique is expressive and less error-prone. We apply it to the Social Golfer Problem and to symmetry breaking of the problem.
This paper addresses the Single Container Loading Problem. We present an exact approach that considers the resolution of integer linear programming and constraint programming models iteratively. A linear relaxation of...
详细信息
This paper addresses the Single Container Loading Problem. We present an exact approach that considers the resolution of integer linear programming and constraint programming models iteratively. A linear relaxation of the problem based on packing in planes is proposed. Moreover, a comprehensive set of mathematical formulations for twelve practical constraints that arise in this problem are discussed. These constraints include complete shipment, conflicting items, priorities, weight limit, cargo stability, load-bearing, multi-drop, load-balancing, manual loading, grouping, separation, and multiple orientations. Extensive computational experiments are carried out on instances from the literature to show the performance of the proposed approach and state how each practical constraint affects the container?s occupancy, the approach runtime, and the number of packing patterns evaluated. In general, the approach could optimally solve instances with around ten items types and a total of 110 items, besides obtaining the optimal solution for more than 70% of all instances. ? 2020 Elsevier Ltd. All rights reserved.
In this work, we introduce a generalized flexible job-shop scheduling problem in which, besides the classical constraints of the flexible job shop scheduling problem other hard constraints such as machine capacity, ti...
详细信息
In this work, we introduce a generalized flexible job-shop scheduling problem in which, besides the classical constraints of the flexible job shop scheduling problem other hard constraints such as machine capacity, time lags, holding times, and sequence-dependent setup times are taken into account. This problem is inspired by a real situation observed in a seamless rolled ring manufacturer. We propose a mixed integer linear programming (MILP) and a constraint programming (CP) models to represent the problem. Additionally, we develop a metaheuristic based on a Greedy Randomized Adaptive Search Procedure (GRASP) able to tackle efficiently large instances of the problem. The results show that CP outperforms the MILP and the proposed GRASP outperforms the CP when solving instances with more than 100 jobs.
As an essential problem in construction management, the resource-constrained project scheduling problem (RCPSP) has been studied for decades;however, an integrated information model that fully supports the RCPSP solvi...
详细信息
As an essential problem in construction management, the resource-constrained project scheduling problem (RCPSP) has been studied for decades;however, an integrated information model that fully supports the RCPSP solving process is still lacking. Though building information modeling (BIM) was proposed to meet the data requirements in the building life cycle, some scheduling and resource information are not considered in information transfers between the information model and the RCPSP mathematical model. This paper presents an integrated approach that enables fluent data flow from the information model to the RCPSP model for construction scheduling. Within this approach, a work package-based information model is proposed to capture all the required data of the RCPSP. Then, a semiautomatic method that integrates multisource data is introduced to form the proposed information model, and an adaptive data transmission method is used to support a designed multimode resource-constrained project scheduling problem (MRCPSP) model. The models and approaches are validated using the data of an actual project, demonstrating the feasibility and efficiency. This study contributes a novel integrated approach to formalizing a construction information model using a semiautomatic data integration approach, covering the information requirement and enables fluent data flow in the RCPSP solving process. Meanwhile, the work package-based information model is a successful attempt to introduce previously-gained knowledge into automatic schedule generation processes. Future work, such as extending the information model, creating new methods for RCPSP model generation, and data analytics, can bring new opportunities to apply more complex and intelligent methods in project scheduling and construction management.
The problem of gene regulatory network inference is a major concern of systems biology. In recent years, a novel methodology has gained momentum, called community network approach. Community networks integrate predict...
详细信息
The problem of gene regulatory network inference is a major concern of systems biology. In recent years, a novel methodology has gained momentum, called community network approach. Community networks integrate predictions from individual methods in a "metapredictor," in order to compose the advantages of different methods and soften individual limitations. This article proposes a novel methodology to integrate prediction ensembles using constraint programming, a declarative modeling and problem solving paradigm. constraint programming naturally allows the modeling of dependencies among components of the problem as constraints, facilitating the integration and use of different forms of knowledge. The new paradigm, referred to as constrained community network, uses constraints to capture properties of the regulatory networks (e.g., topological properties) and to guide the integration of knowledge derived from different families of network predictions. The article experimentally shows the potential of this approach: The addition of biological constraints can offer significant improvements in prediction accuracy.
This paper aims at providing a fast near-optimum solution to the multimode resource-constrained project scheduling problem (MRCPSP) in large-scale projects, with and without resource-leveling constraints. The MRCPSP p...
详细信息
This paper aims at providing a fast near-optimum solution to the multimode resource-constrained project scheduling problem (MRCPSP) in large-scale projects, with and without resource-leveling constraints. The MRCPSP problem is known to be nondeterministic polynomial-time hard (NP-hard) and has been solved using various exact, heuristic, and metaheuristic procedures. In this paper, constraint programming (CP) is used as an advanced mathematical optimization technique that suits scheduling problems. The IBM ILOG modeling software and its CPLEX-CP solver engine have been used to develop a CP optimization model for the MRCPSP problem. Unlike many metaheuristic methods in literature, the CP model is fast and provides a near-optimum solution to the MRCPSP for projects with hundreds of activities within minutes. The paper compares the CP results with two case studies from the literature to prove the practicality and usefulness of the CP approach to both researchers and practitioners. One case study was used as the basis for creating larger projects with up to 2,000 activities. The results reported in this paper can be used as a benchmark for other researchers to compare and improve. This research contributes to developing a practical decision support system for resolving real-life constraints in projects. (C) 2014 American Society of Civil Engineers.
暂无评论