Crew Task Assignment
Generalized Assignment Problem · NP-Hard
Construction · Resource & Workforce · TacticalMismatched crew-to-task assignments waste 12–18% of daily labor hours on construction sites through skill gaps, travel between zones, and idle time between tasks. Every morning, a site foreman must assign 8–15 specialized crews to 20–30 tasks across multiple building zones. This is the Generalized Assignment Problem — NP-hard — where each crew has limited capacity and different efficiency on different task types.
The Problem
Site Operations · Crew Assignment
On a large construction site, each morning begins with a critical planning session: which crew handles which tasks? The site foreman must balance crew skill types (concrete, steel, electrical, plumbing, carpentry, painting, HVAC, glazing), daily hour capacities, task skill requirements, and zone locations across the site. Unlike the Linear Assignment Problem where each agent gets exactly one task, the GAP allows multiple tasks per crew subject to capacity constraints — making it NP-hard.
The cost of assigning task j to crew i captures the skill mismatch penalty (high when a crew lacks the required trade), a zone travel cost, and a productivity factor based on crew experience with that task type. Each crew has a limited number of daily hours, and every task must be assigned to exactly one qualified crew.
| OR Concept | Construction Mapping |
|---|
subject to
Σj aij · xij ≤ bi // crew i capacity (daily hours)
Σi xij = 1 // each task assigned to exactly one crew
xij ∈ {0, 1} // binary assignment decision
Where cij is the cost of assigning task j to crew i, aij is the hours required, and bi is crew i’s daily hour capacity.
See full Assignment Problem theoryTry It Yourself
Assign crews to tasks and compare algorithms
Crew Task Assignment Optimizer
8 Crews · 20 TasksReady. Select a scenario and click Solve.
| Algorithm | Total Cost | Feasible | Time |
|---|
The Algorithms
From relaxation-based bounds to local search improvements
Hungarian Relaxation (LAP Relaxation)
O(n³) relaxed | Provides lower boundRelax the capacity constraints and solve the resulting Linear Assignment Problem using the Hungarian algorithm. This gives a lower bound on the optimal GAP cost. If the LAP solution happens to satisfy all capacity constraints, it is also optimal for the GAP. Otherwise, the gap between the LAP bound and the best feasible solution quantifies how much the capacity constraints cost.
For construction scheduling, the relaxation often reveals which crews are over-committed, guiding the foreman toward capacity-feasible adjustments.
Greedy Assignment
O(n · m · log(n · m)) | No optimality guaranteeSort all crew-task pairs by cost (ascending). Iterate through the sorted list: assign a task to a crew if the crew is qualified and has remaining capacity. This greedy approach is fast and produces a feasible solution, but it can miss globally better assignments by committing to locally cheap pairs too early.
In practice, greedy often performs within 10–20% of optimal for well-structured instances, but can degrade significantly when crew capacities are tight and skill requirements are heterogeneous — common on multi-trade construction sites.
Local Search (Swap Neighborhood)
O(k · n · m) per iteration | Improves feasible solutionStarting from the greedy solution, iteratively try swapping task assignments between two crews. A swap is accepted if it reduces total cost while maintaining feasibility (both crews remain within capacity). The search continues until no improving swap exists or a maximum iteration count is reached.
Swap-based local search is the workhorse of practical GAP solvers. It typically closes 30–60% of the gap between greedy and optimal, runs in milliseconds, and is easy for site managers to understand and trust.
Real-World Complexity
Why construction crew assignment goes beyond a simple cost matrix
Beyond the Assignment Matrix
- Multi-skill crews — Some crews carry secondary skills (e.g., a concrete crew that can also do formwork); exploiting secondary skills increases flexibility but complicates the cost model
- Precedence constraints — Structural steel must precede cladding; electrical rough-in precedes drywall. Task ordering limits which assignments are feasible on a given day
- Zone congestion — Assigning too many crews to the same zone causes physical congestion, crane conflicts, and safety hazards
- Weather dependencies — Exterior tasks (glazing, roofing, concrete pours) are weather-sensitive; the foreman may need to reassign crews mid-day when conditions change
- Overtime and subcontracting — When in-house capacity is insufficient, the foreman must decide between overtime (1.5× cost) and subcontractor call-up (2× cost, lead time)
Related Resource & Scheduling Variants
Crew assignment sits between project scheduling and resource leveling
Key References
Foundational works in assignment and construction scheduling
Need to optimize your construction operations?
From crew assignment to project scheduling and resource leveling, mathematical modeling can transform site productivity. Let’s discuss how Operations Research can work for your organization.