Library manual

One divisible workload distributed from a single master to worker processors over a star network with a shared single-port link. This is the foundational DLT model and the entry point for all solvers in the portfolio: closed-form, heuristic, exact (branch-and-bound, MILP), approximation (FPTAS), and energy-aware methods. All star-model theory generalises to the other topologies as special cases.

Non-star topologies where load propagates through relay nodes before reaching compute workers. The chain and tree solvers apply the same simultaneous-finish LP as the star, adapted for cumulative relay delays at each intermediate node. The graph solver searches over candidate rooted spanning arborescences and applies the tree solver on the best one found.

Several independent divisible workloads that share the same processor pool and must be scheduled jointly on a single network port. The exact MLSD solver finds the task-activation order that minimises the joint makespan; a genetic-algorithm variant handles larger instances; a HiGHS MILP formulation is available when the full build is used; and an ML solver (ml-mlsd) predicts the optimal makespan in under a microsecond — unlike the star and topology classes, no closed form exists here, so this is where the ML estimate is genuinely faster than any exact alternative at scale. This models multiprogramming environments where distinct jobs compete for the same network and compute resources. Available via the CLI (--class=mlsd), the C/C++ library, and the Solver Studio MLSD tab.

A two-phase scheduling problem with mandatory precedence: a map phase that distributes and processes data in parallel, followed by a reduce phase that cannot begin until all partial results have been returned to the originator. The parameter γ₀ (result-return fraction) controls how much data flows back. The closed-form DLT scheduler derives the optimal mapper loads, the reducer start time, and the global makespan analytically in O(m) time, assuming the network can serve every reducer at once. A second, exact solver drops that assumption: it caps concurrent mapper-to-reducer reads at a bisection-width limit l and optimizes mapper loads jointly with the resulting read schedule via an LP (HiGHS builds only). Available via the CLI (--class=mapreduce / --class=mapreduce-bwidth), the C/C++ library, and the Solver Studio MapReduce tab.

A generalization of MapReduce (Berlińska thesis, ch. 5): one mapper layer feeding R reducer layers in a pipeline, each reading the whole output of the previous layer and forwarding a γ fraction to the next. Closed-form for homogeneous mappers/reducers within each layer, recovering plain MapReduce as the R = 1 case. Available via the CLI (--class=multilayer), the C/C++ library, and the Solver Studio Multilayer tab.

A MapReduce variant the closed-form scheduler above doesn’t solve: reducers that read at different speeds, sharing a channel (bisection-width) capacity limit, where WHO reads WHAT and WHEN is genuinely optimized rather than fixed by a round-robin formula. Solved exactly by branch-and-price (HiGHS builds only) — a master LP picks one read plan per reducer, fed by a per-reducer pricing subproblem, branching on individual read-timing decisions. Supports an optional per-reducer subset of mapper outputs (not every reducer need read every mapper) and a switchable objective (minimize the latest finish, or the sum of finish times). Available via the CLI (--class=reducer-read), the C/C++ library, and the Solver Studio Reducer read tab.

Every other MapReduce solver above assumes each reducer gets an equal share of the intermediate data — in practice the key partition is often unbalanced, and the slowest reducer determines the finish time. Two dependency-free mitigation algorithms: a static method that splits the key space more finely than the reducer count and greedily reassigns the parts (LPT bin-packing) before any reducer reads; and a dynamic method that leaves the partition alone and, once every reducer has finished sorting, rebalances the remaining work from the busiest reducers onto the already-finished ones in a single pass. Available via the CLI (--class=mapreduce-skew-static / --class=mapreduce-skew-dynamic), the C/C++ library, and the Solver Studio Skew mitigation tab.

A genuinely different topology from everything else here: bipartite, not a star or relay tree. m storage nodes hold the input data and n ≥ m mapper nodes (the first m of which are the same physical nodes as the storage nodes, so they process their own data for free) pull from potentially several storage nodes at once. Only the map phase is modeled. Solved exactly by an LP (HiGHS builds only) that either derives the optimal data placement among storage nodes too, or optimizes the read schedule alone against a fixed placement. Available via the CLI (--class=multisource), the C/C++ library, and the Solver Studio Multi-source tab.