Lesson 5: Allocation problems and bipartite graphs

The quickest allocation by listing every possibility

SkillsAssignment by inspectionBipartite graphs and allocation tables

Worked example

  • Simple familiar

Three technicians, Ari, Bea and Cam, each quote a time in minutes to do three repair jobs.

Job 1Job 2Job 3
Ari1267
Bea111314
Cam8812

Each technician does one job. By inspection, find the allocation that gives the smallest total time.

1 of 3 steps
  1. Step 1: Count the allocations

    Ari has 3 choices, then Bea 2, then Cam 1: 3×2×1=63 \times 2 \times 1 = 6 allocations.

Try a similar one

A fresh question of the same kind, checked as you answer, with hints and a full solution.

Method

  1. List every allocation systematically (n!n! of them).

  2. Total each one.

  3. 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.

Save your progress with a free account