Modelling and Solving Workforce Scheduling Optimization Problems

Modelling and Solving Workforce Scheduling Optimization Problems

  • Post author:
  • Post category:Blog

Workforce scheduling is an essential optimization problem for any business that needs to cope with variable demand, be it during working hours, days of the week or annual seasons.

Manufacturing plants, warehouses, trucking companies, public transportation, construction, retail, hospitals, banks. All types of businesses need to make the best possible use of their resources in order to maximize customer satisfaction.

There is a large variety of workforce scheduling models, which in general include some or all of the following requirements

  • Timetabling
  • Shift scheduling
  • Task assignment
  • Break assignment
  • TOIL or overtime
  • Demand uncertainty
  • Minimum perturbation rescheduling

Timetabling

Timetabling is generally used to describe problems where people are present in a given place all at the same time

  • usage of classrooms in a school / university
  • departure of buses or trains

It can also be an workforce scheduling problem were shifts are already organized into fixed slots (morning, afternoon, night) or problems considered at the day granularity instead of the hour / minute granularity.

Employee Mo Tu We Th Fr Sa Su
Alice X X X . X . X
Bob X . . X X X X
Charlie . X X X X X .

Allowed and forbidden patterns

Timetabling is often combined with allowed and forbidden patterns to be respected like

  • employees shall have 2 days off in sequence
  • employees shall not work a night shift followed by a morning shift

Industry and company labor agreements very often include very specific constraints to be satisfied and companies are legally liable for their compliance.

Allowed and forbidden patterns

Pattern-based time-tabling is common in industries where managing schedules with fixed shifts is easier than managing at the hour / minute level.

It could be because people work in teams, because of a large number of workers, or because time and attendance (checking employee presence) is done in a way that makes it easier to control with fixes shifts. Other practical reasons may include the need of organizing employee collective transportation (e.g. company buses) because working site are isolated, or well established industry practice.

Contract mix and workforce dimensioning

Timetabling is often used in conjunction with contract selection in workforce dimensioning. In that case the time horizon is a quarter or a year, and the problem consists in finding the best mix of contracts (full-time, weekend, night, temporary) taking into consideration vacations, official holidays and seasonality of demand.

Contract mix and workforce dimensioning

Shift scheduling

Shift scheduling is consists in not only deciding the working day but also the start time and the duration of each shift for each employee.

Labor contracts usually specify

  • Number of working days
  • Number of working hours
  • Minimum shift duration
  • Maximum shift duration
  • Minimum time between shifts
  • Some required or forbidden patterns

For instance 5 working days, 40h per week, between 6 and 10 hours per shift, minimum 12 hours between shifts and 2 consecutive days off.

Shift have to respect labor rules and at the same time cover as closely as possible the needs.

Shift have to respect labor rules

The shifts won’t perfectly cover the demand, therefore any schedule will have over and under-covered parts.

over and under-covered parts

In this example, the demand (above in blue) can only be partially covered (green). The red parts correspond to the under-coverage, the purple parts to the over-coverage.

over and under-covered parts 2

It is not always obvious to rank different solutions to a shift scheduling problem. Problems like "is it better to have 2 units of under-coverage between 12h and 12h15 or 1 unit of under-coverage between 15h and 15h30" arise on a frequent basis. Similar problems arise when having to decide whether hiring one more employee or not.

Task assignment

Task assignment is the problem of computing shifts and fully or partially assigning them to tasks.

Task assignment

The requirements for the tasks can be fixed (a given amount per time slot), floating (a certain amount per day to be done anywhere within a time-window).

Employees may have one or multiple skills and even a rating in the execution of each skill.

Companies policies may contradict each other like

  • employees shall be assigned to tasks where they are the most skilled
  • employees shall be regularly assigned to diverse tasks to keep their proficiency

Generally speaking task assignment is a complex problem that combines the difficulties of multi-criteria decision making with computationally demanding optimization models.

Break assignment

Break assignment is a floating task within a shift. The length of the break or the number of breaks may depend on the length of the shift.

The problem of break assignment is to balance

  • Employees rights to take breaks at reasonable times
  • Employee preference to take breaks together
  • Business needs to maintain service levels at all times

Break assignment

Adding breaks to an existing schedule in general gives poor results, creating deep under-coverage areas during the day. Better results are obtained if breaks are considered during the shift creation phase, allowing optimization engines to create shift overlaps in prevision for the breaks.

Planned versus clocked hours

Employees don’t always work exactly the number of hours that were planned in the schedule. Time and attendance are the systems used to track employees real (clocked) hours.

Overtime versus TOIL

When an employee clocks more hours than the contract stipulates, (s)he can be paid overtime or the extra hours can be compensated by lowering the number of work hours in the next time period. This is called Time-off in-lieu or TOIL.

TOIL results in a variable number of hours to be worked in each scheduling period : the contract may be 40h but because of compensation due to TOIL, the employee may need to work 42h or 39h next week.

This may also play interact with the minimum and maximum hours per shift changing the shift configurations that are possible for a given employee.

Schedule regularity

Cyclic versus regular schedules

Employees like having regular schedules. While periodic or cyclic schedules are not considered a best practice because they prevent adapting the workforce to the demand, having regular schedules is always preferable

  • Helps employees organize themselves
  • Decreases absences, lateness
  • Increases employee satisfaction

Schedule regularity

Making schedules that consider the regularity from the beginning leads to better solutions than swapping shifts on an already created schedule.

As a workaround, the ability for employees to swap shifts with little to no management intervention (employee self-service) is an often requested feature in workforce scheduling software.

Rescheduling

Many organisations require schedules to be published a couple of weeks in advance, sometimes 1 month, to give enough time for employees to organise themselves. Last minute changes (emergency, sickness, etc) require the schedule to be re-done.

When a schedule that has already been made public is redone, it is important to alter the schedule as little as possible.

Uncertainty

Schedules are based on a demand forecast, typically processed with productivity measures to obtain needs in terms of employees per time slot, called the workload.

Computing workload

A call-center may have historical data about the number and duration of past customer calls. However, the amount of time it takes to handle a call doesn’t only depend on external factors (the nature of the problem) but also the skills of the employee, which is set by the schedule.

As a result, the amount of work per time slot cannot be directly forecast from the historical data. A possible solution may be something along the lines of

  • Rate employees with respect to a standard processing speed (e.g. Alice is 1.2x faster the standard)
  • Re-scale the historical data based on which employee handled each call (assuming that data is available)
  • Forecast a standard amount of work per time slot based on the re-scaled historical data
  • Create a schedule taking into consideration the employee speed with respect to the standard
  • Adjust on a regular basis the employee rating

However, productivity data is hard to estimate and the necessary information for its historical computation wasn’t always kept or is not easy to access (e.g. find and capture past schedules to try to estimate who could have processed each call)

Handling uncertainties

Uncertainties in optimization are handled by two subfields

  • Robust optimization handles optimization problems where multiple scenarios are possible and there is a form of preference on outcomes over the whole set of scenarios (e.g. we prefer an average solution everywhere than a solution that is some times excellent, some times horrendous)
  • Stochastic optimization handles optimization problems where the uncertainty can be probabilistically quantified, and the preferred outcome is the maximum expected value.

Stochastic optimization tends to be difficult to apply if there is not an undisputed way of computing the probabilities needed ; It is very difficult for humans to estimate probabilities, therefore if human input is required, robust optimization is often a better approach.

Types of uncertainties that can be handled

Typical uncertainties are uncertainties

  • Demand within the day : Is there going to be a peak of demand around noon or later in the afternoon ? This leads to scheduling extra employees in an average position when possible.
  • Total demand of the day : Is there going to be a large demand on the first day of a promotion or not ? This leads to scheduling employees in that day and possibly send them home later.
  • Absence of an employee : some employee categories have statistical absence patterns like students close to exams, but also bank holidays that are close to a weekend, etc. While the best approach remains trying to agree with employees and give them the days off they would like to have, sometimes preventive measures are taken.

A less common but possibly more interesting use case is balancing uncertainty across stores, with employees "positioned" at some stores but having the ability to move to nearby stores to cope with unexpected surges of activity.

Covid 19

Covid19 creates new challenges in workforce scheduling. It is advisable to separate more fragile populations from the more robust ones, both on the workforce and the customer side.

In a retailer that would translate in creating specific hours for fragile customers, with stricter limitations on maximum density of people in the store, and only employees in the store that have low risk of contaminating them.

From a schedule creation perspective Covid19 generates new constraints on which employees can work at specific times or to specific tasks on certain hours.