Research map / Learning theory and algorithms / Submodular and game algorithms
Using Approximation within Constraint Programming to Solve the Parallel Machine Scheduling Problem with Additional Unit Resources
Arthur Godet, Xavier Lorca, Emmanuel Hebrard, Gilles Simonin
Read the paperCheck your idea against 137,217 papers
AI-extracted. The measured effects below were read by AI from the paper's full text (no summary yet). Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| add the approximation-based cutting rule (APPROXCSTR) to the Order model (ablation) | Order · all 234 instances | #proofs: 172 / 234 -> 174 / 234 | Improved |
| add the approximation-based cutting rule (APPROXCSTR) to the Order model (ablation) | Order · all 234 instances | time to proof (ms): 1875 -> 342 | Improved |
| add the approximation-based cutting rule (APPROXCSTR) to the Order model (ablation) | Order · large instances | time to proof (ms): 17166 -> 231 | Improved |
| add the MaxLoad value heuristic to Order+A (ablation) | Order+A · all 234 instances | #proofs: 174 / 234 -> 213 / 234 | Improved |
| add the MaxLoad value heuristic to Order+A (ablation) | Order+A · all 234 instances | time to proof (ms): 342 -> 137 | Improved |
| add the MaxLoad value heuristic to Order+A (ablation) | Order+A · large instances | #proofs: 17 / 51 -> 43 / 51 | Improved |
| add the MaxLoad value heuristic to Order+A (ablation) | Order+A · small instances | #proofs: 81 / 86 -> 83 / 86 | Improved |
| add the MaxLoad value heuristic to Order+A (ablation) | Order+A · medium instances | objective ratio: 1.0014 -> 1.0000 | Improved |
| use the Order model instead of the Integer model with SetTimes | Order · all 234 instances | #proofs: 127 / 234 -> 172 / 234 | Improved |
| use the Order model instead of the Integer model with domOverWDeg | Order · all 234 instances | objective ratio: 1.8780 -> 1.0201 | Improved |
| use Order+AM instead of Integer model on Chuffed | Order+AM · all 234 instances | objective ratio: 1.5653 -> 1.0000 | Improved |
| use Order instead of SetTimes search | Order · small instances | #proofs: 81 / 86 -> 81 / 86 | No clear effect |
Closest papers by meaning
- What to Predict for Efficient Scheduling on Parallel Machines (NeurIPS 2026 · similarity 0.84)
- Settling the Maximin Share Fairness for Scheduling among Groups of Machines (ICML 2025 · similarity 0.82)
- Fair Scheduling for Time-dependent Resources (NeurIPS 2021 · similarity 0.82)
- Differentiable Combinatorial Scheduling at Scale (ICML 2024 · similarity 0.81)
- What Are the Rules? Discovering Constraints from Data (AAAI 2024 · similarity 0.80)
- Proactive and Reactive Constraint Programming for Stochastic Project Scheduling with Maximal Time-Lags (AAAI 2025 · similarity 0.80)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.
