Linear & LOB Scheduling

Location-Based Scheduling · Repetitive Work · LSM / LOB / RSM

Construction · Schedule & Sequence · Tactical

When the same package of work is repeated across many locations — highway km-posts, high-rise floors, pipeline segments, train-station platforms — the dominant scheduling concern shifts from activity makespan to crew continuity: no gaps, no waiting, no expensive demobilisation-remobilisation of specialty crews. Classical RCPSP is poorly suited to this. The Line-of-Balance (LOB) method (borrowed from manufacturing production control) and the Linear Scheduling Method (LSM) — formalised by Harris & Ioannou (1998) as the Repetitive Scheduling Method — draw each crew as a line on a location-time diagram and enforce that no two crews cross at the same location.

Where This Decision Fits

Repetitive-project scheduling — the highlighted step is what this page optimises

Project TypingIs it repetitive?

→

Crew AssemblyProductivity rates

→

Linear SchedulingLocation-time plan

→

Continuity CheckNo crew gaps

→

ExecuteMonitor, re-pace

The Problem

Continuous-crew scheduling across a set of repetitive locations

A project has $ n $ activities indexed by $ i \in \{1, \ldots, n\} $ and $ L $ repetitive locations indexed by $ \ell \in \{1, \ldots, L\} $ (km-posts, floors, station platforms). Each activity $ i $ has a dedicated crew whose productivity rate $ \rho_i $ is expressed as locations-per-day (e.g., a paving crew lays 1.5 km/day). The time to complete activity $ i $ at one location is $ p_i = 1/\rho_i $ days.

The schedule is a set of start times $ s_{i,\ell} $ that satisfies:

LSM / LOB formulation $$ \min \; s_{n,L} + p_n \qquad \text{(project duration)} $$ $$ \text{s.t.} \quad s_{i,\ell+1} \;\ge\; s_{i,\ell} + p_i \qquad \forall i, \; \ell = 1, \ldots, L-1 \qquad \text{(crew sequence)} $$ $$ s_{j,\ell} \;\ge\; s_{i,\ell} + p_i \qquad \forall (i,j) \in \mathcal{E}, \; \forall \ell \qquad \text{(technological precedence within a location)} $$ $$ s_{i,\ell+1} \;=\; s_{i,\ell} + p_i \qquad \text{if crew continuity required (no gaps)} $$ $$ s_{i,\ell} \;\ge\; 0 \qquad \forall i, \ell $$

Plotted on a location-time diagram (time on x, location on y), each crew draws a line whose slope equals its productivity $ \rho_i $. Crews must not cross at the same location: the faster crew catches the slower one, and either the slower one has to accelerate, or a buffer (time or location gap) must be inserted to prevent the collision.

Harris & Ioannou (1998) showed that the crew-continuous project duration equals the finish time of the controlling sequence — the longest chain of activities where each consecutive pair is limited either by technological precedence at some location or by the slower crew rate. The RSM algorithm identifies this sequence in $ O(n^2 L) $ time and places activities accordingly.

See base RCPSP — the non-repetitive parent formulation

Try It Yourself

Tune crew productivity rates and watch the location-time diagram re-pace

Linear Scheduling Diagram

4 Crews · 10 Locations

Choose a Scenario

Crew Productivity Rates

Adjust rates to see how crew-interference buffers shift. Click Solve to re-plan.

Location-Time Diagram

Each colored line is a crew. Slope = productivity. Gaps between successive crews indicate buffer or idle time.

Pick a scenario and click Solve.

The Algorithms

From graphical LOB to the Repetitive Scheduling Method

Graphical

Line-of-Balance (LOB)

O(n L) — hand-drawable for small n

The original LOB (borrowed from 1950s manufacturing production control) plots each crew's progress as a straight line on the location-time plane. Crews that would otherwise collide are manually offset with time buffers. Pedagogically beautiful, still used in the field as a communication tool between PM and superintendents.

Exact

Repetitive Scheduling Method (RSM)

O(n\u00b2 L) — identifies controlling sequence

Harris & Ioannou (1998) recast LSM as a forward pass that identifies the controlling crew (or sequence) at each location. At every crew boundary the algorithm checks whether precedence forces a shift — at worst, the controlling sequence switches. The output is the minimum project duration with all crews continuous. This is the algorithm implemented on this page.

LP / MIP

Arditi-Tokdemir LP Formulation

O(n L) variables + precedence constraints

Arditi, Tokdemir & Suh (2002) wrote the LSM as a continuous LP: minimise project duration s.t. crew-sequence and technological-precedence inequalities. For the basic crew-continuous case the LP is polynomial. The extension to variable productivity (learning curves) and interruptible crews requires an MIP — a good setting for Vanhoucke (2006)'s scatter search.

Real-World Complexity

Why repetitive-project scheduling needs more than LOB lines

Beyond Textbook LSM

Learning curves — Crews get faster on later units (Wright's law, $ T_n = T_1 n^{-b} $). A straight line overstates time at early units and understates at later ones; piecewise-linear or curved activity lines are the fix.
Unequal locations — Not all km-posts are equal (bridges, tunnels, overpasses take longer than plain roadway). Activity duration becomes location-specific $ p_{i,\ell} $.
Crew interruption vs. continuity — Some crews can be idled cheaply (standard labour); specialty crews (tunnelling rigs) cannot. Mixed-continuity objectives need MIP.
Weather windows — Outdoor activities (paving, concrete pours) have seasonal availability. The LSM line becomes discontinuous at weather boundaries.
Multiple shifts per crew — Double shifts increase productivity but increase cost — a TCTP overlay on LSM.
Location-based risk (LBM) — Kenley & Seppänen (2010)'s Location-Based Management System adds risk analysis per location: a delay at one bridge cascades only through locations downstream of the bridge.

Related Scheduling Variants

LSM is the repetitive branch of the construction-OR tree

RCPSP — non-repetitive projects. When every activity happens once, the location-axis collapses and LSM reduces to RCPSP. → Open Project Scheduling

Time-Cost Tradeoff / MRCPSP. Each crew can operate in single-shift, overtime, or double-shift mode. Shift mode becomes a TCTP overlay on the LSM rate. → Open Time-Cost Tradeoff

Stochastic RCPSP. Crew productivity has variance. Stochastic LSM adds Monte Carlo on top of the controlling-sequence algorithm. → Open Stochastic RCPSP

Resource Leveling. LSM already smooths resource peaks by construction (continuous crews). Applying standard levelling to a LSM schedule is usually a no-op. → Open Resource Leveling

Precast / Prefabrication Scheduling. Production lines in precast yards are LSM-native: each unit passes through fixed stations in sequence. → Open Precast Scheduling

Location-Based Management (LBM). Seppänen & Kenley (2005) extend LSM with location-specific risk, cost, and quality; active research in Nordic construction.

Key References

Cited above · DOIs & permanent URLs

Harris, R. B., & Ioannou, P. G. (1998).

“Scheduling projects with repeating activities.”

Journal of Construction Engineering and Management, 124(4), 269–278. (The Repetitive Scheduling Method, formal LSM algorithm.) doi:10.1061/(ASCE)0733-9364(1998)124:4(269)

Russell, A. D., & Wong, W. C. M. (1993).

“New generation of planning structures.”

Journal of Construction Engineering and Management, 119(2), 196–214. (Early integration of repetitive and network-based scheduling.) doi:10.1061/(ASCE)0733-9364(1993)119:2(196)

Arditi, D., Tokdemir, O. B., & Suh, K. (2002).

“Challenges in line-of-balance scheduling.”

Journal of Construction Engineering and Management, 128(6), 545–556. (LP formulation and practical LOB issues.) doi:10.1061/(ASCE)0733-9364(2002)128:6(545)

El-Rayes, K., & Moselhi, O. (2001).

“Optimizing resource utilization for repetitive construction projects.”

Journal of Construction Engineering and Management, 127(1), 18–27. (Crew interruption vs. continuity optimisation.) doi:10.1061/(ASCE)0733-9364(2001)127:1(18)

Vanhoucke, M. (2006).

“Work continuity constraints in project scheduling.”

Journal of Construction Engineering and Management, 132(1), 14–25. (Scatter search for LSM under continuity constraints.) doi:10.1061/(ASCE)0733-9364(2006)132:1(14)

Kenley, R., & Seppänen, O. (2010).

Location-Based Management for Construction: Planning, Scheduling and Control.

Spon Press. (The LBM methodology — LSM extended with location-specific risk and cost.) doi:10.4324/9780203030417

Johnston, D. W. (1981).

“Linear scheduling method for highway construction.”

Journal of the Construction Division, 107(2), 247–261. (Early American introduction of LSM for highway work.)

Lumsden, P. (1968).

The Line of Balance Method.

Pergamon Press. (Classic textbook; the engineering adoption of LOB from manufacturing.)

Hartmann, S., & Briskorn, D. (2022).

“An updated survey of variants and extensions of the resource-constrained project scheduling problem.”

European Journal of Operational Research, 297(1), 1–14. (Repetitive / location-based variants surveyed in the classification.) doi:10.1016/j.ejor.2021.05.004

Planning a repetitive project?

Highway paving, high-rise construction, pipelines and tunnels — linear scheduling turns repetitive work into a single-glance location-time plan that communicates up, down, and sideways. Let's discuss how Operations Research can sharpen your repetitive-project planning.

Connect on LinkedIn

Disclaimer

Crew productivity rates and location counts are illustrative values chosen to demonstrate the LSM/LOB algorithms. Real repetitive-construction projects involve per-location variability, learning curves, and weather constraints not captured in the simple model shown here.