Lesson 5: Allocation problems and bipartite graphs
The quickest allocation by listing every possibility
SkillsAssignment by inspectionBipartite graphs and allocation tables
Worked example
Three technicians, Ari, Bea and Cam, each quote a time in minutes to do three repair jobs.
| Job 1 | Job 2 | Job 3 | |
|---|---|---|---|
| Ari | 12 | 6 | 7 |
| Bea | 11 | 13 | 14 |
| Cam | 8 | 8 | 12 |
Each technician does one job. By inspection, find the allocation that gives the smallest total time.
Step 1: Count the allocations
Ari has 3 choices, then Bea 2, then Cam 1: allocations.
Step 2: List them systematically
Writing each as Ari's job, Bea's job, Cam's job:
- 1, 2, 3:
- 1, 3, 2:
- 2, 1, 3:
- 2, 3, 1:
- 3, 1, 2:
- 3, 2, 1:
Fixing Ari's job first, then Bea's, guarantees no allocation is missed or repeated.
Step 3: Choose the smallest
The smallest total is 26 minutes, and only one allocation gives it.
Answer
Ari – Job 3, Bea – Job 1, Cam – Job 2, for a minimum total of minutes.
Try a similar one
A fresh question of the same kind, checked as you answer, with hints and a full solution.
Method
List every allocation systematically ( of them).
Total each one.
Choose the smallest (or largest) total, and check whether more than one allocation gives it.
Watch out for
Giving Ari the quickest job (Job 2, 6 minutes) first. The best allocation gives Ari Job 3, because Bea is so much better at Job 1 than at Jobs 2 and 3.