///|
pub(all) struct Task {
id : String
min_duration : Int32
max_duration : Int32
release : Int32
deadline : Int32
resource : String?
} derive(Eq, Debug)
///|
pub(all) struct Dependency {
before : String
after : String
kind : String
min_lag : Int32
max_lag : Int32?
} derive(Eq, Debug)
///|
pub struct PlanningProblem {
tasks : Array[Task]
dependencies : Array[Dependency]
names : Array[String]
rules : Array[Constraint]
}
///|
pub(all) struct ScheduledTask {
id : String
start : Int64
finish : Int64
} derive(Eq, Debug)
///|
pub(all) struct PlanStats {
nodes : Int32
pruned : Int32
decisions : Int32
charged_work : Int32
} derive(Eq, Debug)
///|
pub(all) enum PlanResult {
Planned(Array[ScheduledTask], PlanStats)
Unschedulable(PlanStats)
}
///|
fn task_index(tasks : Array[Task], id : String) -> Int32 raise StnError {
for i = 0; i < tasks.length(); i = i + 1 {
if tasks[i].id == id {
return i
}
}
raise StnError("invalid_input", "unknown task: " + id)
}
///|
fn point(i : Int32, finish : Bool) -> String {
"t" + i.to_string() + (if finish { "f" } else { "s" })
}
///|
pub fn planning_problem(
tasks : Array[Task],
dependencies : Array[Dependency],
) -> PlanningProblem raise StnError {
if tasks.length() < 1 || tasks.length() > 24 || dependencies.length() > 64 {
raise StnError(
"limit_exceeded", "require 1..24 tasks and at most 64 dependencies",
)
}
let ids : Map[String, Bool] = Map([])
let names = ["origin"]
let rules : Array[Constraint] = []
for i = 0; i < tasks.length(); i = i + 1 {
let t = tasks[i]
if !valid_name(t.id) || ids.contains(t.id) {
raise StnError("invalid_input", "invalid or duplicate task id")
}
ids[t.id] = true
if t.min_duration < 1 ||
t.max_duration < t.min_duration ||
t.max_duration > 1000000 ||
t.release < 0 ||
t.release > 1000000 ||
t.deadline < 0 ||
t.deadline > 1000000 {
raise StnError(
"invalid_input", "durations require 1<=min<=max<=1000000; windows require 0..1000000",
)
}
if t.resource is Some(r) && !valid_name(r) {
raise StnError("invalid_input", "invalid resource id")
}
let s = point(i, false)
let f = point(i, true)
names.push(s)
names.push(f)
rules.push({
id: "duration" + i.to_string(),
from: s,
to: f,
lower: Some(t.min_duration),
upper: Some(t.max_duration),
})
rules.push({
id: "release" + i.to_string(),
from: "origin",
to: s,
lower: Some(t.release),
upper: None,
})
rules.push({
id: "deadline" + i.to_string(),
from: "origin",
to: f,
lower: None,
upper: Some(t.deadline),
})
}
for i = 0; i < dependencies.length(); i = i + 1 {
let d = dependencies[i]
let a = task_index(tasks, d.before)
let b = task_index(tasks, d.after)
if !["FS", "SS", "FF", "SF"].contains(d.kind) ||
d.min_lag < -1000000 ||
d.min_lag > 1000000 {
raise StnError(
"invalid_input", "dependency kind must be FS/SS/FF/SF and lag within +/-1000000",
)
}
if d.max_lag is Some(v) && (v < d.min_lag || v > 1000000) {
raise StnError("invalid_input", "invalid maximum lag")
}
rules.push({
id: "dependency" + i.to_string(),
from: point(a, d.kind == "FS" || d.kind == "FF"),
to: point(b, d.kind == "FF" || d.kind == "SF"),
lower: Some(d.min_lag),
upper: d.max_lag,
})
}
{ tasks: tasks.copy(), dependencies: dependencies.copy(), names, rules, }
}
///|
/// Checks original task windows, durations, relations and exclusive resources; never calls solve.
pub fn verify_plan(
p : PlanningProblem,
schedule : Array[ScheduledTask],
) -> Bool {
if schedule.length() != p.tasks.length() {
return false
}
let values : Map[String, ScheduledTask] = Map([])
for s in schedule {
if values.contains(s.id) ||
s.start < 0L ||
s.finish < s.start ||
s.finish > 1000000L {
return false
}
values[s.id] = s
}
for t in p.tasks {
guard values.get(t.id) is Some(s) else { return false }
if s.start < t.release.to_int64() ||
s.finish > t.deadline.to_int64() ||
s.finish - s.start < t.min_duration.to_int64() ||
s.finish - s.start > t.max_duration.to_int64() {
return false
}
}
for d in p.dependencies {
let a = values[d.before]
let b = values[d.after]
let from = if d.kind == "FS" || d.kind == "FF" { a.finish } else { a.start }
let to = if d.kind == "FF" || d.kind == "SF" { b.finish } else { b.start }
if to - from < d.min_lag.to_int64() {
return false
}
if d.max_lag is Some(v) && to - from > v.to_int64() {
return false
}
}
for i = 0; i < p.tasks.length(); i = i + 1 {
for j = i + 1; j < p.tasks.length(); j = j + 1 {
if p.tasks[i].resource is Some(r) && p.tasks[j].resource == Some(r) {
let a = values[p.tasks[i].id]
let b = values[p.tasks[j].id]
if a.start < b.finish && b.start < a.finish {
return false
}
}
}
}
true
}
///|
priv struct PlanBranch {
arcs : Array[TemporalArc]
rule_ids : Array[String]
order : (Int32, Int32)?
}
///|
fn PlanBranch::compile(
self : PlanBranch,
index : Map[String, Int32],
) -> (Array[TemporalArc], Array[String]) raise StnError {
guard self.order is Some((before, after)) else {
return (self.arcs, self.rule_ids)
}
// The validated parent is shared by both children. Check only the new rule.
// Rule IDs and caps also cover callers using the readable model arrays.
if self.rule_ids.length() == 512 {
raise StnError(
"limit_exceeded", "require 1..64 timepoints and at most 512 constraints",
)
}
let id = "order" + before.to_string() + "_" + after.to_string()
if self.rule_ids.contains(id) {
raise StnError("invalid_input", "invalid or duplicate constraint id")
}
let finish = lookup_name(index, point(before, true))
let start = lookup_name(index, point(after, false))
let arcs = self.arcs.copy()
// finish(before) <= start(after) is a zero-weight lower-bound arc.
arcs.push({ source: start, target: finish, bound: 0L, })
let ids = self.rule_ids.copy()
ids.push(id)
(arcs, ids)
}
///|
fn first_resource_conflict(
tasks : Array[Task],
schedule : Array[ScheduledTask],
) -> (Int32, Int32)? {
for i = 0; i < tasks.length(); i = i + 1 {
guard tasks[i].resource is Some(resource) else { continue }
let a = schedule[i]
for j = i + 1; j < tasks.length(); j = j + 1 {
if tasks[j].resource == Some(resource) &&
a.start < schedule[j].finish &&
schedule[j].start < a.finish {
return Some((i, j))
}
}
}
None
}
///|
/// Bounded disjunctive search. Budget exhaustion raises, never returns Unschedulable.
pub fn plan(
p : PlanningProblem,
max_nodes~ : Int32 = 1000,
max_work~ : Int32 = 20000000,
) -> PlanResult raise StnError {
if max_nodes < 1 || max_nodes > 10000 || max_work < 1 || max_work > 100000000 {
raise StnError(
"invalid_input", "planning budgets: nodes 1..10000, work 1..100000000",
)
}
let (index, arcs) : (_, Array[TemporalArc]) = compile_edges(
p.names,
p.rules,
(_, source, target, bound, _) => { source, target, bound, },
)
let n = p.names.length()
let stack : Array[PlanBranch] = [
{ arcs, rule_ids: p.rules.map(rule => rule.id), order: None, },
]
let mut nodes = 0
let mut pruned = 0
let mut decisions = 0
let mut charged = 0
while !stack.is_empty() {
if nodes == max_nodes {
raise StnError(
"limit_exceeded", "planning node budget exhausted; no feasibility conclusion",
)
}
let (arcs, rule_ids) = stack.pop().unwrap().compile(index)
let e = arcs.length()
// Keep the 0.2.0 full-solve charge while computing only a feasibility witness.
let work = n * n * n + n * e + e + 2 * n
if work > max_work - charged {
raise StnError(
"limit_exceeded", "planning work budget exhausted; no feasibility conclusion",
)
}
charged += work
nodes += 1
match feasible_values(n, arcs, work) {
None => pruned += 1
Some(values) => {
let schedule = p.tasks.mapi((i, t) => {
id: t.id,
start: values[1 + 2 * i],
finish: values[2 + 2 * i],
})
match first_resource_conflict(p.tasks, schedule) {
None =>
return Planned(schedule, {
nodes,
pruned,
decisions,
charged_work: charged,
})
Some((i, j)) => {
decisions += 1
// Positive durations imply exactly one order must hold on this resource.
for (a, b) in [(j, i), (i, j)] {
stack.push({ arcs, rule_ids, order: Some((a, b)), })
}
}
}
}
}
}
Unschedulable({ nodes, pruned, decisions, charged_work: charged, })
}
///|
pub extend Task with Eq::{equal, not_equal}
///|
pub extend Task with @debug.Debug::{to_repr}
///|
pub extend Dependency with Eq::{equal, not_equal}
///|
pub extend Dependency with @debug.Debug::{to_repr}
///|
pub extend ScheduledTask with Eq::{equal, not_equal}
///|
pub extend ScheduledTask with @debug.Debug::{to_repr}
///|
pub extend PlanStats with Eq::{equal, not_equal}
///|
pub extend PlanStats with @debug.Debug::{to_repr}