← Back to the line balancer

How the line balancer works

A line makes one unit every cycle time. Takt is the cycle the customer sets: the production time you have in a period divided by the units needed in it, so 27,000 seconds for 450 units is a 60-second takt. Each task has a time and a list of tasks that must be done before it. A balance puts every task in a station, in order along the line, so that no station holds more work than the cycle time and no task sits upstream of something it depends on.

There are two classic questions, known in the literature as the simple assembly line balancing problem (SALBP). Type 1 fixes the cycle time and asks for the fewest stations, which is the number of operators on a one-person-per-station line. Type 2 fixes the stations and asks for the shortest cycle, the most output from the people you have. Both are NP-hard, so a solver either searches cleverly or settles for a rule of thumb.

1. Lower bounds: how few stations could possibly do

The bounds and the earliest and latest station of each task follow those collected by Scholl and Klein (1997, INFORMS Journal on Computing 9(4), the SALOME paper).

2. A quick balance from priority rules

Fill each station in turn with the highest-priority task that is ready and still fits, and open a new station when nothing fits. The page tries four priorities: ranked positional weight (a task's time plus the time of everything after it; Helgeson and Birnie, 1961), number of followers, longest task, and longest path to the end of the line. It runs each one forwards and also on the line reversed (filling from the last station back), and keeps the best. These are the methods most courses teach, and they are often optimal. When they are not, they are a station or two off, and nothing tells you which case you are in.

3. The exact search, and when it says "proved"

Starting from the lower bound, the page asks: is there a balance with this many stations? The first count with a yes is optimal. Each question is answered by searching station by station:

If the search finishes, the answer is proved: no balance with fewer stations exists for the times and precedences typed. If the time limit runs out first, the page shows the best balance found and the count it has proved is needed. It never calls an unfinished answer optimal. Type 2 uses the same yes-or-no search inside a binary search on the cycle time, which works because a balance that fits one cycle time also fits any longer one.

4. How it did on the standard benchmark

Armin Scholl's 1993 data set is the standard test for line balancing: 269 type 1 problems on 25 precedence graphs from 7 to 297 tasks, drawn from industry and from the literature. The published optima are on assembly-line-balancing.de. bench/scholl.mjs reads the data set's zip as published and runs the engine on every problem with the page's default limit of 4 seconds. It checks every balance with code separate from the solver, and writes bench/salbp1.md.

SALBP-1, 4 s per problemProblems
Same station count as the published optimum258 of 269
Proved optimal by this engine within the limit249 of 269
More stations than the published optimum10
Fewer stations than the published optimum (would mean a bug)0

The ten misses are on the hardest graphs: six on Scholl's own 297-task graph (one station over each), two on Barthol2 (148 tasks, two stations over) and two on Wee-Mag (75 tasks, one over). On each of them the page says "best found" and gives the proved bound, so you know to raise the time limit or look harder. One more Wee-Mag problem (cycle 47) is listed on the site as still open between 32 and 33 stations; the engine finds 33 and cannot close it either. Published exact methods do better on these hard graphs. The point of the table is that you can see exactly where this one stands.

The same data set has 302 type 2 problems (a number of stations given, the shortest cycle wanted). At 4 seconds each the engine gave the published optimal cycle time on 256 of 302 and proved it optimal on 251 of 302. It was longer on 42, and shorter on none (bench/salbp2.md). Type 2 is harder for this engine, likely because each step of its binary search on the cycle time is a full yes-or-no search of its own.

5. What it does not model

This is the simple problem: one product, fixed task times, one operator per station, no parallel stations, no zoning (tasks that must or must not share a station), no tool or space limits, no ergonomic load. On a real line those often decide the balance. Use this answer as a lower limit and a first layout, and check it on the floor.