Manufacturing Operations
Scheduling · Assembly · Maintenance · Location
Manufacturing is where operations research was born. The wartime production planning problems of the 1940s were the original motivating problems for linear programming and integer programming. Today, the questions have grown more complex: how to balance assembly lines with hundreds of tasks, how to schedule steel production across blast furnaces, how to cut raw materials with minimum waste.
Every factory embeds a family of NP-hard combinatorial problems. Assembly line balancing is a bin-packing variant. Steel production scheduling is a sequence-dependent job shop. Cutting stock is a one-dimensional bin packing with multiplicity. These problems have been studied continuously since the 1950s; the methods developed in manufacturing have propagated into every other domain.
The Simple Assembly Line Balancing Problem (SALBP-1) assigns tasks to workstations along a serial production line so that no station exceeds the cycle time and all precedence constraints are respected. Each task has a fixed processing time and a set of predecessors that must be completed before it can start. The goal is to minimise the number of stations — equivalently, to maximise line efficiency. SALBP-1 is NP-hard in the strong sense, yet heuristics like Kilbridge-Wester (column-based priority) and COMSOAL (randomised feasible sequencing) produce near-optimal solutions for industrial instances with hundreds of tasks.
Problem type: Bin-packing variant with precedence constraints. Assign n tasks to the minimum number of stations such that the total task time in each station does not exceed the cycle time C, and all precedence arcs are respected (if task i precedes task j, then station(i) ≤ station(j)).
s.t. Σi∈Sk t_i ≤ C ∀ station k // cycle time
station(i) ≤ station(j) ∀ (i,j) ∈ P // precedence
each task assigned to exactly one station
Assembly Line Solver
- Salveson, M. E. (1955). The assembly line balancing problem. Journal of Industrial Engineering, 6(3), 18-25. Published
- Scholl, A. & Becker, C. (2006). State-of-the-art exact and heuristic solution procedures for simple assembly line balancing. European Journal of Operational Research, 168(3), 666-693. Published
- Kilbridge, M. D. & Wester, L. (1961). A heuristic method of assembly line balancing. Journal of Industrial Engineering, 12(4), 292-298. Published
Steel production scheduling is a flexible job-shop problem with sequence-dependent setup times. Each heat of molten steel must pass through a fixed sequence of processing stages — Electric Arc Furnace (EAF), Ladle Furnace (LF), and Continuous Caster (CC) — with tight timing constraints between stages to prevent metal solidification. Different steel grades require different setup times when switching on the caster. The objective is to minimise total makespan while respecting machine capacity, grade-dependent sequencing, and thermal constraints that make buffer time between stages critical.
Problem type: Flexible job-shop with sequence-dependent setups. Schedule n heats across 3 stages (EAF → LF → CC) to minimise makespan, subject to machine capacity, no-wait constraints between stages, and grade-dependent setup times on the caster.
s.t. start(h,LF) ≥ end(h,EAF) // stage precedence
start(h,CC) ≥ end(h,LF) // stage precedence
start(h,LF) - end(h,EAF) ≤ Δ // no-wait thermal
gap(h_i,h_j,CC) ≥ setup(grade_i,grade_j) // seq-dep setup
Steel Scheduling Solver
- Tang, L., Liu, J., Rong, A., & Yang, Z. (2001). A review of planning and scheduling systems and methods for integrated steel production. European Journal of Operational Research, 133(1), 1-20. Published
- Cowling, P. & Rezig, W. (2000). Integration of continuous caster and hot strip mill planning for steel production. Journal of Scheduling, 3(4), 185-208. Published
The one-dimensional cutting stock problem (1D-CSP) arises whenever raw material comes in standard lengths (master rolls of paper, steel bars, timber logs) and customer orders require pieces of various shorter widths. The objective is to minimise the number of master rolls used — equivalently, minimise waste. This is a classic NP-hard problem first solved optimally by Gilmore & Gomory (1961) using column generation, where each column represents a cutting pattern and the LP relaxation is solved iteratively by generating new patterns via a knapsack subproblem. The First Fit Decreasing (FFD) heuristic provides a fast 11/9 OPT + 6/9 upper bound.
Problem type: One-dimensional bin packing with multiplicity. Cut demanded widths from master rolls of width W to minimise the total number of rolls used. Each roll can accommodate any combination of widths that fit within W. Column generation solves the LP relaxation optimally.
s.t. Σp a_ip · x_p ≥ d_i ∀ width i // demand
Σi w_i · a_ip ≤ W ∀ pattern p // roll capacity
x_p ≥ 0 // (LP relaxation; round up for IP)
Cutting Stock Solver
- Gilmore, P. C. & Gomory, R. E. (1961). A linear programming approach to the cutting-stock problem. Operations Research, 9(6), 849-859. Published
- Gilmore, P. C. & Gomory, R. E. (1963). A linear programming approach to the cutting stock problem — Part II. Operations Research, 11(6), 863-888. Published
- Vanderbeck, F. (2000). On Dantzig-Wolfe decomposition in integer programming and ways to perform branching in a branch-and-price algorithm. Operations Research, 48(1), 111-128. Published
All Manufacturing Applications
Browse the complete collection