Scheduling

Interval scheduling algorithms: greedy maximum-cardinality selection, minimum partitioning, minimum-lateness sequencing and the weighted-interval dynamic program.

Scheduling algorithms.

Ports of the MATLAB TCL’s Scheduling directory: interval scheduling by greedy and dynamic-programming methods, as used for sensor time-allocation problems.

pytcl.scheduling.schedule_intervals(intervals)[source]

Maximum-cardinality set of non-overlapping intervals.

The earliest-finish-time greedy algorithm; an interval may start exactly when the previous one finishes.

Port of scheduleIntervals.

Parameters:

intervals (array_like) – (2, N) columns [start; finish].

Returns:

jobs – Indices of the selected intervals, in the order scheduled.

Return type:

ndarray

Examples

>>> schedule_intervals([[0.0, 1.0, 3.0], [2.0, 4.0, 5.0]])
array([0, 2])
pytcl.scheduling.partition_intervals(intervals)[source]

Partition intervals into a minimum number of compatible groups.

The earliest-start greedy algorithm: each interval joins the first existing group whose last job has finished, or opens a new group. The number of groups equals the depth of the interval set.

Port of partitionIntervals.

Parameters:

intervals (array_like) – (2, N) columns [start; finish].

Returns:

partition – For each interval, its 0-based group index.

Return type:

ndarray

Examples

>>> partition_intervals([[0.0, 1.0, 3.0], [2.0, 4.0, 5.0]])
array([0, 1, 0])
pytcl.scheduling.schedule_min_lateness_dense(deadlines, durations, t_start=0.0)[source]

Sequence jobs back-to-back to minimize the maximum lateness.

The earliest-deadline-first rule; jobs run densely (no idle time) from t_start.

Port of scheduleMinLatenessDense.

Parameters:

  • deadlines (array_like) – (N,) job deadlines.

  • durations (array_like) – (N,) job durations.

  • t_start (float, optional) – Time the first job starts. Default 0.

Returns:

  • jobs (ndarray) – Job indices in execution order.

  • t_starts (ndarray) – The start time of each scheduled job, in the same order.

Return type:

tuple[ndarray[tuple[Any, …], dtype[int64]], ndarray[tuple[Any, …], dtype[float64]]]

Examples

>>> jobs, starts = schedule_min_lateness_dense([6.0, 2.0], [1.0, 2.0])
>>> jobs
array([1, 0])
>>> starts
array([0., 2.])
pytcl.scheduling.schedule_weighted_intervals(intervals, weights)[source]

Maximum-weight set of non-overlapping intervals.

The classic dynamic program over intervals sorted by finish time, with the compatible-predecessor table built by binary search.

Port of scheduleWeightedIntervals. Weights are assumed positive, as upstream (the MATLAB traceback loop does not terminate for a leading run of non-positive optima).

Parameters:

  • intervals (array_like) – (2, N) columns [start; finish].

  • weights (array_like) – (N,) positive interval weights.

Returns:

  • weight (float) – The total weight of the optimal selection.

  • jobs (ndarray) – Indices of the selected intervals.

Return type:

tuple[float, ndarray[tuple[Any, …], dtype[int64]]]

Examples

>>> w, jobs = schedule_weighted_intervals(
...     [[0.0, 1.0, 3.0], [2.0, 4.0, 5.0]], [1.0, 5.0, 1.0])
>>> w
5.0
>>> jobs
array([1])

Interval scheduling algorithms.

Ports of the MATLAB TCL’s Scheduling directory: the classic greedy and dynamic-programming interval problems – maximum-cardinality selection, minimum resource partitioning, minimum-lateness sequencing and maximum-weight selection. Intervals are [start; finish] columns of a (2, N) array, matching the MATLAB layout; job indices in the results are 0-based.

References

  • J. Kleinberg and E. Tardos, Algorithm Design, 1st ed. Pearson, 2005: Chapter 4.1 (interval scheduling and partitioning), 4.2 (minimum lateness) and 6.1-6.2 (weighted interval scheduling) – the chapters the MATLAB implementations cite.

pytcl.scheduling.intervals.schedule_intervals(intervals)[source]

Maximum-cardinality set of non-overlapping intervals.

The earliest-finish-time greedy algorithm; an interval may start exactly when the previous one finishes.

Port of scheduleIntervals.

Parameters:

intervals (array_like) – (2, N) columns [start; finish].

Returns:

jobs – Indices of the selected intervals, in the order scheduled.

Return type:

ndarray

Examples

>>> schedule_intervals([[0.0, 1.0, 3.0], [2.0, 4.0, 5.0]])
array([0, 2])
pytcl.scheduling.intervals.partition_intervals(intervals)[source]

Partition intervals into a minimum number of compatible groups.

The earliest-start greedy algorithm: each interval joins the first existing group whose last job has finished, or opens a new group. The number of groups equals the depth of the interval set.

Port of partitionIntervals.

Parameters:

intervals (array_like) – (2, N) columns [start; finish].

Returns:

partition – For each interval, its 0-based group index.

Return type:

ndarray

Examples

>>> partition_intervals([[0.0, 1.0, 3.0], [2.0, 4.0, 5.0]])
array([0, 1, 0])
pytcl.scheduling.intervals.schedule_min_lateness_dense(deadlines, durations, t_start=0.0)[source]

Sequence jobs back-to-back to minimize the maximum lateness.

The earliest-deadline-first rule; jobs run densely (no idle time) from t_start.

Port of scheduleMinLatenessDense.

Parameters:

  • deadlines (array_like) – (N,) job deadlines.

  • durations (array_like) – (N,) job durations.

  • t_start (float, optional) – Time the first job starts. Default 0.

Returns:

  • jobs (ndarray) – Job indices in execution order.

  • t_starts (ndarray) – The start time of each scheduled job, in the same order.

Return type:

tuple[ndarray[tuple[Any, …], dtype[int64]], ndarray[tuple[Any, …], dtype[float64]]]

Examples

>>> jobs, starts = schedule_min_lateness_dense([6.0, 2.0], [1.0, 2.0])
>>> jobs
array([1, 0])
>>> starts
array([0., 2.])
pytcl.scheduling.intervals.schedule_weighted_intervals(intervals, weights)[source]

Maximum-weight set of non-overlapping intervals.

The classic dynamic program over intervals sorted by finish time, with the compatible-predecessor table built by binary search.

Port of scheduleWeightedIntervals. Weights are assumed positive, as upstream (the MATLAB traceback loop does not terminate for a leading run of non-positive optima).

Parameters:

  • intervals (array_like) – (2, N) columns [start; finish].

  • weights (array_like) – (N,) positive interval weights.

Returns:

  • weight (float) – The total weight of the optimal selection.

  • jobs (ndarray) – Indices of the selected intervals.

Return type:

tuple[float, ndarray[tuple[Any, …], dtype[int64]]]

Examples

>>> w, jobs = schedule_weighted_intervals(
...     [[0.0, 1.0, 3.0], [2.0, 4.0, 5.0]], [1.0, 5.0, 1.0])
>>> w
5.0
>>> jobs
array([1])