This paper deals with the Generalised Workforce Scheduling and Routing Problem (GWSRP) where 9 temporal constraints ensuring visit dependencies are all together taken into account and where customer and worker's q...
详细信息
This paper deals with the Generalised Workforce Scheduling and Routing Problem (GWSRP) where 9 temporal constraints ensuring visit dependencies are all together taken into account and where customer and worker's quality of service are taken into consideration. A constraint-programming based Decomposition Method (CPDM) is proposed, firstly based on a relaxation of coordination constraints and a column generation, and secondly with an iterative insertion of coordination constraint by constraint programming solver. Numerical experiments are achieved on huge instances derived from WSRP benchmark instances with up to 177 customers, 59 vehicles and coordination constraints. The CPDM is able to find nearly optimal solution for medium-size instances and find high-quality solution for huge-size instances whereas CPLEX solver applied to a mixed integer linear model is not able to give a solution in this case.
We outline the development and performance of heuristic approaches to obtain prioritized load planning solutions for the embarkation of cargo onto the deck of an amphibious ship. The heuristic techniques are underpinn...
详细信息
We outline the development and performance of heuristic approaches to obtain prioritized load planning solutions for the embarkation of cargo onto the deck of an amphibious ship. The heuristic techniques are underpinned by a constraint programming paradigm and have been implemented in a Java-based software package called COmPacT (constraint Optimization Packing Tool). COmPacT utilizes the modeling and solver libraries of the IBM ILOG CPLEX Optimization Studio. For the purposes of mathematical modeling, the embarkation planning problem is akin to packing a set of rectangular items onto a larger rectangular space (the deck), which could contain obstacles and may be subject to mass balance constraints. The modeling and algorithmic approaches are outlined in connection to the software development of COmPacT. Finally, we demonstrate how COmPacT may be used in conjunction with a planner's knowledge and expertise to enable iterative packing techniques, thereby combining the strengths of both automated and manual methods.
Explaining opaque Machine Learning (ML) models is an increasingly relevant problem. Current explanation in AI (XAI) methods suffer several shortcomings, among others an insufficient incorporation of background knowled...
详细信息
ISBN:
(纸本)9783031436185;9783031436192
Explaining opaque Machine Learning (ML) models is an increasingly relevant problem. Current explanation in AI (XAI) methods suffer several shortcomings, among others an insufficient incorporation of background knowledge, and a lack of abstraction and interactivity with the user. We propose reasonx, an explanation method based on constraint Logic programming (CLP). reasonx can provide declarative, interactive explanations for decision trees, which can be the ML models under analysis or global/local surrogate models of any black-box model. Users can express background or common sense knowledge using linear constraints and MILP optimization over features of factual and contrastive instances, and interact with the answer constraints at different levels of abstraction through constraint projection. We present here the architecture of reasonx, which consists of a Python layer, closer to the user, and a CLP layer. reasonx's core execution engine is a Prolog meta-program with declarative semantics in terms of logic theories.
In recent years, the multi-manned assembly line has become popular since the large-sized products allow more than one operator working simultaneously on the same product in a workstation. This line usually occurs in l...
详细信息
In recent years, the multi-manned assembly line has become popular since the large-sized products allow more than one operator working simultaneously on the same product in a workstation. This line usually occurs in large-size products such as cars, buses, trucks, and so on. The multi-manned assembly line offers several advantages, such as fewer number of workers/workstation and less cycle time to improve the performance of the system. However, it has been analyzed by a few papers in literature due to being a relatively new and complex problem. The current study aims to develop an efficient exact solution approach, constraint programming, to solve from small to large-size problems by minimizing the cycle time as a primary objective and the total number of workers as a secondary objective. First, two mixed-integer linear programming (MILP) models are proposed based on previous studies to solve the small test cases of the problem optimally. However, the models are not capable of solving the large-size test instances. Therefore, a constraint programming (CP) model is formulated to address both small and large-size data sets. The results of the CP model are compared with two MILP models and two heuristic algorithms available in the literature. The computational results indicate that the CP model discovers optimal solutions, approximately 90% of all the instances, and small optimality gaps in the remaining instances. It is useful to highlight that the CP model is highly concise and solved by a black-box, commercial solver. (c) 2020 Elsevier Ltd. All rights reserved.
Compromising productivity in exchange for energy saving does not appeal to highly capitalized manufacturing industries. However, we might be able to maintain the same productivity while significantly reducing energy c...
详细信息
Compromising productivity in exchange for energy saving does not appeal to highly capitalized manufacturing industries. However, we might be able to maintain the same productivity while significantly reducing energy consumption. This paper addresses a flexible job shop scheduling problem with a shutdown (on/off) strategy aiming to minimize makespan and total energy consumption. First, an alternative mixed integer linear programming model is proposed. Second, a novel constraint programming is proposed. Third, practical operational scenarios are compared. Finally, we provide benchmarking instances, CPLEX codes, and genetic algorithm codes, in order to promote related research, thus expediting the adoption of energy-efficient scheduling in manufacturing facilities. The computational study demonstrates that (1) the proposed models significantly outperform other benchmark models and (2) we can maintain maximum productivity while significantly reducing energy consumption by 14.85% (w/o shutdown) and 15.23% (w/shutdown) on average.
We present a novel approach for automatic apartment layout generation. Given a polygonal apartment envelope and a list of rooms with associated area, our so-called Optimizer algorithm generates several floor plans aim...
详细信息
We present a novel approach for automatic apartment layout generation. Given a polygonal apartment envelope and a list of rooms with associated area, our so-called Optimizer algorithm generates several floor plans aiming at both architectural and functional constraints. To do so, Optimizer discretizes the floor space into a grid according to architectural constraints and reduces the problem to a cell assignment which is solved through a coupled constraint programming genetic optimization approach. Obtained results demonstrate the feasibility of our approach, customized plans are architecturally and functionally valid, they are mostly generated in about 1 min.
Integration of process planning and scheduling (IPPS) is to carry out both functions simultaneously. This paper provides a graph-based constraint programming (GCP) approach to solve the type-2 IPPS problem that takes ...
详细信息
Integration of process planning and scheduling (IPPS) is to carry out both functions simultaneously. This paper provides a graph-based constraint programming (GCP) approach to solve the type-2 IPPS problem that takes AND/OR graphs as input. The proposed GCP approach is implemented based on the IBM ILOG CP Optimizer. AND/OR graph is tailored to cope with IPPS instances. Directed arcs define both precedence and presence relationships. The or-link, a set of mutually-exclusive operations, is defined to represent alternative process routes. Interval variables and scheduling-oriented constraints are adopted to project the IPPS-specific AND/OR graph to a concise CP model with which minimizing makespan is incorporated as the objective. The GCP approach is tested on a set of benchmark problems. Experimental results show that the proposed approach outperforms compared algorithms on major IPPS instances. (C) 2021 Elsevier Ltd. All rights reserved.
Requirements Engineering (RE) covers not only the capture and structuring of various properties the system should achieve but also the identification of high-level choices on how to achieve such goals or to avoid rela...
详细信息
ISBN:
(纸本)9781728183589
Requirements Engineering (RE) covers not only the capture and structuring of various properties the system should achieve but also the identification of high-level choices on how to achieve such goals or to avoid related obstacles. Generic RE frameworks support simple formalisation of alternatives using AND/OR refinements while more specialised fields such as safety and security engineering have richer analysis capabilities respectively through fault and attack trees. In this paper, we review the various constructs proposed in those domains and state their semantics at RE level to support safety and security co-engineering. As a supplementary step, we propose a mapping on the semantics provided by constraint programming in order to search for optimal configurations in the design space of a RE model. We consider multiple objectives stated as non-functional requirements and formalised using quantified attributes over goal models. Our work is validated on the complex design of an oil pipe system mixing safety and security critical properties.
We explore how planning for near optimal behaviors of mixed discrete-continuous systems can be done by deductive reasoning. For reasoning to be efficient, it must be properly controlled. It is surprising and mathemati...
详细信息
The traditional resource-constrained project scheduling problem makes the amounts of resource input fixed and ignores the joint effect of multiple time constraints, which may lead to the failure of traditional algorit...
详细信息
The traditional resource-constrained project scheduling problem makes the amounts of resource input fixed and ignores the joint effect of multiple time constraints, which may lead to the failure of traditional algorithms. This paper introduces a new practical problem called the resource input optimization problem with combined time constraints (RIOP/CTC), which studies the influence of resource input schemes. The new problem combines three types of time constraints, including precedence relations, resource calendars, and interruptability for the first time, which makes it closer to the actual scheduling problem. We propose a new network diagram called node network diagram and develop an optimization model based on constraint programming (CP) and the technique for order preference by similarity to the ideal solution (TOPSIS). A three-step guideline and an actual project case are provided for schedulers to help them better use the model to solve RIOP/CTC, which also proves the validity of the model. Computational experiments are carried out to show that the CP optimizer is superior to the three common metaheuristic algorithms in solving quality and speed and can provide a near-optimum solution for large-scale scheduling problems in an acceptable time. The proposed model contributes to improving the practical decision system to support the formulation of real-life project resource input schemes, scheduling plans, and employee work plans.
暂无评论