Satisfiability Modulo Theories: An Efficient Approach for the Resource-Constrained Project Scheduling Problem

Carlos Ansótegui · Miquel Bofill · Miquel Palahí · Josep Suy · Mateu Villaret

28 citations0/0 files storedSymposium on Abstraction, Reformulation and Approximation

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

The Resource-Constrained Project Scheduling Problem (RCPSP) and some of its extensions have been widely studied. Many approaches have been considered to solve this problem: constraint programming (CP), Boolean satisfiability (SAT), mixed integer linear programming (MILP), branch and bound algorithms (BB) and others. In this paper, we present a new approach for solving this problem: satisfiability modulo theories (SMT). Solvers for SMT generalize SAT solving by adding the ability to handle arithmetic and other theories. We provide several encodings of the RCPSP into SMT, and introduce rcp2smt, a tool for solving RCPSP instances using SMT solvers, which exhibits good performance.

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 — 28 citations exist upstream.

References

1999Resource-constrained project scheduling: Notation, classification, models, and methods 1997PSPLIB - A project scheduling problem library 2004Project scheduling under uncertainty: Survey and research potentials 2009A survey of variants and extensions of the resource-constrained project scheduling problem 1969Multiproject Scheduling with Limited Resources: A Zero-One Programming Approach 1998Resource-constrained project scheduling: A survey of recent developments 2001An integrated survey of deterministic project scheduling 1988Scheduling project networks with resource constraints and time windows

Cited by

2020SMT encodings for Resource-Constrained Project Scheduling Problems

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.