BlyxDocumentation
Browse chapters
Documentation / Workflow recipes

Albatross · Estimate a build's critical-path lower bound

Estimate a build forest's scheduling lower bound from dependencies and worker capacity.

Estimate a build's critical-path lower bound

Adding workers cannot shorten a serial dependency chain. Compare total work with the longest dependency path before sizing a build pool. The four stages take eleven units of serial work. A dependency chain takes eight, so two workers cannot finish sooner than eight.

Run the framework with your own input

Install Blyx 0.2.1 and a Rust toolchain with a host linker, then run the versioned project. Each positional argument is a number or a comma-separated numerical vector. The CLI accepts up to 16 entries per vector. The imported module accepts longer inputs.

git clone --depth 1 --branch v0.1.0 https://github.com/Rahulchaube1/blyx-albatross.git
cd blyx-albatross
blyxc native-run project.blyx -- "-1,0,0,2" "1,3,2,5" 2

API and return values

Returns [critical path, total work, lower bound with given workers, deepest stage count]. The capacity bound assumes divisible worker time; actual nonpreemptive schedules can take longer. Invalid input returns an empty vector.

ArgumentAccepted input
parentsVector of: exact signed integer
durationsVector of: nonnegative finite number
workerspositive exact integer

Use the libraries independently

The framework vendors the same library source published in these two repositories. Each module has its own package page, input contract and regression suite.

Try the program

Output Ready
Expected output
8
11
8
3
Open in the full playground →

Practice

Change parents = [-1, -1, -1], durations = [5, 5, 5], workers = 1.0. Predict the result, then run the program.

Hint

Returns [critical path, total work, lower bound with given workers, deepest stage count]. The capacity bound assumes divisible worker time; actual nonpreemptive schedules can take longer.

Worked solution

The result vector is [5, 15, 15, 1]. Compare its fields with the return layout in the API section.

Find

    let parents = [-1, 0, 0, 2];

Replace with

    let parents = [-1, -1, -1];

Find

    let durations = [1, 3, 2, 5];

Replace with

    let durations = [5, 5, 5];

Find

    let workers = 2.0;

Replace with

    let workers = 1.0;

Output after the change

5
15
15
1