Automatic and optimal shift scheduling using Reinforcement Learning (Part 4)
Using Sequential Decision Analytics to find ongoing optimal decisions
Retail Industry
Scheduling
Powell Unified Framework
Reinforcement Learning
Python
Author
Kobus Esterhuysen
Published
November 2, 2023
Modified
November 2, 2023
0 INTRODUCTION
In the previous part we added tracking of the cumulative unmet resource demands (Ucum) by resource type. We now also track the overall or total unmet demands. We are also keeping track of the associated pandas datetime for each integer value of the time \(t\). Additionally we added another parameter to be learned by the agent: \(\theta^{SickProb}\). We are also making use of past employee data to calculate, for each month of the year, the probability that a particular resource will call in sick or not show up for work. To be considered a candidate for allocation to a shift a resource’s sick probability for the month must be lower than \(\theta^{SickProb}\).
In this part we change the policy. First, we renamed it from X__AllocBelow to X__Alloc. We now have the policy consider costs/contributions instead of excluding candidates below thCumShifts & thSickProb. We found that the agent exploits the situation by having thCumShifts and thSickProb near their max values so that it can use the complete pool. So, instead of using thresholds below which resources are included as candidates, we will always have all (available) resources in the candidates pool. However, we will have the agent earn rewards or incur penalties to discourage allocation of less ideal resources. The new parameters will be:
\(\theta^{CumShifts}\)
\(\theta^{SickProb}\)
Each of these will operate as a weighting factor to weight the associated component of the cumulative reward \(C^{cum}\):
To keep the visualizations manageable, we will only have the resources:
Courtesy Clerk (7 resources)
Stocker (3 resources)
In a later part we will also add:
Cleaner (2 resources)
Curbsider (4 resources)
Daily demands are provided by a stochastic simulator based on past needs and trends.
The overall structure of this project and report follows the traditional CRISP-DM format. However, instead of the CRISP-DM’S “4 Modeling” section, we inserted the “6 step modeling process” of Dr. Warren Powell in section 4 of this document. Dr Powell’s universal framework shows great promise for unifying the formalisms of at least a dozen different fields. Using his framework enables easier access to thinking patterns in these other fields that might be beneficial and informative to the sequential decision problem at hand. Traditionally, this kind of problem would be approached from the reinforcement learning perspective. However, using Dr. Powell’s wider and more comprehensive perspective almost certainly provides additional value.
In order to make a strong mapping between the code in this notebook and the mathematics in the Powell Universal Framework (PUF), we follow the following convention for naming Python identifier names:
How to read/say
var name & flavor first
at t/n
for entity OR of/with attribute
\(\hat{R}^{fail}_{t+1,a}\) has code Rhat__fail_tt1_a which is read: “Rhatfail at t+1 of/with (attribute) a”
Superscripts
variable names have a double underscore to indicate a superscript
\(X^{\pi}\): has code X__pi, is read X pi
when there is a ‘natural’ distinction between the variable symbol and the superscript (e.g. a change in case), the double underscore is sometimes omitted: Xpi instead of X__pi, or MSpend_t instead of M__Spend_t
Subscripts
variable names have a single underscore to indicate a subscript
\(S_t\): has code S_t, is read ‘S at t’
\(M^{Spend}_t\) has code M__Spend_t which is read: “MSpend at t”
\(\hat{R}^{fail}_{t+1,a}\) has code Rhat__fail_tt1_a which is read: “Rhatfail at t+1 of/with (attribute) a” [RLSO-p436]
Arguments
collection variable names may have argument information added
\(X^{\pi}(S_t)\): has code X__piIS_tI, is read ‘X pi in S at t’
the surrounding I’s are used to imitate the parentheses around the argument
Next time/iteration
variable names that indicate one step in the future are quite common
\(R_{t+1}\): has code R_tt1, is read ‘R at t+1’
\(R^{n+1}\): has code R__nt1, is read ‘R at n+1’
Rewards
State-independent terminal reward and cumulative reward
\(F\): has code F for terminal reward
\(\sum_{n}F\): has code cumF for cumulative reward
State-dependent terminal reward and cumulative reward
\(C\): has code C for terminal reward
\(\sum_{t}C\): has code cumC for cumulative reward
Vectors where components use different names
\(S_t(R_t, p_t)\): has code S_t.R_t and S_t.p_t, is read ‘S at t in R at t, and, S at t in p at t’
the code implementation is by means of a named tuple
self.State = namedtuple('State', SVarNames) for the ‘class’ of the vector
self.S_t for the ‘instance’ of the vector
Vectors where components reuse names
\(x_t(x_{t,GB}, x_{t,BL})\): has code x_t.x_t_GB and x_t.x_t_BL, is read ‘x at t in x at t for GB, and, x at t in x at t for BL’
the code implementation is by means of a named tuple
self.Decision = namedtuple('Decision', xVarNames) for the ‘class’ of the vector
self.x_t for the ‘instance’ of the vector
Use of mixed-case variable names
to reduce confusion, sometimes the use of mixed-case variable names are preferred (even though it is not a best practice in the Python community), reserving the use of underscores and double underscores for math-related variables
1 BUSINESS UNDERSTANDING
The HR manager has to schedule resources for 3 shifts: Shift1, Shift2, and Shift3. For now, only Shift1 will be handled by the AI agent.
The number of resources of each type for each schedule slots for each day will be provided by the simulator. Only two resource types will be handled:
Courtesy
Stocker
The HR manager typically runs the AI Shift Scheduler 2 weeks into the future to produce a tentative schedule to publish for the team.
As demands for shift slot allocations come in, they are handled in the following way:
the candidates for the resource type must have their:
\(R^{Avail}_t\) be True
the specific resources are then marked for allocation considering the number of resources needed for the type
the state of the resources are then updated including the number of accumulated shifts
at the end of the shift all resources are made available again
The overall objective will be to maximize the cumulative reward.
2 DATA UNDERSTANDING
Based on recent market research, the demand may be modeled by a Poisson distribution for each resource type: \[
\begin{aligned}
\mu^{ResourceType} &= \mathrm{SIM\_MU\_D[RESOURCE\_TYPE]}
\end{aligned}
\]
So we have: \[
D^{ResourceType}_{t+1} \sim Pois(\mu^{ResourceType})
\]
The decision window is 1 day and these simulations are for the daily demands for Shift1.
DeprecationWarning: Please use `shift` from the `scipy.ndimage` namespace, the `scipy.ndimage.interpolation` namespace is deprecated.
from scipy.ndimage.interpolation import shift
We will use the data provided by the simulator directly. There is no need to perform additional data preparation.
4 MODELING
4.1 Narrative
Please review the narrative in section 1. The next figure is a representation of the solution to the problem:
AIShiftScheduler1
4.2 Core Elements
This section attempts to answer three important questions:
What metrics are we going to track?
What decisions do we intend to make?
What are the sources of uncertainty?
For this problem, the only metric we are interested in is the number of allocated shift slots for Shift1 after each decision window. The only source of uncertainty is the levels of demand for each of the resource types.
4.3 Mathematical Model | SUS Design
A Python class is used to implement the model for the SUS (System Under Steer):
class Model():
def __init__(self, S_0_info):
...
...
4.3.1 State variables
The state variables represent what we need to know.
\(x_{tab}\) is a boolean vector that indicates whether a specific resource is to be allocated to a demand
Decisions are made with a policy (TBD below):
\(X^{\pi}(S_t)\)
4.3.3 Exogenous information variables
The exogenous information variables represent what we did not know (when we made a decision). These are the variables that we cannot control directly. The information in these variables become available after we make the decision \(x_t\).
When we assume that the demand in each time period is revealed, without any model to predict the demand based on past demands, we have, using approach 1:
We will make use of approach 1 which means that the exogenous information, \(W_{t+1}\), is the directly observed demands of the resources.
The exogenous information is obtained by a call to
DemandSimulator.simulate(...)
4.3.4 Transition function
The transition function describe how the state variables evolve over time. We have the equations:
\[
R^{Avail}_{t+1} =
\begin{cases}
1 & \text{if resource with attribute $a$ has not been allocated} \\
0 & \text{if resource with attribute $a$ has been allocated }
\end{cases}
\]
\[
R^{CumShifts}_{t+1} =
\begin{cases}
R^{CumShifts}_{t} + 1 & \text{if resource was allocated} \\
R^{CumShifts}_{t} & \text{if resource was not allocated }
\end{cases}
\]
Collectively, they represent the general transition function:
\[
S_{t+1} = S^M(S_t,X^{\pi}(S_t))
\]
4.3.5 Objective function
The objective function captures the performance metrics of the solution to the problem.
We can write the state-dependant reward (also called contribution due to the allocation of a resource with attribute \(b\)):
\[
C(S_t,x_t) =
\begin{cases}
1 & \text{if resource was allocated} \\
-1 & \text{if resource was not allocated }
\end{cases}
\]
4.3.6 Implementation of the System Under Steer (SUS) Model
class Model():def__init__(self, W_fn=None, S__M_fn=None, C_fn=None):self.S_t = {'R_t': pd.DataFrame({'ResourceId': RESOURCE_IDS,'Type': TYPES,'RAvail_t': AVAILABILITIES_DOW_Shift1['0_Sunday'],'RCumShifts_t': [0]*len(TYPES), ##cumulative allocs (for T) }),'D_t': pd.DataFrame({'Type': RESOURCE_TYPES,'DShift1_t': [1]*len(RESOURCE_TYPES),'DShift2_t': [1]*len(RESOURCE_TYPES), }), }self.x_t = {'xAlloc_t': pd.DataFrame({'Comb': abNAMES, ##Combination'Allocd_t': [False]*len(abNAMES), ##Allocated }), }self.Ccum =0.0##cumulative rewardself.Ccum_CumShifts =0.0self.Ccum_SickProb =0.0self.Ucum_Total =0##cumulative unallocated/unmet demands##cumulative unallocated/unmet demandsself.Ucum = {rt: 0for rt in RESOURCE_TYPES}## def reset(self):# self.Ccum = 0.0# self.Ucum = 0## exogenous information, dependent on a random process,## the directly observed demandsdef W_fn(self, t):return {'shift1': SIM.simulate(), 'shift2': SIM.simulate()}def update_Ccum(self, dt, S_t, x_t, theta): m1 = x_t['xAlloc_t'].merge(S_t['R_t'][['RCumShifts_t', 'RAvail_t']], left_index=True, right_index=True) m2 = m1.merge(SICK_PROBS[[dt.month_name()]], left_index=True, right_index=True) m2.rename(columns={dt.month_name(): 'SickProb'}, inplace=True) m2['Capacity'] = CAPACITIES.loc[:, ['Capacity']] m2['Ccum_CumShifts'] =-(m2['RCumShifts_t'] - m2['Capacity'])## m2['Ccum_SickProb'] = -100*m2['SickProb'] m2['Ccum_SickProb'] =-100*(m2['SickProb'] - m2['SickProb'].mean()) ##100 makes values more comparable with other component of Ccum## m2['Ccum_Avail'] = m2['RAvail_t'].replace({True: 0, False: -10}) summables = m2.loc[ m2['Allocd_t'] ==True, ['Ccum_CumShifts', 'Ccum_SickProb'],## ['Ccum_CumShifts', 'Ccum_SickProb', 'Ccum_Avail'] ] Ccum_CumShifts, Ccum_SickProb = summables.sum(axis=0)## Ccum_CumShifts, Ccum_SickProb, Ccum_Avail = summables.sum(axis=0) Ccum =\ theta.thCumShifts*Ccum_CumShifts +\ theta.thSickProb*Ccum_SickProb## theta.thAvail*Ccum_Availself.Ccum_CumShifts += Ccum_CumShiftsself.Ccum_SickProb += Ccum_SickProbself.Ccum += Ccumdef performAllocDecision(self, S_t, x_t, theta):## find list of ResourceIds for allocs from x_t resourceIds = x_t['xAlloc_t'].loc[ x_t['xAlloc_t']['Allocd_t']==True, ['Comb'] ]['Comb'].str.split('_').str[:1].tolist();##print(f'{resourceIds=}') resourceIds_flat = [e[0] for e in resourceIds];##print(f'{resourceIds_flat=}')## update state of allocs S_t['R_t'].loc[ S_t['R_t']['ResourceId'].isin(resourceIds_flat), ['RAvail_t'] ] =False S_t['R_t'].loc[ S_t['R_t']['ResourceId'].isin(resourceIds_flat), ['RCumShifts_t'] ] +=1## update Ccum with allocations## self.Ccum += len(resourceIds_flat) #number of allocationsdef S__M_fn(self, t, dt, S_t, x_t, W_tt1, theta):## perform decision taken this morningself.performAllocDecision(S_t, x_t, theta)## D_t #direct approachfor rt in RESOURCE_TYPES: sh1_demands = W_tt1['shift1'][rt] sh2_demands = W_tt1['shift2'][rt] S_t['D_t'].loc[S_t['D_t']['Type']==rt, 'DShift1_t'] = sh1_demands S_t['D_t'].loc[S_t['D_t']['Type']==rt, 'DShift2_t'] = sh2_demands## Update availabilities of all resources dow = (t +1)%7 mask = AVAILABILITIES_DOW_Shift1.columns.str.contains(str(dow) +'_') dow_col = AVAILABILITIES_DOW_Shift1.loc[:, mask] S_t['R_t']['RAvail_t'] = AVAILABILITIES_DOW_Shift1[dow_col.columns[0]] record_t = [t, dt] +\list(S_t['R_t']['RAvail_t']) +\list(S_t['R_t']['RCumShifts_t']) +\list(S_t['D_t']['DShift1_t']) +\ [self.Ucum[rt] for rt in RESOURCE_TYPES] +\ [self.Ucum_Total] +\ [self.Ccum_CumShifts] +\ [self.Ccum_SickProb] +\ [self.Ccum] +\list(x_t['xAlloc_t']['Allocd_t'])return record_tdef C_fn(self, S_t, x_t, W_tt1, theta):returndef step(self, t, dt, theta):## IND = '\t\t'## print(f"{IND}..... M. step() .....\n{t=}\n{theta=}") W_tt1 =self.W_fn(t);##print(f'{W_tt1=}')## update state & reward record_t =self.S__M_fn(t, dt, self.S_t, self.x_t, W_tt1, theta)return record_t
4.4 Uncertainty Model
We will simulate the rental demand vector \(D^{Shift1}_{t+1}\) as described in section 2.
4.5 Policy Design
There are two main meta-classes of policy design. Each of these has two subclasses: - Policy Search - Policy Function Approximations (PFAs) - Cost Function Approximations (CFAs) - Lookahead - Value Function Approximations (VFAs) - Direct Lookaheads (DLAs)
In this project we will only use one approach: - A simple allocate parameterized policy (from the PFA class), called X__Alloc.
## setup labels to plot infoRAvail_t_labels = ['RAvail_t_'+an for an in aNAMES]RCumShifts_t_labels = ['RCumShifts_t_'+an for an in aNAMES]DShift1_t_labels = ['DShift1_t_'+rt for rt in RESOURCE_TYPES]xAlloc_t_labels = ['Allocd_t_'+abn for abn in abNAMES]labels = ['piName', 'theta', 'l'] +\ ['t', 'dt'] +\ RAvail_t_labels + RCumShifts_t_labels +\ DShift1_t_labels +\ ['Ucum_'+rt for rt in RESOURCE_TYPES] +\ ['Ucum_Total'] +\ ['Ccum_CumShifts'] +\ ['Ccum_SickProb'] +\ ['Ccum'] +\ xAlloc_t_labels
## def grid_search_thetas(thetas1, thetas2, thetas1_name, thetas2_name):# thetas = [# P.build_theta({thetas1_name: thA0, thetas2_name: thB0})# for thA0 in thetas1# for thB0 in thetas2# ]# return thetas## def grid_search_thetas(thetas1, thetas1_name):# thetas = [# P.build_theta({thetas1_name: thA0})# for thA0 in thetas1# ]# return thetas
## print out the 14-day (2-week) scheduleprint(f"SCHEDULE:")for res_alloc in resource_allocs: _,_,id,resType,_,_,_ = res_alloc.split('_') resName =id+'_'+resTypeprint(f'\n{resName}:') sched_list =list(schedule.loc[ schedule[res_alloc] ==True, ['dt', res_alloc] ]['dt'])print(f"{[ts.strftime('%a %b %d %Y') for ts in sched_list]}")
SCHEDULE:
1_Courtesy:
['Sun Oct 29 2023', 'Tue Oct 31 2023', 'Sun Nov 05 2023']
2_Courtesy:
['Mon Oct 30 2023', 'Tue Oct 31 2023', 'Wed Nov 01 2023', 'Thu Nov 02 2023', 'Fri Nov 03 2023', 'Mon Nov 06 2023', 'Wed Nov 08 2023', 'Thu Nov 09 2023', 'Fri Nov 10 2023']
3_Courtesy:
['Wed Nov 01 2023', 'Thu Nov 02 2023', 'Sat Nov 04 2023', 'Mon Nov 06 2023', 'Tue Nov 07 2023', 'Thu Nov 09 2023', 'Sat Nov 11 2023']
4_Courtesy:
['Tue Oct 31 2023', 'Wed Nov 01 2023', 'Thu Nov 02 2023', 'Mon Nov 06 2023', 'Wed Nov 08 2023', 'Thu Nov 09 2023', 'Sat Nov 11 2023']
5_Courtesy:
['Thu Nov 02 2023', 'Fri Nov 03 2023', 'Mon Nov 06 2023', 'Fri Nov 10 2023']
6_Courtesy:
['Wed Nov 01 2023', 'Fri Nov 03 2023', 'Sun Nov 05 2023', 'Fri Nov 10 2023']
7_Courtesy:
['Wed Nov 01 2023', 'Mon Nov 06 2023', 'Wed Nov 08 2023', 'Sat Nov 11 2023']
8_Stocker:
['Sun Oct 29 2023', 'Mon Oct 30 2023', 'Tue Oct 31 2023', 'Wed Nov 01 2023', 'Fri Nov 03 2023', 'Sat Nov 04 2023', 'Sun Nov 05 2023', 'Mon Nov 06 2023', 'Tue Nov 07 2023', 'Sat Nov 11 2023']
9_Stocker:
['Mon Oct 30 2023', 'Tue Oct 31 2023', 'Wed Nov 01 2023', 'Thu Nov 02 2023', 'Fri Nov 03 2023', 'Sun Nov 05 2023', 'Mon Nov 06 2023', 'Tue Nov 07 2023', 'Fri Nov 10 2023']
10_Stocker:
['Thu Nov 02 2023', 'Sat Nov 04 2023', 'Sun Nov 05 2023', 'Sat Nov 11 2023']