The resource-constrained project scheduling problem and its schedule classes
DefinitionComplexScheduling_RCPSPThis file fixes the resource-constrained project scheduling problem (RCPSP), the central model of Brucker and Knust's book, together with the left-shift classification of its schedules.
The problem. There are activities and renewable resources. Activity must be processed without interruption for time units, during which it occupies a constant units of resource ; a constant units of resource is available at every time. Precedence constraints are given as a set of pairs , meaning cannot start before is complete. All data are integers.
A schedule assigns each activity an integer starting time , and its completion times are . It is feasible when
- every precedence constraint holds, whenever ; and
- at every time the total demand does not exceed the capacity, for every resource .
Left shifts. A left shift of activity moves it to an earlier start, leaving every other activity where it is, and lands on a feasible schedule. It is a local left shift when it can be reached by successive one-period shifts — every intermediate schedule being feasible — and a global left shift otherwise, meaning some intermediate schedule violates a resource constraint. A feasible schedule is semi-active when no local left shift is possible for any activity, and active when no left shift at all, local or global, is possible.
Objectives. An objective evaluated on the completion-time vector is regular when it is monotone nondecreasing: whenever for every . Makespan, total weighted completion time, maximum lateness and the weighted number of late activities are all regular. A schedule is optimal when no feasible schedule gives a smaller value of .
Formalization Note Starting times are natural numbers, matching the book's "all data are
assumed to be integers" and ; no finite horizon is imposed, which only
enlarges the feasible set. Precedence constraints are a Finset of pairs rather than a relation,
so they are finite and decidable, and no acyclicity is assumed — an inconsistent set simply has
no feasible schedule. The resource constraint is quantified over every natural time , which is
equivalent to quantifying over because no activity is in process beyond the last
completion. Active is stated as "no left shift", which is the book's "no local or global left
shift" unfolded: a global left shift is by definition one that is not local, so the two cases are
exhaustive.
import Mathlib
namespace ComplexScheduling
variable {n r : ℕ}
/-- Activity `i` is in process at the integer time `t` under the schedule `S`: it has started
and has not yet completed. Brucker and Knust, *Complex Scheduling*, §1.1, p. 1. -/
def InProcess (p : Fin n → ℕ) (S : Fin n → ℕ) (t : ℕ) (i : Fin n) : Prop :=
S i ≤ t ∧ t < S i + p i
instance (p : Fin n → ℕ) (S : Fin n → ℕ) (t : ℕ) : DecidablePred (InProcess p S t) :=
fun _ => inferInstanceAs (Decidable (_ ∧ _))
/-- The total amount of resource `k` occupied at time `t`: activity `i` occupies `demand i k`
units throughout its processing. Brucker and Knust §1.1, p. 1. -/
def resourceUsage (p : Fin n → ℕ) (demand : Fin n → Fin r → ℕ) (S : Fin n → ℕ)
(k : Fin r) (t : ℕ) : ℕ :=
∑ i ∈ Finset.univ.filter (InProcess p S t), demand i k
/-- A schedule assigns each activity an integer starting time; it is **feasible** when the
precedence constraints `i → j`, given as pairs in `prec`, are met — `S i + p i ≤ S j` — and when
at every time the demand for each resource is within its capacity. Brucker and Knust §1.1,
pp. 1-2. -/
def FeasibleSchedule (p : Fin n → ℕ) (Rcap : Fin r → ℕ) (demand : Fin n → Fin r → ℕ)
(prec : Finset (Fin n × Fin n)) (S : Fin n → ℕ) : Prop :=
(∀ e ∈ prec, S e.1 + p e.1 ≤ S e.2) ∧
∀ (k : Fin r) (t : ℕ), resourceUsage p demand S k t ≤ Rcap k
/-- The schedule obtained from `S` by starting activity `i` at time `s` instead, every other
activity left where it was. -/
def restart (S : Fin n → ℕ) (i : Fin n) (s : ℕ) : Fin n → ℕ := Function.update S i s
/-- A **left shift** of activity `i` to time `s`: `s < S i` and the result is feasible, all other
activities unmoved. Brucker and Knust §3.1.2, p. 119. -/
def LeftShiftTo (p : Fin n → ℕ) (Rcap : Fin r → ℕ) (demand : Fin n → Fin r → ℕ)
(prec : Finset (Fin n × Fin n)) (S : Fin n → ℕ) (i : Fin n) (s : ℕ) : Prop :=
s < S i ∧ FeasibleSchedule p Rcap demand prec (restart S i s)
/-- A **local left shift**: a left shift reachable by successive one-period left shifts, so every
intermediate schedule — the start of `i` lowered one time unit at a time — is itself feasible.
Brucker and Knust §3.1.2, pp. 119-120. -/
def LocalLeftShiftTo (p : Fin n → ℕ) (Rcap : Fin r → ℕ) (demand : Fin n → Fin r → ℕ)
(prec : Finset (Fin n × Fin n)) (S : Fin n → ℕ) (i : Fin n) (s : ℕ) : Prop :=
s < S i ∧ ∀ u : ℕ, s ≤ u → u ≤ S i → FeasibleSchedule p Rcap demand prec (restart S i u)
/-- A feasible schedule is **semi-active** when no local left shift is possible for any activity.
Brucker and Knust §3.1.2, p. 120. -/
def SemiActive (p : Fin n → ℕ) (Rcap : Fin r → ℕ) (demand : Fin n → Fin r → ℕ)
(prec : Finset (Fin n × Fin n)) (S : Fin n → ℕ) : Prop :=
FeasibleSchedule p Rcap demand prec S ∧
∀ (i : Fin n) (s : ℕ), ¬ LocalLeftShiftTo p Rcap demand prec S i s
/-- A feasible schedule is **active** when no left shift at all — local or global — is possible
for any activity. Brucker and Knust §3.1.2, p. 120. -/
def Active (p : Fin n → ℕ) (Rcap : Fin r → ℕ) (demand : Fin n → Fin r → ℕ)
(prec : Finset (Fin n × Fin n)) (S : Fin n → ℕ) : Prop :=
FeasibleSchedule p Rcap demand prec S ∧
∀ (i : Fin n) (s : ℕ), ¬ LeftShiftTo p Rcap demand prec S i s
/-- The completion times `C i = S i + p i` of a schedule. Brucker and Knust §1.1, p. 2. -/
def completion (p : Fin n → ℕ) (S : Fin n → ℕ) : Fin n → ℕ := fun i => S i + p i
/-- An objective is **regular** when it is monotone nondecreasing in the completion times:
`f C ≤ f C'` whenever `C i ≤ C' i` for every activity. Brucker and Knust §1.2, p. 18. -/
def Regular (f : (Fin n → ℕ) → ℝ) : Prop :=
∀ C C' : Fin n → ℕ, (∀ i, C i ≤ C' i) → f C ≤ f C'
/-- The objective value of a schedule: `f` evaluated at its completion-time vector. -/
def scheduleValue (p : Fin n → ℕ) (f : (Fin n → ℕ) → ℝ) (S : Fin n → ℕ) : ℝ :=
f (completion p S)
/-- `S` is optimal when no feasible schedule has a smaller objective value. -/
def IsOptimalSchedule (p : Fin n → ℕ) (Rcap : Fin r → ℕ) (demand : Fin n → Fin r → ℕ)
(prec : Finset (Fin n × Fin n)) (f : (Fin n → ℕ) → ℝ) (S : Fin n → ℕ) : Prop :=
FeasibleSchedule p Rcap demand prec S ∧
∀ S' : Fin n → ℕ, FeasibleSchedule p Rcap demand prec S' →
scheduleValue p f S ≤ scheduleValue p f S'
end ComplexScheduling