Finding the Perfect�Shift Schedule

PyCon APAC 2022

Shung-Hsi Yu

Click here to see the accompanying Jupyter notebook

About Me

Shung-Hsi Yu (@shunghsiyu)

​

Kernel Engineer at

working from Taitung

Scheduling Problem

Situation where you…

Allocate resource

• e.g. worker
• usually limited

For some purpose

• e.g. task/job/shift

Under some rules

• e.g. 8 hours a day

Day [009] Schedule. by Sadie Hernandez

In fact, you being here mean…

​

1. PyCon organizers scheduling each talk
• meeting rooms are the limited resource

​

• You're experiencing a scheduling problem
• choosing talks to listen
• your time & attention is the limited resource

Shift Scheduling

a.k.a. employee rostering

Timeslot

• e.g. Monday, Tuesday

​

Person

• more commonly referred as employee
• the limited resource

Shift icons created by Iconjam - Flaticon

Shift Scheduling

a.k.a. employee rostering

Fairly similar to solving Sudoku

​

Instead of reinventing the wheel…

use existing solvers

Sudoku icons created by Freepik - Flaticon

Using Solvers

Magical tools

Describe the problem

instead of solving it

​

Too good to be true?

Magic icons created by Freepik - Flaticon

Describing problem to a solver

Alice works on Monday ∧ ¬Bob works on Monday ∧ ¬Carol works on Monday�∨�¬Alice works on Monday ∧ Bob works on Monday ∧ ¬Carol works on Monday�∨�¬Alice works on Monday ∧ ¬Bob works on Monday ∧ Carol works on Monday

Modeling the Problem

Encoding the Model

Person

from dataclasses import dataclass # Python 3.7+

​

@dataclass

class Person:

name: str

Encoding the Model

Person

Three person/employees

​

persons = [

Person('Alice'),

Person('Bob'),

Person('Carol'),

]

Encoding the Model

Timeslot

Just one timeslot, for now

​

@dataclass

class TimeSlot:

name: str # Let's start simple

​

Encoding the Model

Timeslot

Just one timeslot, for now

​

@dataclass

class TimeSlot:

name: str # Let's start simple

​

monday = TimeSlot('Monday')

Encoding the Model

How to encode Schedule?

Life would be easy if…

​

class Schedule:

time: TimeSlot

assignee: Person

​

scheds = solver(persons, timeslots=[monday])

len(scheds) == 1

scheds[0].assignee.name == 'Bob'

Encoding the Model

How to encode Schedule?

Life would be easy if…

​

class Schedule:

time: TimeSlot

assignee: Person

​

scheds = solver(persons, timeslots=[monday])

len(scheds) == 1

scheds[0].assignee.name == 'Bob'

Encoding the Model

How to encode Schedule?

Life would be easy if…

​

class Schedule:

time: TimeSlot

assignee: Person

​

scheds = solver(persons, timeslots=[monday])

len(scheds) == 1

scheds[0].assignee.name == 'Bob'

Basic of Solvers

Solvers work with Boolean Variables*

* Actually, SMT solvers like Z3 can work with other variables such as Bit Vector, custom Data-type, etc. It’s the SAT solvers that only work with Boolean Variables.

Basic of Solvers

Solvers work with Boolean Variables

Bool('It is sunny outside')

ID / Name

Encoding the Model

Turning an (ideal) Python class into Boolean Variable

class Schedule:

time: TimeSlot

assignee: Person

Bool('...')

?

Encoding the Model

Turning an (ideal) Python class into Boolean Variable

class Schedule:

time: TimeSlot

assignee: Person

Bool('...')

Bool('...')

Bool('...')

Encoding the Model

# Represent whether Alice is works on Monday

alice_works_on_monday = Bool('Alice works on Monday')

​

# Similar Bob

bob_works_on_monday = Bool('Bob works on Monday')

​

# and Carol

carol_works_on_monday = Bool('Carol works on Monday')

Basic of Solvers

Solver decides it’s value automatically

Bool('Alice works on Monday')

True

False

?

?

Rules

One Person per Shift

Each shift only needs one person (for now)

​

​

One Person per Shift

Only one of them should be working, so either

1. Alice works, while Bob and Carol does not, or
2. Bob works, while Alice and Carol does not, or
3. Carol works, while Alice and Bob does not

​

​

One Person per Shift

Only one of them should be working, so either

• Alice works, while Bob and Carol does not, or
• Bob works, while Alice and Carol does not, or
• Carol works, while Alice and Bob does not

​

​

One Person per Shift

Here’s how you represent the observation

Alice works, while Bob and Carol does not

​

​

And(

alice_works_on_monday == True,

bob_works_on_monday == False,

carol_works_on_monday == False,

)

One Person per Shift

Here’s how you represent the observation

Alice works, while Bob and Carol does not

​

​

And(

alice_works_on_monday == True,

bob_works_on_monday == False,

carol_works_on_monday == False,

)

One Person per Shift

Here’s how you represent the observation

Alice works, while Bob and Carol does not

​

​

And(

alice_works_on_monday == True,

bob_works_on_monday == False,

carol_works_on_monday == False,

)

One Person per Shift

Here’s how you represent the observation

Alice works, while Bob and Carol does not

​

​

And(

alice_works_on_monday == True,

bob_works_on_monday == False,

carol_works_on_monday == False,

)

One Person per Shift

Here’s how you represent the observation

Alice works, while Bob and Carol does not

​

​

And(

alice_works_on_monday == True,

bob_works_on_monday == False,

carol_works_on_monday == False,

)

One Person per Shift

Here’s how you represent the observation

Alice works, while Bob and Carol does not

​

​

And(

alice_works_on_monday,

Not(bob_works_on_monday),

Not(carol_works_on_monday),

)

One Person per Shift

Only one of them should be working, so either

• Alice works, while Bob and Carol does not, or
• Bob works, while Alice and Carol does not, or
• Carol works, while Alice and Bob does not

​

​

One Person per Shift

Only one of them should be working, so either

• Alice works, while Bob and Carol does not, or
• Bob works, while Alice and Carol does not, or
• Carol works, while Alice and Bob does not

​

​

One Person per Shift

Only one of them should be working, so either

• Alice works, while Bob and Carol does not, or
• Bob works, while Alice and Carol does not, or
• Carol works, while Alice and Bob does not

​

​

One Person per Shift

Or(

# Only Alice is working

And(alice_works..., Not(bob_work...),� Not(carol_works_on_monday)),

# Only Bob is working

And(Not(alice_works...), bob_works...,

Not(carol_works_on_monday)),

# Only Carol is working

And(Not(alice_works...), Not(bob_works…),

carol_works_on_monday),

)

One Person per Shift

Or(

# Only Alice is working

And(alice_works..., Not(bob_work...),� Not(carol_works_on_monday)),

# Only Bob is working

And(Not(alice_works...), bob_works...,

Not(carol_works_on_monday)),

# Only Carol is working

And(Not(alice_works...), Not(bob_works…),

carol_works_on_monday),

)

One Person per Shift

Or(

# Only Alice is working

And(alice_works..., Not(bob_work...),� Not(carol_works_on_monday)),

# Only Bob is working

And(Not(alice_works...), bob_works...,

Not(carol_works_on_monday)),

# Only Carol is working

And(Not(alice_works...), Not(bob_works…),

carol_works_on_monday),

)

One Person per Shift

Or(

# Only Alice is working

And(alice_works..., Not(bob_work...),� Not(carol_works_on_monday)),

# Only Bob is working

And(Not(alice_works...), bob_works...,

Not(carol_works_on_monday)),

# Only Carol is working

And(Not(alice_works...), Not(bob_works…),

carol_works_on_monday),

)

One Person per Shift

Or(

# Only Alice is working

And(alice_works..., Not(bob_work...),� Not(carol_works_on_monday)),

# Only Bob is working

And(Not(alice_works...), bob_works...,

Not(carol_works_on_monday)),

# Only Carol is working

And(Not(alice_works...), Not(bob_works…),

carol_works_on_monday),

)

One Person per Shift

only_one_works_monday = Or(

# Only Alice is working

And(alice_works..., Not(bob_work...),� Not(carol_works_on_monday)),

# Only Bob is working

And(Not(alice_works...), bob_works...,

Not(carol_works_on_monday)),

# Only Carol is working

And(Not(alice_works...), Not(bob_works…),

carol_works_on_monday),

)

One Person per Shift

Plugging it in…

solve(

only_one_works_monday,

)

​

[Bob works on Monday = True,

Carol works on Monday = False,

Alice works on Monday = False]

One Person per Shift

Plugging it in…

solve(

only_one_works_monday,

)

​

[Bob works on Monday = True,

Carol works on Monday = False,

Alice works on Monday = False]

Ta-da!

Firework icons created by Freepik - Flaticon

Scaling Up

More timeslots

timeslots = [

TimeSlot('Monday'),

TimeSlot('Tuesday'),

TimeSlot('Wednesday'),

TimeSlot('Thursday'),

...

TimeSlot('Sunday'),

]

Scaling Up

More timeslots

solve(

only_one_works_monday,

only_one_works_tuesday,

only_one_works_wednesday,

only_one_works_thursday,

...

only_one_works_sunday,

)

Scaling Up

Getting rid of hard-coding

alice_works_on_monday = Bool('Alice works on Monday')

​

only_one_works_monday = Or(

And(alice_works..., Not(bob_work...),

Not(carol_works_on_monday)),

...

)

Scaling Up

Getting rid of hard-coding

alice_works_on_monday = Bool('Alice works on Monday')

​

only_one_works_monday = Or(

And(alice_works..., Not(bob_work...),

Not(carol_works_on_monday)),

...

)

Refactoring

Getting rid of hard-coding

in Bool()

def get_var(timeslot, person):

name = person.name

day = timeslot.name

return Bool(f'{name} works on {day}')

Getting rid of hard-coding

in Bool()

alice_works_on_monday = Bool('Alice works on Monday')

​

​

person = Person('Alice')

timeslot = Timeslot('Monday')

alice_works_on_monday = get_var(timeslot, person)

Getting rid of hard-coding

in Bool()

alice_works_on_monday = Bool('Alice works on Monday')

​

​

person = Person('Alice')

timeslot = Timeslot('Monday')

alice_works_on_monday = get_var(timeslot, person)

Getting rid of hard-coding

in Bool()

def get_vars(timeslot, persons):

vars = [get_var(timeslot, person)

for person in persons]

return vars

Getting rid of hard-coding

in Bool()

def get_vars(timeslot, persons):

vars = [get_var(timeslot, person)

for person in persons]

return vars

​

alice_works_on_monday, bob..., carol... = \

get_vars(monday, persons)

Simplifying the Rule

only_one_works_monday = Or(

And(alice_works..., Not(bob_work...),� Not(carol_works_on_monday)),

And(Not(alice_works...), bob_works...,

Not(carol_works_on_monday)),

And(Not(alice_works...), Not(bob_works…),

carol_works_on_monday),

)

Simplifying the Rule

Using helpers

AtMost(..., n)

AtLeast(..., n)

Simplifying the Rule

Using helpers

AtMost(..., n)

AtLeast(..., n)

Simplifying the Rule

Using helpers

AtMost(..., n)

AtLeast(..., n)

Simplifying the Rule

Using helpers

Either one or none of them works

​

at_most_one_works_monday = AtMost(

alice_works_on_monday,

bob_works_on_monday,

carol_works_on_monday,

1

)

​

Simplifying the Rule

Using helpers

Either one or none of them works

​

at_most_one_works_monday = AtMost(

*get_vars(monday, persons),

1

)

​

Simplifying the Rule

Using helpers

Either one, two, or three of them works

​

at_least_one_works_monday = AtLeast(

*get_vars(monday, persons),

1

)

​

Simplifying the Rule

Using helpers

only_one_works_monday = And(

at_most_one_works_monday,

at_least_one_works_monday,

)

Simplifying the Rule

Creating a helper

def ExactlyOne(vars):

return And(AtMost(*vars, 1), AtLeast(*vars, 1))

Simplifying the Rule

Creating a helper

def ExactlyOne(vars):

return And(AtMost(*vars, 1), AtLeast(*vars, 1))

​

only_one_works_monday = \

ExactlyOne(get_vars(monday, persons))

Putting it All Together

rules = [] # Store the rules for re-use

​

# For each timeslot, only one person works

for timeslot in timeslots:

working = get_vars(timeslot, persons)

rules.append(ExactlyOne(working))

​

solve(rules) # Call the solver

Putting it All Together

rules = [] # Store the rules for re-use

​

# For each timeslot, only one person works

for timeslot in timeslots:

working = get_vars(timeslot, persons)

rules.append(ExactlyOne(working))

​

solve(rules) # Call the solver

Putting it All Together

rules = [] # Store the rules for re-use

​

# For each timeslot, only one person works

for timeslot in timeslots:

working = get_vars(timeslot, persons)

rules.append(ExactlyOne(working))

​

solve(rules) # Call the solver

A schedule for the week

A schedule for the week

More Rules

Fairness

Making people equally (un)happy

Can be a tricky subject

​

Using an objective measure:

Number of shifts

Fairness icons created by Freepik - Flaticon

Fairness

Making people equally (un)happy

Find the ideal number of shift each person should take

​

num_shifts, num_persons = len(timeslots), len(persons)

​

min_shifts = math.floor(num_shifts / num_persons)

​

max_shifts = math.ceil(num_shifts / num_persons)

​

Fairness

Making people equally (un)happy

for person in persons:

# shifts belonging to person

shifts = [get_var(timeslot, person)

for timeslot in timeslots]

rules.append(AtLeast(*shifts, min_shifts))

rules.append(AtMost(*shifts, max_shifts))

​

solve(rules)

Fairness

Making people equally (un)happy

for person in persons:

# shifts belonging to person

shifts = [get_var(timeslot, person)

for timeslot in timeslots]

rules.append(AtLeast(*shifts, min_shifts))

rules.append(AtMost(*shifts, max_shifts))

​

solve(rules)

A fairer schedule for the week

Days-off

Certain person may not be available for certain timeslot

​

How to not assign them?

Beach icons created by Freepik - Flaticon

Days-off

Let’s say Carol can’t work on Monday due to urgent issue

​

rules.append(

get_var(monday, Person('Carol')) == False

)

Days-off

Let’s say Carol can’t work on Monday due to urgent issue

​

rules.append(

Not(get_var(monday, Person('Carol')))

)

Carol taking day-off on Monday

Days-off

What if besides Carol,

Bob and Alice both prefer not to work on Monday

​

rules.append(

get_var(monday, Person('Alice')) == False

)

rules.append(

get_var(monday, Person('Bob')) == False

)

Solver return value

UNSAT

Days-off

No one can be assigned for Monday

​

# Urgent issue

get_var(monday, Person('Carol')) == False

​

# Prefer not to work on Monday

get_var(monday, Person('Alice')) == False

get_var(monday, Person('Bob')) == False

No schedule can satisfy the rules

Days-off

Better way to express preference?

​

Soft Constraints

Expressing Preference

We create a solver variable to keep track of

how bad/good the schedule is

​

Expressing Preference

We create a solver variable to keep track of

how bad/good the schedule is

​

# Higher value means worst schedule

penalty = IntVal(0)

Expressing Preference

Increase it everything something not preferred happens

Alice prefers not to work on Monday

​

penalty += 1 if get_var(monday, Person('Alice')) else 0

Expressing Preference

Increase it everything something not preferred happens

Alice prefers not to work on Monday

​

penalty += 1 if get_var(monday, Person('Alice')) else 0

Expressing Preference

Increase it everything something not preferred happens

Alice prefers not to work on Monday

​

penalty += 1 if get_var(monday, Person('Alice')) else 0

solver boolean variables,

not a Python boolean

Expressing Preference

Increase it everything something not preferred happens

Alice prefers not to work on Monday

​

penalty += If(get_var(monday, Person('Alice')), 1, 0)

Expressing Preference

def var_to_int(var):

return If(var, 1, 0)

​

def get_int(timeslot, person):

return var_to_int(get_var(timeslot, person))

Expressing Preference

def var_to_int(var):

return If(var, 1, 0)

​

def get_int(timeslot, person):

return var_to_int(get_var(timeslot, person))

​

penalty += get_int(monday, Person('Alice'))

Putting it Together

# Hard constraints

rules.append(

get_var(monday, Person('Carol')) == False

)

​

# Soft constraints

penalty += get_int(monday, Person('Alice'))

penalty += get_int(monday, Person('Bob'))

Putting it Together

# Hard constraints

rules.append(

get_var(monday, Person('Carol')) == False

)

​

# Soft constraints

penalty += get_int(monday, Person('Alice'))

penalty += get_int(monday, Person('Bob'))

Putting it Together

# Hard constraints

rules.append(

get_var(monday, Person('Carol')) == False

)

​

# Soft constraints

penalty += get_int(monday, Person('Alice'))

penalty += get_int(monday, Person('Bob'))

Putting it Together

Use the Optimize solver, which support soft-constraints

​

solver = Optimize()

solver.add(rules)

solver.minimize(penalty)

solver.check()

model = solver.model() # the schedule

A schedule for the week with soft-constraints

Quick Summary

The basic of scheduling

We’ve covered:

• Encoding scheduling problem with boolean variables
• One person per shift rule
• Shift fairness
• Using soft-constraints to express preferences

Advance Scheduling

non-working day

two-person shifts

(special) two-person shifts

consistent schedule on the same week day

intern is not allowed to work alone

Alice doesn’t want to work on Monday and Tuesday of the first week

Bob doesn’t want to work on Wednesdays

(NOT entirely fulfilled)

Dave prefers to work one day on the weekend consistently

Erin doesn’t want to on the last Friday

2x load

4x load

Irregular Schedules

Some shifts have:

• Two person
• Zero person (i.e. non-working day)

Irregular Schedules

@dataclass

class TimeSlot:

week: int

day: WeekDay

num_worker: int = 1

load: int = 1

class WeekDay(Enum):

Monday = auto()

Tuesday = auto()

Wednesday = auto()

Thursday = auto()

...

Sunday = auto()

​

​

Irregular Schedules

timeslots = [

TimeSlot(week=1, day=WeekDay.Monday, num_worker=2),

TimeSlot(week=1, day=WeekDay.Tuesday, num_worker=2),

TimeSlot(week=1, day=WeekDay.Wednesday),

TimeSlot(week=1, day=WeekDay.Thursday, num_worker=0),

TimeSlot(week=1, day=WeekDay.Friday, num_worker=2),

…

TimeSlot(week=4, day=WeekDay.Sunday, num_worker=2,

load=4),

]

Spreading Loads Evenly

With soft constraints penalizing large deviation

for person in persons:

loads = sum(

get_int(timeslot, person))*timeslot.load

for timeslot in timeslots

)

deviation = If(

loads < min_loads,

loads - min_loads,

If(loads > max_loads,

max_loads - loads, 0)

)

penalty += weight * deviation**2

Spreading Loads Evenly

With soft constraints penalizing large deviation

for person in persons:

loads = sum(

get_int(timeslot, person))*timeslot.load

for timeslot in timeslots

)

deviation = If(

loads < min_loads,

loads - min_loads,

If(loads > max_loads,

max_loads - loads, 0)

)

penalty += weight * deviation**2

Spreading Loads Evenly

With soft constraints penalizing large deviation

for person in persons:

loads = sum(

get_int(timeslot, person))*timeslot.load

for timeslot in timeslots

)

deviation = If(

loads < min_loads,

loads - min_loads,

If(loads > max_loads,

max_loads - loads, 0)

)

penalty += weight * deviation**2

Conclusion

Compared to a Custom Scheduler

The Good

• (Usually) less code ⇒ less bugs & faster to write
• and easier to maintain
• Gets better over time
• Runs fast enough

Compared to a Custom Scheduler

The Bad

• Can be intimidating at first
• Solving time is not deterministic
• Tuning requires in-depth knowledge of solvers
• e.g. need to know what tactics are

My Suggestion for Writing a Scheduler

General suggestions

• Rules should be known and agreed upon
• Best for mundane, recurring schedule
• Graphical user interface
• Or take & output Excel/CSV
• Soft constraints make all the difference

My Suggestion for Writing a Scheduler

Picking a tool

Solver-based Tools

• Z3, OR-Tools, Gurobi

​

High-level Tools

• OptaPlanner/OptaPy

My Suggestion for Writing a Scheduler

Picking a tool

Solver-based Tools

• Z3, OR-Tools, Gurobi

​

High-level Tools

• OptaPlanner/OptaPy

What this talk is about

My Suggestion for Writing a Scheduler

Picking a tool

Solver-based Tools

• Z3, OR-Tools, Gurobi

​

High-level Tools

• OptaPlanner/OptaPy

Powerful, flexible

Math > Programming

My Suggestion for Writing a Scheduler

Picking a tool

Solver-based Tools

• Z3, OR-Tools, Gurobi

​

High-level Tools

• OptaPlanner/OptaPy

Easier for scheduling

Object-oriented approach

My Suggestion for Writing a Scheduler

Picking a tool

Solver-based Tools

• Z3, OR-Tools, Gurobi

​

High-level Tools

• OptaPlanner/OptaPy

If you need a scheduler made right away

Learning for fun & intellectual challenges

Portability

Other Superpowers of Z3

with also applied to other SMT solvers

• Software verification
• Program synthesis
• Dependency resolution
• Auto-layout
• and many more…

Magic icons created by Freepik - Flaticon

The End

Happy Scheduling!