EURO-Online login
- New to EURO? Create an account
- I forgot my username and/or my password.
- Help with cookies
(important for IE8 users)
4250. Improved Results on RCPSP Using Failure-Directed Search in Constraint Programming
Invited abstract in session MD-60: RCPSP and extensions, stream Project Management and Scheduling.
Monday, 14:30-16:00Room: S09 (building: 101)
Authors (first author is the speaker)
| 1. | Zdenek Hanzalek
|
| CTU Prague | |
| 2. | Vilem Heinz
|
| Czech Technical University in Prague | |
| 3. | Petr Vilím
|
| ScheduleOpt |
Abstract
The Failure-Directed Search (FDS) was introduced as a state-of-the-art algorithm for proving optimality and lower bounds for scheduling problems such as Job Shop Scheduling Problem (JSSP) and Resource-Constrained Project Scheduling Problems (RCPSP). We re-implemented the FDS algorithm in a new CP solver called OptalCP to understand its notable performance better and use these insights to improve its performance further. Despite its genericity and simplicity, FDS proved optimality or solved optimally numerous scheduling instances that were open for decades. In this paper, we investigate the properties of FDS. Experimental results show the improved FDS is 1.7x faster on JSSP and 2.1x faster on RCPSP benchmarks and is 3.5x times faster on JSSP and 2.1x times faster on RCPSP than the state-of-the-art FDS algorithm in IBM CP Optimizer 22.1. The new FDS improved existing lower bounds of 66 out of 78 and 43 out of 78 randomly picked JSSP and RCPSP instances, respectively.
Keywords
- Scheduling
- Machine Learning
- Algorithms
Status: accepted
Back to the list of papers