Complete MCS-based search: application to resource constrained project scheduling

Philippe Laborie

69 citations0/0 files storedInternational Joint Conference on Artificial Intelligence

No readable copy stored yet — this record is metadata only.

No open-access location is known for this record yet.

Literature note Cite in a project Citation map

Resource-Constrained Project Scheduling Scheduling and Optimization Algorithms Constraint Satisfaction and Optimization

Abstract

This paper describes a simple complete search for cumulative scheduling based on the detection and resolution of minimal critical sets (MCS). The heuristic for selecting MCSs relies on an estimation of the related reduction of the search space. An extension of the search procedure using self-adapting shaving is proposed. The approach was implemented on top of classical constraint propagation algorithms and tested on resource constrained project scheduling problems (RCPSP). We were able to close more than 15% of the previously open problems of the PSPLIB [Kolisch and Sprecher, 1996] and improve more than 31% of the best known lower bounds on those heavily studied problems. Other new results on open-shop and cumulative job-shop scheduling are reported.

Paper brief

Loading…

Cite this work

Citation unavailable for this work.

BibTeX RIS CSL-JSON

No public copy is stored for this record, so only the metadata is cited.

Citations in this library

Citation map →

Stored only when both papers are in the corpus — 69 citations exist upstream.

References

1997PSPLIB - A project scheduling problem library 2002Project Scheduling: A Research Handbook 2000Experimental evaluation of state-of-the-art heuristics for the resource-constrained project scheduling problem 2000A linear programming and constraint propagation-based lower bound for the RCPSP

Cited by

2012Optimal methods for resource allocation and scheduling: a cross-disciplinary survey 2011Timetable Edge Finding Filtering Algorithm for Discrete Cumulative Resources 2008Extending the RCPSP for modeling and solving disruption management problems 2011Satisfiability Modulo Theories: An Efficient Approach for the Resource-Constrained Project Scheduling Problem

Explore the map →

Papers that cite the same references — the relational fallback while embeddings are still backfilling.

Imported from OpenAlex (CC0) — nothing here is generated.