Documentation

Library manual

Reference for the self-contained C++20 divisible-load scheduling library that powers this portal: what it is for, what it covers, how to build and use it, and how it is licensed. Concepts and notation are defined in the Knowledge base. This manual is a living document and will grow as new problem classes and solvers are added.

Command line

The dls tool has three subcommands: list (print the available solvers and problem classes), solve (read an instance file and run a solver), and show (parse and re-emit an instance in canonical form). All flags use the --key=value syntax. The --json flag switches the output from human-readable text to the machine-readable JSON contract, which includes the full Gantt timing for every fragment.

Available solvers

$ dls list
Single-load solvers (--class=dls, default):
  --solver=auto         (heuristic)
  --solver=ga           (heuristic)
  --solver=best-rate    (heuristic)
  --solver=online       (heuristic)
  --solver=single-round (heuristic)
  --solver=exact        (exact)
  --solver=exact-dual   (exact)
  --solver=optv         (exact)
  --solver=fptas-optv   (heuristic)
  --solver=fptas-optt   (heuristic)
  --solver=exact-milp   (exact)   # HiGHS build only
  --solver=milp-multi   (exact)   # HiGHS build only
Other problem classes:
  --class=mlsd        --solver=mlsd-exact (default) | mlsd-ga | mlsd-milp
  --class=mapreduce   (closed-form scheduler)
  --class=mapreduce-bwidth (bisection-width limit, exact LP)   # HiGHS build only
  --class=mapreduce-skew-static  (reducer skew mitigation, fine partition + LPT)
  --class=mapreduce-skew-dynamic (reducer skew mitigation, single-shot rebalancing)
  --class=multilayer  (closed-form scheduler)
  --class=chain       (linear daisy chain, allocation LP)
  --class=tree        (multi-level tree, allocation LP)
  --class=graph       (general graph, best spanning arborescence)
  --class=reducer-read (heterogeneous multi-channel read scheduling, branch-and-price)   # HiGHS build only
  --class=multisource  (multi-source map-phase scheduling, bipartite LP)   # HiGHS build only

Examples

# human-readable solve output (default)
$ dls solve --solver=best-rate instance.txt
solver     : best-rate (heuristic)
status     : Feasible
makespan   : 302.14
load (Σα)  : 1000.0
lower bound: 298.51
schedule   :
  P0  load=417.31
  P1  load=332.84
  P2  load=249.85
time (s)   : 0.000312

# machine-readable JSON (for front-ends and scripts)
$ dls solve --solver=auto --json instance.txt | python3 -m json.tool

# exact branch-and-bound with a 10 000-node budget
$ dls solve --solver=exact --nodes=10000 instance.txt

# FPTAS OptT with ε = 0.01 (1 % approximation guarantee)
$ dls solve --solver=fptas-optt --epsilon=0.01 instance.txt

# non-star topologies
$ dls solve --class=chain  chain.txt
$ dls solve --class=tree   tree.txt
$ dls solve --class=graph  graph.txt

# show the parsed instance in canonical form (sanity check)
$ dls show instance.txt

JSON output structure

With --json the tool emits a single JSON object. The fragments array gives the full Gantt chart: each entry is one installment with its communication and computation windows. Timing fields are in the same time units as the instance parameters.

// output of: dls solve --solver=best-rate --json instance.txt
{
  "lowerBound": 298.51,
  "solution": {
    "status":  "Feasible",
    "makespan": 302.14,
    "energy":  0.0,
    "sequence": [0, 1, 2],
    "fragments": [
      { "processorId": 0, "loadSize": 417.31,
        "commStart": 0.10,  "commFinish": 46.10,
        "computeStart": 46.10, "computeFinish": 302.14 },
      { "processorId": 1, "loadSize": 332.84,
        "commStart": 46.10, "commFinish": 116.82,
        "computeStart": 116.82, "computeFinish": 302.14 },
      { "processorId": 2, "loadSize": 249.85,
        "commStart": 116.82, "commFinish": 193.57,
        "computeStart": 193.57, "computeFinish": 302.14 }
    ],
    "wallTimeSec": 0.000312
  }
}

Flags reference

Flag Default Applies to Description
--solver=NAME (required) single-load Solver name; run dls list to see what is available in this build.
--class=CLASS dls all Problem class: dls · mlsd · mapreduce · mapreduce-bwidth · mapreduce-skew-static · mapreduce-skew-dynamic · multilayer · chain · tree · graph · reducer-read · multisource.
--json off single-load Emit machine-readable JSON (instance + lowerBound + solution with full Gantt timing).
--load=V from file all Override the total load V declared in the instance file.
--installments=N 5 GA, exact, optv Search depth for branch-and-bound / maximum installments per processor in GA.
--repeats=0|1 1 exact, optv Whether a processor may appear more than once in the activation sequence.
--backend=NAME simplex GA, best-rate, exact LP back-end used by the schedule evaluator: simplex (built-in) or highs.
--deadline=T (none) optv, fptas-optv Time deadline T for the load-maximisation problem (required by OptV and FPTAS OptV).
--epsilon=E 0.1 fptas-optv, fptas-optt Approximation precision ε for the FPTAS schemes.
--nodes=N 0 (unlimited) exact Branch-and-bound node budget; 0 means exhaustive (no limit).
--cost=G (none) GA, best-rate, exact Bi-criteria cost cap: minimise makespan subject to total cost ≤ G.
--seed=S (random) GA RNG seed for reproducible genetic-algorithm runs.
--chunk=gss|ssc gss online Self-scheduling chunk rule: GSS (guided, geometric) or SSC (fixed minimum).
--psr=RULE all online Processor sorting rule: all · compute · comm · startup · memory · energy.