Published in Blog
Load balancing and fairness in constraints
Discover how to bring fairness to your Timefold solution
Load balancing is a common constraint for many Timefold use cases. Especially when scheduling employees, the workload needs to be spread out fairly. For example, nurses in your hospital care that everyone works the same number of weekends, and there may even be legal requirements to that effect. Join us as we show you how to bring fairness to your Timefold solution.
Defining fairness
Fairness is a complex concept, and it is not always clear what is fair.
For example, let’s assign 15 undesirable tasks to five employees.
Each task takes a day, but the tasks have different skill requirements.
In a perfectly fair schedule, each employee will get three tasks,
because the average is 15 / 5 = 3.
Unfortunately, this doesn’t solve the entire problem, because there are other constraints.
For example, there are seven tasks that require a skill which only two of the employees possess.
One of them will have to do at least four tasks.
From the above, we can see that our schedule cannot be perfectly fair, but we can make it as fair as possible. We can define fairness in two opposing ways:
-
A schedule is fair if most users think it is fair to them.
-
A schedule is fair if the employee with the most tasks has as few tasks as possible.
Since we want to treat all employees equally, the second definition is correct. Besides, if we make almost everyone happy by letting one employee do all the work, that employee would probably quit, and that doesn’t help.
Let’s look at a few different solutions of the same dataset, sorted from most to least fair. Each one has 15 tasks:
| Ann | Beth | Carl | Dan | Ed | Solution Quality | |
|---|---|---|---|---|---|---|
Schedule A |
3 |
3 |
3 |
3 |
3 |
Most fair |
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 |
5 |
6 |
2 |
1 |
1 |
|
Schedule G |
11 |
1 |
1 |
1 |
1 |
Most unfair |
Ann has the most tasks each time. How do we compare schedules in which Ann has the same number of tasks?
| Ann | Beth | Carl | Dan | Ed | Solution Quality | |
|---|---|---|---|---|---|---|
Schedule C |
5 |
3 |
3 |
2 |
2 |
More fair |
Schedule D |
5 |
5 |
2 |
2 |
1 |
Less fair |
We look at the second most loaded employee, Beth. In schedule D, she has five tasks, while in schedule C, she has less. This makes schedule C fairer overall. Therefore, this is the definition of fairness we use in the remainder of this post.
Measuring unfairness
For the mathematically minded among you, we’re currently using the following formula to calculate the unfairness of a solution, also called "squared deviation from the mean":
In this formula:
-
nis the number of employees. -
xiis the number of tasks assigned to employeei. -
x̄is the average number of tasks per employee.
Also see a MathExchange question discussing this formula and other alternatives in depth.
Implementing fairness constraints
Timefold Solver supports fairness constraints out of the box through the use of grouping
and the load-balancing constraint collector.
In your ConstraintProvider implementation, a load-balancing constraint may look like this:
- Java
-
Constraint balanceEmployeeShiftAssignments(ConstraintFactory constraintFactory) { return constraintFactory.forEach(Shift.class) .groupBy(ConstraintCollectors.loadBalance(Shift::getEmployee)) .penalizeBigDecimal(HardSoftBigDecimalScore.ONE_SOFT, LoadBalance::unfairness) .asConstraint("Balance employee shift assignments"); } - Kotlin
-
fun balanceEmployeeShiftAssignments(constraintFactory: ConstraintFactory): Constraint { return constraintFactory.forEach(Shift::class.java) .groupBy(ConstraintCollectors.loadBalance({ shift -> shift.employee })) .penalizeBigDecimal(HardSoftBigDecimalScore.ONE_SOFT) { loadBalance -> loadBalance.unfairness } .asConstraint("Balance employee shift assignments") } - Python
-
def balance_employee_shift_assignments(constraint_factory: ConstraintFactory): return (constraint_factory.for_each(Shift) .group_by(ConstraintCollectors.load_balance(lambda shift: shift.employee)) .penalize_decimal(HardSoftDecimalScore.ONE_SOFT, lambda load_balance: load_balance.unfairness()) .as_constraint("Balance employee shift assignments") )
This constraint will penalize the solution based on its unfairness,
defined in this case by how many ShiftAssignment are allocated to any particular Employee.
Unfairness is a dimensionless number that measures how fair the solution is. A lower value indicates a fairer solution. The smallest possible value is 0, indicating that the solution is perfectly fair. There is no upper limit to the value, and it is expected to scale linearly with the size of your dataset. The value is rounded to six decimal places.
Different unfairness values may only be compared for solutions coming from the same dataset. Unfairness values computed from different datasets are incomparable.
|
Important
|
When using fairness constraints, we recommend that you use one of the score types based on |
Conclusion
Fairness in your planning improves employee satisfaction and helps you comply with legal requirements. Adding fairness to your Timefold solution is straightforward and can be done in a few lines of Java, Python or Kotlin code. Other solvers would be hard-pressed to match the flexibility of our implementation. Check out the latest Timefold Solver and start making your solutions fairer today.
