Producer Consumer
Producer consumer constraints (balance constraints) can be used to solve RCPSP and RCPSP MAX problems.
We report the best way to do this in a learning solver in
-
A. Schutt, P.J. Stuckey.
Explaining Producer/Consumer Constraints.
[PDF]
We generated larger benchmarks of size 200 for the ubo examples. They are available
RCPSP MAX
RCPSP with maximal time lags extends RCPSP by allowing arbitrary precedence constraints between tasks.
The problem becomes substantially harder than RCPSP, since now even finding a feasible solution is NP hard.
We have constructed a lazy clause generation solution to RCPSP MAX
that is state of the art. It matches the best known results
for all instances we have tried with 200 tasks or less except 3,
and improves the best known results for all
unclosed instances with less than 200 tasks except 7.
This is reported in:
-
A. Schutt, T. Feydy, P.J. Stuckey, and M. G. Wallace.
Solving the Resource-constrained Scheduling Problem with generalized Precedences by Lazy Clause Generation.
[PDF]
A table of all the results is available:
RCPSP
Cumulative resources are part of many real-world scheduling problems. A
resource can represent not only a machine which is able to run multiple
tasks in parallel but also entities such as: electricity, water,
consumables or even human skills. Those resources arises for example in
the resource-constrained project scheduling problem RCPSP, their
variants, their extensions and their specialisations. An RCPSP consists
of tasks (also called activities ) consuming one or more resources,
precedences between some tasks, and resources. In this paper we
restrict ourselves to case of non-preemptive tasks and renewable
resources with a constant resource capacity over the planning horizon.
A solution is a schedule of all tasks so that all precedences and
resource constraints are satisfied. RCPSP is an NP-hard problem.
New Results
Using a new cumulative propagator Time Table with Edge Finding originally by Vilim and extended by us to include explanations we have been able to close a number of instances and improve lower bounds on many more.
These new results are reported in
-
A. Schutt, T. Feydy, and P.J. Stuckey.
Explaining Time-Table-Edge-Finding Propagation for the Cumulative Resource Constraint
[PDF]
A table of all the results is available:
Files without "lb" are calculated using branch and bound search.
Files including "lb" are calculated by destructive lower bounding, increasing the bound from the best known lower bound by one until the time limit is reached.
where a green table entry indicates that the corresponding method either closes the corresponding instances for the first time or improves the best known lower or upper bound.
Old Results
This is reported in:
-
A. Schutt, T. Feydy, P.J. Stuckey, and M. G. Wallace. Why cumulative decomposition
is not as bad as it sounds. In I. Gent, editor, Proceedings of the 15th International
Conference on Principles and Practice of Constraint Programming, volume 5732 of
LNCS, 746-761. Springer-Verlag, 2009.
LNCS,
[PDF]
[PDF] is a full version of a paper
to appear at CP2009, with an appendix containing the new results.
Detailed results for the benchmarks from the PSPLib are presented in several tables where a green table entry indicates that the corresponding method either closes the corresponding instances for the first time or improves the best known lower or upper bound.
New results are reported in:
-
A. Schutt, T. Feydy, P.J. Stuckey, and M. G. Wallace. Explaining the cumulative propagator. to appear in Constraints.
[PDF]
Detailed results for the benchmarks from the PSPLib are presented in several tables where a green table entry indicates that the corresponding method either closes the corresponding instances for the first time or improves the best known lower or upper bound.