Module network 

Network models and scheduling: project planning, flows on networks, and the sequencing rules that provably optimise a stated objective.

Two threads run through this module. The first is that several graph problems are linear programs in disguise, and their constraint matrices are totally unimodular, so the linear relaxation is automatically integral. Shortest path and maximum flow both have this property, which is why they can be solved by combinatorial algorithms and by a general linear programming solver with the same answer. Having both is worth the duplication: the graph module’s algorithms are far faster, and the linear programs are an independent check on them.

The second is that scheduling is a subject of exact greedy rules rather than heuristics. Sorting by processing time minimises mean flow time; sorting by due date minimises maximum lateness; Moore and Hodgson’s rule minimises the number of late jobs; Johnson’s rule minimises makespan on two machines. Each is provably optimal for its own objective and provably not for the others – shortest-processing-time can make a job catastrophically late while minimising the average – so the objective must be chosen before the rule. The tests check each rule against exhaustive enumeration of every permutation, on the objective it claims and on nothing else.

Structs

TaskTimes

The four schedule times of one task: earliest start, earliest finish, latest start, latest finish.

Functions

critical_path_method

The critical path method: the shortest possible project duration, which tasks cannot slip, and every task’s four schedule times.

gantt_data

Turns a single-machine job order into (job, start, finish) bars.

interval_scheduling_max

The largest set of pairwise disjoint intervals, by earliest finish time.

job_shop_shifting_bottleneck_lite

A lower bound on a job shop makespan by the shifting bottleneck idea, simplified.

johnson_two_machine

Johnson’s rule: the order minimising makespan through two machines in series.

lpt_makespan

Longest processing time first onto identical parallel machines.

max_flow_lp_check

The value of a maximum flow, computed as a linear program.

moore_hodgson

The Moore-Hodgson rule: the order minimising the number of late jobs on one machine.

network_simplex_lite

A minimum-cost flow by the network simplex, expressed through the general simplex method.

pert

PERT: the mean and variance of the project duration under three-point estimates.

scheduling_edd

Earliest due date first: the order minimising maximum lateness on one machine.

scheduling_spt

Shortest processing time first: the order minimising mean flow time on one machine.

shortest_path_lp_check

The length of a shortest path, computed as a linear program.

transshipment

The transshipment problem: ship from sources to sinks through intermediate nodes at least cost.

two_machine_makespan

The makespan of a two-machine flow shop under a given order.

vehicle_routing_savings

Clarke-Wright savings for the capacitated vehicle routing problem.

weighted_interval_scheduling

The most valuable set of pairwise disjoint intervals.