pycsp3-scheduling 0.2.4

Scheduling extension for PyCSP3 with interval variables, sequence variables, and scheduling constraints

pycsp3-scheduling

Scheduling extension for pycsp3 with interval variables, sequence variables, and scheduling constraints.

Features

• Interval Variables: Represent tasks/activities with start, end, size, length, and optional presence
• Intensity Functions: Stepwise intensity metadata with granularity scaling for size/length
• Sequence Variables: Ordered sequences of intervals on disjunctive resources
• Precedence Constraints: end_before_start, start_at_start, etc.
• Grouping Constraints: span, alternative, synchronize
• Sequence Constraints: SeqNoOverlap, first, last, before, previous, same_sequence
• Forbidden Time Constraints: forbid_start, forbid_end, forbid_extent
• Presence Constraints: presence_implies, presence_or, presence_xor, chain
• Cumulative Functions: pulse, step_at_start, step_at_end for resource modeling
• State Functions: Model resource states with transitions
• XCSP3 Extension: Output scheduling models in extended XCSP3 format
• Visualization: Gantt charts and resource profiles

Installation

pip install pycsp3-scheduling

For development:

git clone https://github.com/sohaibafifi/pycsp3-scheduling.git
cd pycsp3-scheduling
pip install -e ".[dev]"

Quick Start

from pycsp3 import *
from pycsp3_scheduling import *

# Create interval variables for tasks
task1 = IntervalVar(size=10, name="task1")
task2 = IntervalVar(size=15, name="task2")
task3 = IntervalVar(size=8, name="task3")

# Precedence: task1 must finish before task2 starts
satisfy(end_before_start(task1, task2))

# No overlap: task2 and task3 cannot overlap
satisfy(SeqNoOverlap([task2, task3]))

# Minimize makespan
minimize(max(end_time(task1), end_time(task2), end_time(task3)))

Example: Job Shop Scheduling

from pycsp3 import *
from pycsp3_scheduling import *

# Data
n_jobs, n_machines = 3, 3
durations = [[3, 2, 2], [2, 1, 4], [4, 3, 3]]
machines = [[0, 1, 2], [0, 2, 1], [1, 0, 2]]

# Create interval variables for each operation
ops = [[IntervalVar(size=durations[j][o], name=f"op_{j}_{o}")
        for o in range(n_machines)] for j in range(n_jobs)]

# Sequences for each machine
sequences = [SequenceVar(
    intervals=[ops[j][o] for j in range(n_jobs)
               for o in range(n_machines) if machines[j][o] == m],
    name=f"machine_{m}"
) for m in range(n_machines)]

# Precedence within jobs
satisfy(
    end_before_start(ops[j][o], ops[j][o+1])
    for j in range(n_jobs) for o in range(n_machines-1)
)

# No overlap on machines
satisfy(SeqNoOverlap(seq) for seq in sequences)

# Minimize makespan
minimize(Maximum(end_time(ops[j][-1]) for j in range(n_jobs)))

Example: RCPSP (Resource-Constrained Project Scheduling)

from pycsp3 import *
from pycsp3_scheduling import *

# Data
durations = [3, 2, 5, 4, 2]
demands = [[2, 1], [1, 2], [3, 0], [2, 1], [1, 3]]
capacities = [4, 3]
precedences = [(0, 2), (1, 3), (2, 4)]

# Interval variables
tasks = [IntervalVar(size=durations[i], name=f"task_{i}")
         for i in range(len(durations))]

# Precedence constraints
satisfy(end_before_start(tasks[p], tasks[s]) for p, s in precedences)

# Cumulative resource constraints
for r in range(len(capacities)):
    resource = sum(pulse(tasks[i], demands[i][r])
                   for i in range(len(tasks)) if demands[i][r] > 0)
    satisfy(resource <= capacities[r])

# Minimize makespan
minimize(Maximum(end_time(t) for t in tasks))

API Reference

Variables

Function	Description
IntervalVar(size, start, end, length, intensity, granularity, optional, name)	Create an interval variable
IntervalVarArray(size, ...)	Create array of interval variables
SequenceVar(intervals, types, name)	Create a sequence variable

Expressions

Function	Description
start_of(interval, absent_value=0)	Start time of interval
end_of(interval, absent_value=0)	End time of interval
size_of(interval, absent_value=0)	Size/duration of interval
length_of(interval, absent_value=0)	Length of interval
presence_of(interval)	Boolean presence status
overlap_length(interval1, interval2, absent_value=0)	Overlap duration between two intervals
expr_min(*args)	Minimum of scheduling expressions
expr_max(*args)	Maximum of scheduling expressions

Element Expressions (Array Indexing)

Function	Description
element(array, index)	Access array element by interval expression index
element2d(matrix, row, col)	Access 2D matrix element by interval expressions
ElementMatrix(matrix)	Wrapper for 2D indexing with [] operator

Interop Helpers

Function	Description
start_time(interval)	pycsp3 variable for start time
end_time(interval)	pycsp3 expression for end time
presence_time(interval)	pycsp3 variable for presence (optional intervals)
interval_value(interval)	Get solved interval values (start, end, size, present)
model_statistics()	Get model statistics (variables, constraints counts)
solution_statistics()	Get solution statistics after solving

Precedence Constraints

Constraint	Semantics (when both present)
start_before_start(a, b, delay)	start(b) >= start(a) + delay
start_before_end(a, b, delay)	end(b) >= start(a) + delay
end_before_start(a, b, delay)	start(b) >= end(a) + delay
end_before_end(a, b, delay)	end(b) >= end(a) + delay
start_at_start(a, b, delay)	start(b) == start(a) + delay
start_at_end(a, b, delay)	start(b) == end(a) + delay
end_at_start(a, b, delay)	end(a) == start(b) + delay
end_at_end(a, b, delay)	end(b) == end(a) + delay

Grouping Constraints

Constraint	Description
span(main, subtasks)	Main interval spans all present subtasks
alternative(main, alts, card=1)	Select card alternatives matching main
synchronize(main, intervals)	All present intervals sync with main

Sequence Constraints

Constraint	Description
SeqNoOverlap(sequence, transition_matrix, is_direct)	Non-overlap with optional transition times
first(sequence, interval)	Constrain interval to be first in sequence
last(sequence, interval)	Constrain interval to be last in sequence
before(sequence, interval1, interval2)	interval1 must end before interval2 starts
previous(sequence, interval1, interval2)	interval1 immediately precedes interval2
same_sequence(seq1, seq2)	Common intervals have same position in both
same_common_subsequence(seq1, seq2)	Common intervals have same relative order

Sequence Accessor Expressions

Function	Description
start_of_next(sequence, interval, absent_value)	Start time of next interval in sequence
end_of_next(sequence, interval, absent_value)	End time of next interval
size_of_next(sequence, interval, absent_value)	Size of next interval
length_of_next(sequence, interval, absent_value)	Length of next interval
type_of_next(sequence, interval, absent_value)	Type of next interval
start_of_prev(sequence, interval, absent_value)	Start time of previous interval
end_of_prev(sequence, interval, absent_value)	End time of previous interval
size_of_prev(sequence, interval, absent_value)	Size of previous interval
length_of_prev(sequence, interval, absent_value)	Length of previous interval
type_of_prev(sequence, interval, absent_value)	Type of previous interval

Cumulative Functions

Function	Description
pulse(interval, height)	Constant consumption during interval
step_at(time, height)	Step at fixed time point
step_at_start(interval, height)	Step at interval start
step_at_end(interval, height)	Step at interval end
height_at_start(interval, cumul)	Cumulative height at interval start
height_at_end(interval, cumul)	Cumulative height at interval end
cumul_range(cumul, min, max)	Constrain cumul to [min, max]
always_in(cumul, interval, min, max)	Cumul in range during interval
SeqCumulative(sequence, heights, capacity)	Cumulative on sequence with per-interval heights

State Functions

Function	Description
StateFunction(transition_matrix)	Create state function with optional transitions
TransitionMatrix(n_states)	Create transition matrix for state function
always_equal(func, interval, value)	State equals value during interval
always_constant(func, interval)	State constant during interval
always_no_state(func, interval)	No state assigned during interval

Forbidden Time Constraints

Constraint	Description
forbid_start(interval, periods)	Interval cannot start during forbidden periods
forbid_end(interval, periods)	Interval cannot end during forbidden periods
forbid_extent(interval, periods)	Interval cannot overlap forbidden periods

Presence Constraints

Constraint	Description
presence_implies(a, b)	If a is present, b must be present
presence_or(a, b)	At least one must be present
presence_xor(a, b)	Exactly one must be present
all_present_or_all_absent(intervals)	All-or-nothing group
if_present_then(interval, constraint)	Apply constraint only when present
at_least_k_present(intervals, k)	At least k must be present
at_most_k_present(intervals, k)	At most k can be present
exactly_k_present(intervals, k)	Exactly k must be present

Chain Constraints

Constraint	Description
chain(intervals, delays)	Intervals execute in sequence with optional delays
strict_chain(intervals, delays)	Intervals execute back-to-back (equality)

Requirements

• Python >= 3.10
• pycsp3 >= 2.5
• lxml >= 4.9
• matplotlib >= 3.7 (optional, for visualization)
• java >= 8 (optional, for solving with ACE/Choco)

License

MIT License - see LICENSE file.

References

• PyCSP3 Documentation
• XCSP3 Specification