The Multi-Skill Project Scheduling Problem is a variant of the well-studied Resource Constrained Project Scheduling Problem, in which the resources are assumed to be multi-skilled. Practical applications of this probl...
详细信息
ISBN:
(纸本)9783319661582;9783319661575
The Multi-Skill Project Scheduling Problem is a variant of the well-studied Resource Constrained Project Scheduling Problem, in which the resources are assumed to be multi-skilled. Practical applications of this problem occur when the resources considered are a multi-skilled workforce or multi-purpose machines. This variant introduces a set of assignment decisions between the resources and activities, further to the usual scheduling decisions. This additional layer of complexity results in the problem becoming far more difficult to solve. We investigate different constraint programming models and searches tailored for solvers with nogood learning. These models and searches are then evaluated on instances available from the literature as well as newly generated ones. Using the best performing model and search, we are able to close at least 87 open instances from the literature.
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.
The team orienteering problem with time windows (TOPTW) is a NP-hard combinatorial optimization problem. It has many real-world applications, for example, routing technicians and disaster relief routing. In the TOPTW,...
详细信息
The team orienteering problem with time windows (TOPTW) is a NP-hard combinatorial optimization problem. It has many real-world applications, for example, routing technicians and disaster relief routing. In the TOPTW, a set of locations is given. For each, the profit, service time and time window are known. A fleet of homogenous vehicles are available for visiting locations and collecting their associated profits. Each vehicle is constrained by a maximum tour duration. The problem is to plan a set of vehicle routes that begin and end at a depot, visit each location no more than once by incorporating time window constraints. The objective is to maximize the profit collected. In this study we discuss how to use constraint programming (CP) to formulate and solve TOPTW by applying interval variables, global constraints and domain filtering algorithms. We propose a CP model and two branching strategies for the TOPTW. The approach finds 119 of the best-known solutions for 304 TOPTW benchmark instances from the literature. Moreover, the proposed method finds one new best-known solution for TOPTW benchmark instances and proves the optimality of the best-known solutions for two additional instances. (C) 2017 Elsevier Ltd. All rights reserved.
Constrained Clustering allows to make the clustering task more accurate by integrating user constraints, which can be instance-level or cluster-level constraints. Few works consider the integration of different kinds ...
详细信息
Constrained Clustering allows to make the clustering task more accurate by integrating user constraints, which can be instance-level or cluster-level constraints. Few works consider the integration of different kinds of constraints, they are usually based on declarative frameworks and they are often exact methods, which either enumerate all the solutions satisfying the user constraints, or find a global optimum when an optimization criterion is specified. In a previous work, we have proposed a model for Constrained Clustering based on a constraint programming framework. It is declarative, allowing a user to integrate user constraints and to choose an optimization criterion among several ones. In this article we present a new and substantially improved model for Constrained Clustering, still based on a constraint programming framework. It differs from our earlier model in the way partitions are represented by means of variables and constraints. It is also more flexible since the number of clusters does not need to be set beforehand;only a lower and an upper bound on the number of clusters have to be provided. In order to make the model-based approach more efficient, we propose new global optimization constraints with dedicated filtering algorithms. We show that such a framework can easily be embedded in a more general process and we illustrate this on the problem of finding the optimal Pareto front of a bi-criterion constrained clustering task. We compare our approach with existing exact approaches, based either on a branch-and-bound approach or on graph coloring on twelve datasets. Experiments show that the model outperforms exact approaches in most cases. (C) 2015 Elsevier B.V. All rights reserved.
constraint programming (CP) has proven to be an effective platform for constraint based sequence mining. Previous work has focused on standard frequent sequence mining, as well as frequent sequence mining with a maxim...
详细信息
constraint programming (CP) has proven to be an effective platform for constraint based sequence mining. Previous work has focused on standard frequent sequence mining, as well as frequent sequence mining with a maximum 'gap' between two matching events in a sequence. The main challenge in the latter is that this constraint can not be imposed independently of the omnipresent frequency constraint. Indeed, the gap constraint changes whether a subsequence is included in a sequence, and hence its frequency. In this work, we go beyond that and investigate the integration of timed events and constraining the minimum/maximum gap as well as minimum/maximum span. The latter constrains the allowed time between the first and last matching event of a pattern. We show how the three are interrelated, and what the required changes to the frequency constraint are. Key in our approach is the concept of an extension window defined by gap/span and we develop techniques to avoid scanning the sequences needlessly, as well as using a backtracking-aware data structure. Experiments demonstrate that the proposed approach outperforms both specialized and CP-based approaches in almost all cases and that the advantage increases as the minimum frequency threshold decreases. This paper is an extension of the original manuscript presented at CPAIOR'17 [5].
constraint programming is used for a variety of real-world optimization problems, such as planning, scheduling, and resource allocation problems, all while we continuously gather vast amounts of data about these probl...
详细信息
constraint programming is used for a variety of real-world optimization problems, such as planning, scheduling, and resource allocation problems, all while we continuously gather vast amounts of data about these problems. Current constraint programming software doesn't exploit such data to update schedules, resources, and plans. The authors propose a new framework that they call the inductive constraint programming loop. In this approach, data is gathered and analyzed systematically to dynamically revise and adapt constraints and optimization criteria. Inductive constraint programming aims to bridge the gap between the areas of data mining and machine learning on one hand and constraint programming on the other.
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.
Because of the bottlenecking operations in a complex coal rail system, millions of dollars are costed by mining companies. To handle this issue, this paper investigates a real-world coal rail system and aims to optimi...
详细信息
Because of the bottlenecking operations in a complex coal rail system, millions of dollars are costed by mining companies. To handle this issue, this paper investigates a real-world coal rail system and aims to optimise the coal railing operations under constraints of limited resources (e.g., limited number of locomotives and wagons). In the literature, most studies considered the train scheduling problem on a single-track railway network to be strongly NP-hard and thus developed metaheuristics as the main solution methods. In this paper, a new mathematical programming model is formulated and coded by optimization programming language based on a constraint programming (CP) approach. A new depth-first-search technique is developed and embedded inside the CP model to obtain the optimised coal railing timetable efficiently. Computational experiments demonstrate that high-quality solutions are obtainable in industry-scale applications. To provide insightful decisions, sensitivity analysis is conducted in terms of different scenarios and specific criteria.
Sudoku is not only a popular puzzle but also an interesting and challenging constraint satisfaction problem. Therefore, automatic solving methods have been the subject of several publications in the past two decades. ...
详细信息
Sudoku is not only a popular puzzle but also an interesting and challenging constraint satisfaction problem. Therefore, automatic solving methods have been the subject of several publications in the past two decades. Although current methods provide good solutions for small-sized puzzles, larger instances remain challenging. This article introduces a new local search technique based on the min-conflicts heuristic for Sudoku. Furthermore, the authors propose an innovative hybrid search technique that exploits constraint programming as a perturbation technique within the iterated local search framework. They experimentally evaluate their methods on challenging benchmarks for Sudoku and report improvements over state-of-the-art solutions. To show the generalizability of the proposed approach, they also applied their method on another challenging scheduling problem. The results show that the proposed method is also robust in another problem domain.
The Nurse Rostering Problem can be defined as assigning a series of shift sequences (schedules) to several nurses over a planning horizon according to some limitations and preferences. The inherent benefits of generat...
详细信息
The Nurse Rostering Problem can be defined as assigning a series of shift sequences (schedules) to several nurses over a planning horizon according to some limitations and preferences. The inherent benefits of generating higher-quality schedules are a reduction in outsourcing costs and an increase in job satisfaction of employees. In this paper, we present a hybrid algorithm, which combines Integer programming and constraint programming to efficiently solve the highly-constrained Nurse Rostering Problem. We exploit the strength of IP in obtaining lower-bounds and finding an optimal solution with the capability of CP in finding feasible solutions in a co-operative manner. To improve the performance of the algorithm, and therefore, to obtain high-quality solutions as well as strong lower-bounds for a relatively short time, we apply some innovative ways to extract useful information such as the computational difficulty of instances and constraints to adaptively set the search parameters. We test our algorithm using two different datasets consisting of various problem instances, and report competitive results benchmarked with the state-of-the-art algorithms from the recent literature as well as standard IP and CP solvers, showing that the proposed algorithm is able to solve a wide variety of instances effectively. (C) 2017 Elsevier Ltd. All rights reserved.
暂无评论