Especially when scheduling employees, the workload needs to be spread out fairly.
Easier said than done. Let’s take a look at this challenging problem.
15
undesirable tasks to 5
employees.Each task takes a day, but they have different skill requirements.
What is fair?
3
tasks,because the mean (= average) is
15 / 5 = 3
.Or explained more formally, for the math geeks:
- Mean (= average): (overline{x} = frac{sum_{i=1}^{n} x_i}{n})
For example, there are 7 tasks that require a skill which only Ann and Beth posses.
One of them will have to do at least 4 tasks.
What is fairer?
- A schedule is fair if most users think it is fair to them.
- A schedule is fair if the employee with most tasks has as little tasks as possible.
Besides, if we make almost everyone happy by letting Ann do all the work, she would probably quit on us.
That wouldn’t help.
Number of tasks per employee | Quality | Measurement of fairness | |||||
---|---|---|---|---|---|---|---|
Ann | Beth | Carl | Dan | Ed | Mean | ||
Schedule A | 3 | 3 | 3 | 3 | 3 | Fair | 3 |
Sorting solutions by fairness
Each one has
15
undesirable tasks:Number of tasks per employee | Quality | |||||
---|---|---|---|---|---|---|
Ann | Beth | Carl | Dan | Ed | ||
Schedule | 15 | 0 | 0 | 0 | 0 | Unfair. Ann quits her job. |
Several of these are probably infeasible, due to hard constraints such as skill requirements.
Number of tasks per employee | Quality | |||||
---|---|---|---|---|---|---|
Ann | Beth | Carl | Dan | Ed | ||
Schedule A | 3 | 3 | 3 | 3 | 3 | Fairest |
Schedule B | 4 | 4 | 3 | 2 | 2 | |
Schedule C | 5 | 3 | 3 | 2 | 2 | |
Schedule D | 5 | 5 | 2 | 2 | 1 | |
Schedule E | 6 | 3 | 3 | 2 | 1 | |
Schedule F | 6 | 5 | 2 | 1 | 1 | |
Schedule G | 11 | 1 | 1 | 1 | 1 | Unfairest |
And we minimize her tasks.
Measuring unfairness
The lower, the fairer. How do we calculate that number? Let’s look at some formula’s:
Deviation from the mean
what if we simply sum the difference with the mean per employee?
- Absolute deviation from the mean: (f(n) = sum_{i=1}^{n} |x_i – overline{x}|)
- Average deviation from the mean: (f(n) = frac{sum_{i=1}^{n} |x_i – overline{x}|}{n})
Number of tasks per employee | Quality | |||||
---|---|---|---|---|---|---|
Ann | Beth | Carl | Dan | Ed | ||
Schedule C | 5 | 3 | 3 | 2 | 2 | More fair |
Schedule D | 5 | 5 | 2 | 2 | 1 | Less fair |
Both claim that schedule D is worse than E. It’s not: just ask Ann.
Variance and standard deviation
That sounds like exactly what we need:
- Variance: (f(n) = frac{sum_{i=1}^{n} (x_i – overline{x})^2}{n})
- Standard deviation: (f(n) = sqrt{frac{sum_{i=1}^{n} (x_i – overline{x})^2}{n}})
- Squared deviation from the mean (= variance * n): (f(n) = sum_{i=1}^{n} (x_i – overline{x})^2)
- Root of squared deviation from the mean: (f(n) = sqrt{sum_{i=1}^{n} (x_i – overline{x})^2})
Number of tasks per employee | Measurement of fairness | ||||||
---|---|---|---|---|---|---|---|
Ann | Beth | Carl | Dan | Ed | Absolute deviation | Average deviation | |
Schedule A | 3 | 3 | 3 | 3 | 3 | 0 | 0.00 |
Schedule B | 4 | 4 | 3 | 2 | 2 | 4 – Bad | 0.80 – Bad |
Schedule C | 5 | 3 | 3 | 2 | 2 | 4 | 0.80 |
Schedule D | 5 | 5 | 2 | 2 | 1 | 8 – Very bad | 1.60 – Very bad |
Schedule E | 6 | 3 | 3 | 2 | 1 | 6 | 1.20 |
Schedule F | 6 | 5 | 2 | 1 | 1 | 10 | 2.00 |
Schedule G | 11 | 1 | 1 | 1 | 1 | 16 | 3.20 |
They aren’t.
Maximum
- Maximum: (f(n) = underset{0 < i leq n}max x_i)
Number of tasks per employee | Measurement of fairness | ||||||||
---|---|---|---|---|---|---|---|---|---|
Ann | Beth | Carl | Dan | Ed | Variance | Standard deviation | Squared deviation | Root squared deviation | |
Schedule A | 3 | 3 | 3 | 3 | 3 | 0.00 | 0.00 | 0 | 0.00 |
Schedule B | 4 | 4 | 3 | 2 | 2 | 0.80 | 0.89 | 4 | 2.00 |
Schedule C | 5 | 3 | 3 | 2 | 2 | 1.20 | 1.10 | 6 | 2.45 |
Schedule D | 5 | 5 | 2 | 2 | 1 | 2.80 – Bad | 1.67 – Bad | 14 – Bad | 3.74 – Bad |
Schedule E | 6 | 3 | 3 | 2 | 1 | 2.80 | 1.67 | 14 | 3.74 |
Schedule F | 6 | 5 | 2 | 1 | 1 | 4.40 | 2.10 | 22 | 4.69 |
Schedule G | 11 | 1 | 1 | 1 | 1 | 16.00 | 4.00 | 80 | 8.94 |
Furthermore, it completely discards fairness between the remaining employees.
That might be ok if there’s one employee, but not if there are thousands.
List of maximums
Number of tasks per employee | Measurement of fairness | |||||
---|---|---|---|---|---|---|
Ann | Beth | Carl | Dan | Ed | Maximum | |
Schedule A | 3 | 3 | 3 | 3 | 3 | 3 |
Schedule B | 4 | 4 | 3 | 2 | 2 | 4 |
Schedule C | 5 | 3 | 3 | 2 | 2 | 5 – Bad |
Schedule D | 5 | 5 | 2 | 2 | 1 | 5 |
Schedule E | 6 | 3 | 3 | 2 | 1 | 6 – Bad |
Schedule F | 6 | 5 | 2 | 1 | 1 | 6 |
Schedule G | 11 | 1 | 1 | 1 | 1 | 11 |
this isn’t compatible with other soft constraints…
No constraint is an island
But there are other soft constraints that we’ll need to optimize for too,
so we’ll need to weight them against each other.
An example
that’s 10 times as important as a fairness violation.
Let’s also add a schedule with 1500 tasks, to see how it scales out:
Number of tasks per employee | Measurement of fairness | |||||
---|---|---|---|---|---|---|
Ann | Beth | Carl | Dan | Ed | List of maximums | |
Schedule A | 3 | 3 | 3 | 3 | 3 | [3,3,3,3,3] |
Schedule B | 4 | 4 | 3 | 2 | 2 | [4,4,3,2,2] |
Schedule C | 5 | 3 | 3 | 2 | 2 | [5,3,3,2,2] |
Schedule D | 5 | 5 | 2 | 2 | 1 | [5,5,2,2,1] |
Schedule E | 6 | 3 | 3 | 2 | 1 | [6,3,3,2,1] |
Schedule F | 6 | 5 | 2 | 1 | 1 | [6,5,2,1,1] |
Schedule G | 11 | 1 | 1 | 1 | 1 | [11,1,1,1,1] |
Represented by a single number
(because it uses multiple score levels),
so it’s difficult to mix in priority violations:
Number of tasks | Priority violations | Fairness violations | Soft score | Quality | |
---|---|---|---|---|---|
Schedule F | 15 | 1 | ? | ? | Best |
Schedule C | 15 | 2 | ? | ? | |
Schedule D | 15 | 2 | ? | ? | Worst |
Schedule X | 1500 | 100 | ? | ? | Different dataset |
Grow with the number of violations
we notice that maximum gets dwarfed by the priority violations:
Number of tasks | Priority violations | Measurement of fairness | Soft score | |
---|---|---|---|---|
List of maximums | ||||
Schedule F | 15 | 1 | [6,5,2,1,1] | ERROR? |
Schedule C | 15 | 2 | [5,3,3,2,2] | ERROR? |
Schedule D | 15 | 2 | [5,5,2,2,1] | ERROR? |
Schedule X | 1500 | 100 | [8,8,7,7,7,7,…] | ERROR? |
on bigger datasets too:
Number of tasks | Priority violations | Measurement of fairness | Soft score | |
---|---|---|---|---|
Maximum | ||||
Schedule F | 15 | 1 | 6 | 16 |
Schedule C | 15 | 2 | 5 | 25 |
Schedule D | 15 | 2 | 5 | 25 |
Schedule X | 1500 | 100 | 8 | 1008 – Dwarfed |
Do not grow exponentially with the number of violations
Squared deviation does that:
Number of tasks | Priority violations | Measurement of fairness | |||
---|---|---|---|---|---|
Average deviation | Variance | Standard deviation | |||
Schedule F | 15 | 1 | 2.00 | 4.40 | 2.10 |
Schedule C | 15 | 2 | 0.80 | 1.20 | 1.10 |
Schedule D | 15 | 2 | 1.60 | 2.80 | 1.67 |
Schedule X | 1500 | 100 | 1.50 – Dwarfed | 2.50 – Dwarfed | 1.58 – Dwarfed |
Conclusion
- absolute deviation from the mean which compares terribly for fairness
- root squared deviation which isn’t perfect but works well enough
- Root of squared deviation from the mean: (f(n) = sqrt{sum_{i=1}^{n} (x_i – overline{x})^2})
Number of tasks | Priority violations | Measurement of fairness | |
---|---|---|---|
Squared deviation | |||
Schedule F | 15 | 1 | 80 |
Schedule C | 15 | 2 | 6 |
Schedule D | 15 | 2 | 14 |
Schedule X | 1500 | 100 – Dwarfed | 10201 |
Additional notes
Part-time employees
for example if some employees work half as many hours as other employees,
multiply their number of tasks by the inverse of their FTE (full time equivalent)
before feeding into this formula.
can be handled in a similar fashion or with separate constraints, depending on the requirement.
Update
see this mathexchange answer,
but it might suffer from numerical instability and overflow.
Number of tasks | Priority violations | Measurement of fairness | Soft score | |
---|---|---|---|---|
Root squared deviation | ||||
Schedule F | 15 | 1 | 4.69 | 14.69 |
Schedule C | 15 | 2 | 2.45 | 22.45 |
Schedule D | 15 | 2 | 3.74 | 23.74 |
Schedule X | 1500 | 100 | 101.00 | 1101.00 |