Job Assignment (Assignment Problem) - Handbook

Type: BIP (Binary Integer Programming)

This handbook explains the Job Assignment sample problem in the LP Black Box platform.

This is the classic "Assignment Problem" - optimally assign workers to jobs.

---

The Problem

Scenario

Assign 4 workers to 4 jobs. Each worker has different skills, so their productivity varies per job. We want to maximize total productivity.

Worker	Job A	Job B	Job C	Job D
Worker 1	85	70	90	65
Worker 2	75	80	70	85
Worker 3	90	75	80	70
Worker 4	60	85	75	80

Each worker can do exactly one job, and each job needs exactly one worker.

Your Goal

Maximize total productivity by assigning the best worker to each job.

The Key: Binary Variables

Each assignment is either:

• 1 - Worker is assigned to this job
• 0 - Worker is not assigned to this job

Each row and column must have exactly one "1".

The Variables

Variable	Type	Meaning
w1_jobA	Binary (0 or 1)	Worker 1 → Job A
w1_jobB	Binary (0 or 1)	Worker 1 → Job B
w1_jobC	Binary (0 or 1)	Worker 1 → Job C
w1_jobD	Binary (0 or 1)	Worker 1 → Job D
w2_jobA	Binary (0 or 1)	Worker 2 → Job A
...	...	...

The Constraints

1. Each worker does one job:

   • w1_jobA + w1_jobB + w1_jobC + w1_jobD = 1
   • w2_jobA + w2_jobB + w2_jobC + w2_jobD = 1
   • w3_jobA + w3_jobB + w3_jobC + w3_jobD = 1
   • w4_jobA + w4_jobB + w4_jobC + w4_jobD = 1

2. Each job has one worker:

   • w1_jobA + w2_jobA + w3_jobA + w4_jobA = 1
   • w1_jobB + w2_jobB + w3_jobB + w4_jobB = 1
   • w1_jobC + w2_jobC + w3_jobC + w4_jobC = 1
   • w1_jobD + w2_jobD + w3_jobD + w4_jobD = 1

The Objective

Maximize: Sum of productivity scores for all assignments

---

How to Use

Step 1: Load the Sample

Select Job Assignment from the dropdown.

Step 2: Solve

The solver finds the optimal assignment (which worker goes to which job).

Step 3: Interpret Results

• Variable = 1 means "assign this worker to this job"
• The constraint ensures each worker does exactly one job

---

Try It Yourself

• Add a constraint that Worker 1 must do Job A or Job B
• Add a constraint that Worker 3 cannot do Job D
• Change to minimize cost (use negative coefficients)

---

Real-World Applications

• Employee Scheduling: Assign workers to shifts
• Task Allocation: Assign tasks to team members
• Vehicle Routing: Assign vehicles to routes
• Sports Lineups: Assign players to positions
• Project Assignment: Assign projects to teams

---

This demonstrates the classic Assignment Problem - finding the best one-to-one matching between two sets.