🧩 Constraint Solving POTD:Problem of the Day: Assembly Line Balancing Problem

[github-actions[bot]]

Problem Statement

The Assembly Line Balancing Problem (ALBP)

Imagine you're designing a manufacturing assembly line for smartphones. The production process consists of a sequence of tasks (e.g., "solder circuit board", "attach LCD screen", "test camera module"). Each task:

• Has a fixed duration (in seconds)
• May depend on other tasks being completed first (precedence constraints)

Your goal is to assign tasks to workstations arranged in a line such that:

1. All precedence constraints are satisfied
2. The total time at each station (the "cycle time") does not exceed a target throughput time
3. The number of workstations is minimized (or the cycle time is minimized, depending on variant)

Small Concrete Instance

Tasks: A(10s), B(15s), C(12s), D(8s), E(20s), F(14s)
Precedences: A → B, A → C, B → D, C → E, D → F, E → F
Target Cycle Time: 25s

Question: Assign tasks to stations to minimize the number of stations.

Solution sketch:

• Station 1: A (10s)
• Station 2: B, C (15+12 = 27s... exceeds 25s!)
• Revised:
  • Station 1: A (10s)
  • Station 2: B, D (15+8 = 23s) ✓
  • Station 3: C (12s)
  • Station 4: E, F (20+14 = 34s... exceeds!)
  • Revised again:
    • Station 1: A (10s)
    • Station 2: B, D (23s)
    • Station 3: C (12s)
    • Station 4: E (20s)
    • Station 5: F (14s)

Minimum 5 stations required for this instance.

---

Why It Matters

Manufacturing & Production: Assembly line balancing directly impacts production cost and throughput. Every additional workstation means more equipment, floor space, labor, and overhead. Reducing from 10 stations to 8 can save hundreds of thousands of dollars for high-volume production.

Logistics & Workflow Design: Beyond factories, ALBP appears in software development pipelines, medical lab workflows, and food processing lines wherever sequential tasks must be distributed across parallel resources.

---

Modeling Approaches

Approach 1: Constraint Programming (CP) Model

Decision Variables:

• s_i ∈ {1..m} — the station assigned to task i (where m is the number of stations)
• c ∈ R+ — the cycle time (makespan)

Constraints:

1. Precedence: s_i ≤ s_j − 1  ∀ (i → j) ∈ precedences
2. Cycle time: Σ(d_i : task i in station k) ≤ c  ∀ stations k
3. Objective: minimize m  (or fix m and minimize c)

Strengths:

• Naturally expresses precedence via cumulative workload constraints
• Global constraints like cumulative or disjunctive can propagate tightly

Weaknesses:

• Station indices are symmetric (many equivalent solutions) → need symmetry breaking
• Propagation alone rarely finds optimal solutions; requires search

Approach 2: Mixed Integer Programming (MIP) Model

Decision Variables:

• x_{i,k} ∈ {0,1} — binary: task i assigned to station k
• c ∈ R+ — cycle time

Constraints:

1. Assignment:  Σ_k x_{i,k} = 1  ∀ tasks i
2. Precedence:  Σ_{j ≤ k} x_{j,k} ≥ Σ_{j ≤ k} x_{i,k}  ∀ (i → j) ∈ precedences, ∀ k
3. Capacity:    Σ_{i: i in k} d_i ≤ c  ∀ stations k
4. Objective:   minimize m  (count stations with ≥1 task) or minimize c

Strengths:

• Linear formulation → can leverage powerful MIP solvers (CPLEX, Gurobi)
• Good relaxation bounds and cutting planes

Weaknesses:

• More variables/constraints than CP; slower for large instances
• Less direct encoding of the problem structure

Example MiniZinc Model

int: n_tasks;
int: max_stations = n_tasks;  % upper bound
array[1..n_tasks] of int: duration;
array[1..n_tasks, 1..n_tasks] of int: precedence;  % adjacency matrix

var 1..max_stations: station[1..n_tasks];
var 0..max(duration)*n_tasks: cycle_time;
var 0..n_tasks: n_stations;

constraint forall(i, j in 1..n_tasks where precedence[i,j] = 1) (
  station[i] < station[j]
);

constraint forall(k in 1..max_stations) (
  sum(i in 1..n_tasks where station[i] = k) (duration[i]) <= cycle_time
);

constraint n_stations >= max(station);

solve minimize n_stations;

---

Key Techniques

1. Symmetry Breaking

Station indices are interchangeable (Station 1 ≠ Station 2 is arbitrary). Solutions with tasks {A,B,C} on station 5 and {D} on station 8 are equivalent to many relabelings. To prune the search space:

• Impose lexicographic ordering: station[i] ≤ station[i+1] for some task ordering
• Use bin-based branching: assign tasks to lowest-indexed available station first

2. Precedence-Based Bounds

Compute a critical path through the precedence DAG:

• The critical path length is a lower bound on cycle time
• The critical path width (maximum parallelism) is a lower bound on the number of stations
• Use these bounds to prune infeasible search branches early

3. Guided Local Search & Metaheuristics

Exact algorithms struggle on large instances (hundreds of tasks). Many practitioners use:

• Greedy assignment + local improvement: Start with a simple greedy assignment (e.g., longest task first), then iteratively move tasks between stations to reduce imbalance
• Genetic algorithms: Evolve station assignments over generations
• Tabu search: Explore neighborhood moves while avoiding recently visited configurations
• Hybrid CP/Local Search: Use CP to verify feasibility; local search to improve solutions

---

Challenge Corner

Extension questions for you to explore:

1. Reducing the Search Space:
   How would you add constraints to break symmetry beyond lexicographic ordering? (Hint: think about task sequence within a station—does it matter?)

2. Handling Uncertainty:
   In real factories, task durations vary (e.g., ±10% due to fatigue, equipment wear). How would you model and optimize for robust balancing—a solution that remains feasible even if some tasks take longer?

3. Multiple Objective Trade-offs:
   Modern assembly lines care about both the number of stations AND cycle time. How would you formulate a multi-objective variant and explore the Pareto frontier?

---

References

1. Scholl, A., & Becker, C. (2006). "State-of-the-art exact algorithms for the simple assembly line balancing problem." Journal of Heuristics, 12(5), 409–419.
   → Comprehensive survey of exact and heuristic methods.

2. Boysen, N., Fliedner, M., & Scholl, A. (2007). "A classification of assembly line balancing problems." European Journal of Operational Research, 183(2), 674–693.
   → Taxonomy of ALBP variants (SALBP, GALBP, MALBP).

3. Rossi, F., van Beek, P., & Walsh, T. (eds.) (2006). Handbook of Constraint Programming. Elsevier.
   → Chapter 28: industrial applications and global constraints (especially cumulative and circuit constraints).

4. OR-Tools Assembly Line Balancing Examples: (developers.google.com/redacted)
   → Practical MIP and CP formulations with solver implementation.

---

Happy constraint solving! 🧩 If you've tackled assembly line balancing in your work, share your approach or favorite modeling trick in the comments below.

Generated by 🧩 Constraint Solving — Problem of the Day · copilot · haiku45 · ~8 AIC · ⌖ ~11 AIC · ⊞ 7.1K · ◷

• expires on Nov 9, 2026, 3:31 AM UTC-08:00

[github-actions[bot]]

This discussion has been marked as outdated by Constraint Solving — Problem of the Day.

A newer discussion is available at Discussion #74505.