Explaining Time-Table-Edge-Finding Propagation for the Cumulative Resource Constraint
From MaRDI portal
Abstract: Cumulative resource constraints can model scarce resources in scheduling problems or a dimension in packing and cutting problems. In order to efficiently solve such problems with a constraint programming solver, it is important to have strong and fast propagators for cumulative resource constraints. One such propagator is the recently developed time-table-edge-finding propagator, which considers the current resource profile during the edge-finding propagation. Recently, lazy clause generation solvers, i.e. constraint programming solvers incorporating nogood learning, have proved to be excellent at solving scheduling and cutting problems. For such solvers, concise and accurate explanations of the reasons for propagation are essential for strong nogood learning. In this paper, we develop the first explaining version of time-table-edge-finding propagation and show preliminary results on resource-constrained project scheduling problems from various standard benchmark suites. On the standard benchmark suite PSPLib, we were able to close one open instance and to improve the lower bound of about 60% of the remaining open instances. Moreover, 6 of those instances were closed.
Recommendations
- Timetable edge finding filtering algorithm for discrete cumulative resources
- Edge finding for cumulative scheduling
- scientific article; zbMATH DE number 1822445
- Time-table disjunctive reasoning for the cumulative constraint
- scientific article; zbMATH DE number 802345
- scientific article; zbMATH DE number 708851
- Tractable approximations for temporal constraint handling
- Satisfiability tests and time-bound adjustments for cumulative scheduling problems
Cited in
(19)- Linear-time filtering algorithms for the disjunctive constraint and a quadratic filtering algorithm for the cumulative not-first not-last
- Using constraint programming for solving RCPSP/MAX-cal
- Mixed-integer linear programming and constraint programming formulations for solving resource availability cost problems
- Sharpening constraint programming approaches for bit-vector theory
- A satisfiability and workload-based exact method for the resource constrained project scheduling problem with generalized precedence constraints
- A MinCumulative resource constraint
- A polyhedral study of event-based models for the resource-constrained project scheduling problem
- Time table edge finding with energy variables
- A project scheduling problem with periodically aggregated resource-constraints
- Horizontally elastic edge-finder algorithm for cumulative resource constraint revisited
- Edge finding for cumulative scheduling
- Optimization Strategies for Resource-Constrained Project Scheduling Problems in Underground Mining
- Time-table disjunctive reasoning for the cumulative constraint
- A genetic algorithm for the resource-constrained project scheduling problem with alternative subgraphs using a Boolean satisfiability solver
- Presolving techniques and linear relaxations for cumulative scheduling
- Fifty years of research on resource-constrained project scheduling explored from different perspectives
- Improved timetable edge finder rule for cumulative constraint with profile
- Quadratic horizontally elastic not-first/not-last filtering algorithm for cumulative constraint
- Constraint propagation on GPU: a case study for the cumulative constraint
This page was built for publication: Explaining Time-Table-Edge-Finding Propagation for the Cumulative Resource Constraint
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4922915)
