Employee Assignment Problem¶
Optimal assignment of employees to stores is an important task for retail and service industries with a large number of employees. Typically, such assignment processes must take into account each employee's position, skills, and preferred work location, as well as a variety of dailychanging tasks in each store.
Here, we address the combinatorial optimization problem of employee assignment, using a restaurant chain as an example. In particular, we aim to assign employees appropriately according to position, skill type and level, position, and desired work location.
For example, an employee may have the following attributes:
Position
 Store manager
 Assistant manager
 Staff (no position)
Role
 Kitchen staff
 Floor staff
Skill level
 Cooking Skills
For a sushi chain restaurant considered in Step 3: Filleting skill
 Nigiri (hand role) skill
 Soup cooking skill
 A la carte dish preparation skill
Work location preference
 For each work location, an employee has one of the following preference:
 Unavailable
 Available
 Preferred
In addition, suppose that the following requirements must be met at each store.
 Requirements
 Number of people required for each position and role
 Type and level of culinary skills required
Here, we attempt to assign all employees to stores based on the above requirements and attributes. In addition, employee assignments are made to minimize the variation in fill rate among the stores.
Since it is complex to consider all the requirements at once, we implement the solver following the steps below.

Step 1
Employees are assigned to each store based on their work location preferences and the number of employees needed for each store, regardless of each employee's position, role, or skill level. 
Step 2
In addition to the requirements addressed in Step 1, we consider the position requirements so that the required number of employees for each position is appropriately assigned to each store. 
Step 3
Finally, we will look at the remaining requirements, which are the role and skill level of the employees, as well as the cooking skill requirements in each store.
Now, we follow the above steps to formulate the problem and implement the formulation.
Step 1¶
In this step, employees are assigned to each store, based on each employee's work location preference and the number of employees required for each store.
Suppose each store requires several employees, while each employee has a work preference for each store. Their preference levels are expressed as integers between 0 and 2 for each store, corresponding to the following: unavailable, available, and preferred.
 Unavailable → Preference level: 0
 Available → Preference level: 1
 Preferred → Preference level: 2
Our goal is to assign employees to stores in a way that matches the number of employees to the needs of the stores, while satisfying employees' location preferences as much as possible.
1.1. Formulation¶
First, we define sets, constants, and decision variables used in the formulation.
Sets¶
 $W$: the set of employees (the symbol $i \in W$ is used to denote employees)
 $S$: the set of stores (the symbol $l \in S$ is used to denote stores)
Constants¶
 $r_{l}$: the number of employees needed for store $l$ ($l \in S$)
 $c_{i,l}$: preference of employee $i$ to work in store $l$ ($i \in W$ and $l \in S$)
Decision variables¶
 $L_{i,l}\in \{0,1\}$:
1
if employee $i$ is assigned to store $l$ and0
if not ($i\in W$ and $l\in S$)
We optimize which store to assign to an employee. Therefore, the decision variable $L$ is declared as
a
binary variable matrix of size [number of employees] x [number of stores]
.
For example, if the number of employees is 5 and there are two stores, "Hakata Store" and "Tenjin
Store",
it is represented by a 2 x 5
binary variable matrix as follows.
Employee $i$  Hakata ($l=0$)  Tenjin ($l=1$) 

$0$  $L_{0,0}$  $L_{0,1}$ 
$1$  $L_{1,0}$  $L_{1,1}$ 
$2$  $L_{2,0}$  $L_{2,1}$ 
$3$  $L_{3,0}$  $L_{3,1}$ 
$4$  $L_{4,0}$  $L_{4,1}$ 
Objective function¶
When making assignments, it is important to consider the fill rate of the assigned employees with respect to the number of employees required by each store. The fill rate $w_l$ of store $l$ is the ratio of "the number of employees assigned to store $l$" to "the number of employees required by the store $r_l$", and can be defined as follows:
$$ w_l = \frac{1}{r_l} \displaystyle\sum_{i\in W} L_{i,l}. $$
In other words, if the fill rate is greater than or equal to 1, the requirement $r_l$ is satisfied; if it is less than 1, the requirement is not satisfied.
In general, it is undesirable for the fill rate to vary from store to store. Therefore, we consider the following three factors. Here, $\langle \cdot \rangle$ denotes the average operation.

Maximize the average of the fill rate $w_l$
$$ \begin{matrix} {\rm maximize} & \langle w_l \rangle \end{matrix} $$ 
Minimize the variance of the fill rate $w_l$
$$ \begin{matrix} {\rm minimize} & \langle w_l^2 \rangle  \langle w_l \rangle^2 \end{matrix} $$ 
Maximize all employees' preferences of work location $c_{i,l}$ for allocated store $l$
$$ \begin{matrix} {\rm maximize}& \displaystyle \sum_{i\in W}\sum_{l\in S}c_{i,l}L_{i,l} \end{matrix} $$
Note that the work preference of employee $i$ for stores that are unassigned ($L_{i,l}=0$) is naturally irrelevant to the sum because $c_{i,l}L_{i,l}=0$.
Constraints¶
In the definition of the decision variable, the situation may arise where an employee can be assigned to more than one store at the same time. To avoid such assignments, we impose the following constraint that prohibits the same employee from being assigned to more than one store.
 Employee $i$ can only be assigned to one store at a time
$$ \sum_{l \in S}L_{i,l} = 1 \:\: (\forall i\in W) $$
Since the required number of employees $r_l$ is set for each store, and the total number of employees assigned to each store must be greater than or equal to $r_l$, the following constraint is given.

Each store $l$ is assigned a number of employees equal to or greater than its required number of employees $r_l$
$$ \sum_{i\in W}L_{i,l} \geq r_{l} \:\: (\forall l \in S) $$
1.2. Data Creation¶
We now define the problem setting for the employee assignment problem. As an example, we consider the following problem setting with 5 employees and 2 stores.
We use pandas.DataFrame
to store the data.
import pandas as pd
# Set the name of each store and the number of employees required
dict_req = {"location": ["tenjin", "hakata"], "num_employees": [2, 3]}
# Set the work location preference for each employee
dict_worker_loc = {
"worker_id": [0, 1, 2, 3, 4], # ID of the employee
"tenjin": [2, 2, 1, 0, 1], # Each employee's preference to work at tenjin store
"hakata": [1, 1, 1, 1, 0], # Each employee's desire to work at hakata stores
}
df_req = pd.DataFrame.from_dict(dict_req, orient="index").T
print("Number of employees requested for each store")
display(df_req)
df_worker_loc = pd.DataFrame.from_dict(dict_worker_loc, orient="index").T
print("\nEach employee's work location preference")
display(df_worker_loc)
workers = df_worker_loc["worker_id"].values
locations = df_req["location"].values
# Get the size of each data
num_workers = len(workers)
num_locations = len(locations)
# Create a dictionary with store names and their indices as keys and values, respectively
loc2idx = dict((v, i) for i, v in enumerate(df_req["location"].values))
# Create a dictionary with store indices and their names as keys and values, respectively
idx2loc = dict((i, v) for i, v in enumerate(df_req["location"].values))
1.3. Implementation with Amplify¶
Now we implement the formulations using Amplify.
First, create a binary variable matrix, location_variables
, representing the decision
variable $L$ using the BinarySymbolGenerator
class.
from amplify import BinarySymbolGenerator
gen = BinarySymbolGenerator()
# Binary variable indicating whether employee i is assigned to store l or not
location_variables = gen.array(num_workers, num_locations)
# The decision variables are a 5x2 matrix.
print(location_variables)
If the work location preference of employee $i$ for store $l$ is "unavailable", we know in advance
that
they will not work at that store, so we can assign a constant 0 to the corresponding element of the
location_variables
. This reduces the size of the final problem to be solved by annealing.
from itertools import product
# Assign 0 for locations where employee i is unable to work
for i, l in product(range(num_workers), locations):
worker_req = df_worker_loc.iloc[i][l]
# Unable to work based on work location preference
if worker_req == 0:
location_variables[i, loc2idx[l]] = 0
# In the decision variables, the element related to the store where the worker cannot work is zeropadded.
print(location_variables)
Next, we implement the formulation of the fill rate $w_l$ defined for the required number of employees in each store $l$. The fill rate $w_l$ is expressed as follows, as described in 1.1. Formulation:
$$ \begin{align*} w_l = \frac{1}{r_l} \displaystyle\sum_{i\in W} L_{i,l} \end{align*} $$
from amplify import sum_poly
w_l = location_variables.sum(axis=0) / df_req["num_employees"].values
Based on the fill rate defined above, we can now calculate each element of the objective function introduced in 1.1. Formulation. To maximize the function, we transform it into a minimization problem by considering its negative value.

Maximize the average of the fill rate $w_l$
(Convert to minimizing its negative value)
$$ \begin{matrix} {\rm minimize} & \langle w_l \rangle \end{matrix} $$

Minimize the variance of the fill rate $w_l$
$$ \begin{matrix} {\rm minimize} & \langle w_l^2 \rangle  \langle w_l \rangle^2 \end{matrix} $$

Maximize all employees' preferences of work location $c_{i,l}$ for assigned store $l$
(Convert to minimizing its negative value)
$$ \begin{matrix} {\rm minimize}& \displaystyle \sum_{i\in W}\sum_{l\in S}c_{i,l}L_{i,l} \end{matrix} $$
# Maximize average fill rate (minimize its negative values)
average_fill_rate_cost = ((w_l.sum() / w_l.size) ** 2)
# Minimize the fill rate variance
variance_fill_rate_cost = (w_l * w_l).sum() / w_l.size  (w_l.sum() / w_l.size) ** 2
# Maximize the employees' work location preference for the assigned store (minimize its negative values)
location_cost = sum_poly(
num_workers,
lambda i: sum_poly(
num_locations,
lambda l: df_worker_loc.loc[i][idx2loc[l]] * location_variables[i, l],
),
)
Finally, we will implement the constraints introduced in 1.1. Formulation.
Employee $i$ can only be assigned to one store at a time
$$ \sum_{l \in S}L_{i,l} = 1 \:\: (\forall i\in W) $$
Each store $l$ is assigned a number of employees equal to or greater than its required number of employees $r_l$
$$ \sum_{i\in W}L_{i,l} \geq r_{l} \:\: (\forall l \in S) $$
The first constraint is implemented using one_hot
(or equal_to
since it is
an
equality constraint). The second constraint expression is an inequality constraint, so we use
greater_equal
.
from amplify.constraint import equal_to, greater_equal, one_hot
# An employee i can be assigned to only one store at a time
location_constarints = sum(one_hot(location_variables[i]) for i in range(num_workers))
# In a store l, assign a number of employees greater than or equal to the store's required number of employees r_l
require_constraints = sum(
greater_equal(location_variables[:, l], df_req["num_employees"][l])
for l in range(num_locations)
)
The three objective functions and two constraint formulas implemented earlier are added together to create the model to be optimized.
Note that these objective functions and constraint expressions have different ranges of possible values. If optimization is performed on the combined model as it is, the objective or constraint equations with relatively small possible values will not be properly considered in the optimization. As a result, there is a possibility that only the objective or constraint equations with large possible values may be satisfied in the solution. In other words, if a highpriority objective function is intentionally given a large value, there is a high probability that this objective function will be optimized.
Therefore, it is sometimes necessary to multiply each objective and/or constraint function by one or
more
coefficients (weights) so that the range of possible values of all objective and constraint
expressions is
approximately the same, or so that the objective function is prioritized is relatively large. The
following loc_priority
, ave_fill_priority
, and
var_fill_priority
are the coefficients corresponding to the location preference, the average fill rate, and the variance
of
fill rate, respectively. Also, constraint_weight
is the weight for the constraint
equations.
Here, the coefficients are determined by considering the possible values of each objective function. For example, since the variance will be positive and small, you will need to give it a relatively large coefficient to be considered as an objective function.
# Coefficients of the respective objective function
loc_priority = 1
ave_fill_priority = 1
var_fill_priority = 10
# Objective function
cost_func = (
loc_priority * location_cost
+ ave_fill_priority * average_fill_rate_cost
+ var_fill_priority * variance_fill_rate_cost
)
The strength of the constraints must also be set appropriately. Since the constraint is given to the Ising machine as a penalty function for the objective function, it is determined by estimating a value slightly larger than the possible values of the objective function.
Here, we take $10$ as the weight. If no solution is found that satisfies the constraints, the weight of the constraints must be increased slightly and another attempt must be made.
On the other hand, if the used constraint weights are extremely high, the objective function will not be considered relatively in the optimization process, so care must be taken.
# Penalty function weights for constraint conditions
constraint_weight = 10
# Constraint
constraints = constraint_weight * (location_constarints + require_constraints)
# Add together the objective function and constraints to create the model to be optimized
model = cost_func + constraints
Formulation implementation is now complete.
1.4. Solution¶
First, set up the client for the Ising or quantum annealing machine to be used. This time, choose an
Ising machine, Fixstars Amplify AE (FixstarsClient
).
from amplify.client import FixstarsClient
# Setup the client
client = FixstarsClient()
# client.token = "xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx" # Enter Amplify AE access token for your environment
client.parameters.timeout = 1000 # Timeout 1 second
Next, a solver is created from the configured client to optimize the formulated model. After solving,
the
solution is retrieved using the decode
method to obtain the solution in the form
corresponding to the decision variable matrix location_variables
. The obtained solution
is
stored in location_solutions
.
from amplify import Solver
# Instantiate the solver class
solver = Solver(client)
# Pass the model to the solver to solve and obtain the result
result = solver.solve(model)
# If a solution that satisfies the constraints is not obtained, RuntimeError is issued (adjust weights, etc., and rerun)
if len(result) == 0:
raise RuntimeError("The given constraints are not satisfied")
values = result[0].values
# Retrieve the solution in the form corresponding to the `location_variables` variable matrix
location_solutions = location_variables.decode(values, 0)
print(location_solutions)
Results¶
From the obtained solution, we can extract the information about which store each employee is
assigned
to. If the result of the solution location_solutions[i][l] = 1
, it means that employee
$i$ is
assigned to store $l$. Therefore, by retrieving the index whose solution is $1$, we can know the
assigned
store for the employee $i$.
Store the result in a pandas.DataFrame
for tabular output.
import numpy as np
from collections import defaultdict
location_index_list = np.where(np.array(location_solutions) == 1)[1]
dict_df = defaultdict(list)
for i, loc_ind in enumerate(location_index_list):
worker_id = df_worker_loc.loc[i]["worker_id"]
# Store to be assigned to
loc = locations[loc_ind]
dict_df["worker_id"].append(worker_id)
dict_df["allocation"].append(loc)
df_result = pd.DataFrame.from_dict(dict_df, orient="index").T
print("Assigned store for each employee")
display(df_result)
Finally, check to what extent the solution meets the number of people required at each store. To do this, we can calculate the fill rate at each store by using the formulation defined in 1.1. Formulation.
# Count the number of times each store name appears in the `allocation` list in df_result = number of employees assigned to each store
num_employees_allocated = df_result["allocation"].value_counts()
fill_rate = df_req.copy()
fill_rate["fill rate"] = [
df_req.loc[l]["num_employees"] / num_employees_allocated[idx2loc[l]]
for l in range(num_locations)
]
print("Fill rate for each store")
display(fill_rate)
This confirms that the employee assignments were successfully optimized in Step 1 since the fill rate is greater than or equal to 1.0 in all stores.
Step 2¶
In Step 2, in addition to "each employee's preference for work location" and "the number of employees required for each store" considered in Step 1, we will assign employees to satisfy the number of employees for each position required at each store.
For example, there may be a store that requires one manager and three staff members.
We consider three positions which are store manager, assistant manager, and staff. Each employee has an attribute that indicates whether they can be assigned to each position, in addition to the work location preference mentioned above.
2.1. Formulation¶
First, we define the sets, constants, and decision variables to be used in the formulation.
Sets¶
 $W$: the set of employees (the symbol $i \in W$ is used to denote employees)
 $S$: the set of stores (the symbol $l \in S$ is used to denote stores)
 $R$: the set of positions (the symbol $j \in R$ is used to denote positions)
 $j=0$: manager (
manager
)  $j=1$: assistant manager (
submanager
)  $j=2$: staff (no position) (
staff
)
 $j=0$: manager (
Constants¶
 $r_{j,l}$: the number of required employees needed for position $j$ in store $l$ ($l \in S$ and $j \in R$)
 $c_{i,l}$: preference of work location $l$ for employee $i$ ($i \in W$ and $l \in S$)
 $m_{i,j}$: whether employee $i$ can be assigned to position $j$, 0: impossible, 1: possible ($i \in W$ and $j \in R$)
Decision variables¶
 $M_{i,j,l}$: whether assigning employee $i$ to store $l$ as position $j$
1
or not0
($i\in W$ and $j\in R$, $l\in S$)  $L_{i,l}\in \{0,1\}$: whether assigning employee $i$ to store $l$
1
or not0
($i\in W$ and $l\in S$) There is a relation $L_{i,l} = \sum_{j \in R} M_{i,j,l}$.
Objective function¶
As in Step 1, we define the fill rate $w_l$ of assigned employees to the required number of employees in each store regardless of the positions.
$$ w_l = \frac{\displaystyle \sum_{i\in W} L_{i,l}}{\displaystyle \sum_{j\in R} r_{j,l}} $$
As in Step 1, the following three objective functions are used.

Maximize the average of the fill rate $w_l$
$$ \begin{matrix} {\rm maximize} & \langle w_l \rangle \end{matrix} $$

Minimize the variance of the fill rate $w_l$
$$ \begin{matrix} {\rm minimize} & \langle w_l^2 \rangle  \langle w_l \rangle^2 \end{matrix} $$

Maximize all employee preferences for work location $c_{i,l}$ for assigned store $l$
$$ \begin{matrix} {\rm maximize}& \displaystyle \sum_{i\in W}\sum_{l\in S}c_{i,l}L_{i,l} \end{matrix} $$
Constraints¶
Similar to Step 1, when we define decision variables, a situation may arise where an employee can be assigned to more than one store at the same time. In addition, the required number of employees who can be a manager(s)/assistant manager(s) must be appropriately assigned to each store.
Therefore, the following constraints are imposed to properly assign the required number of employees with a managerial position to each store and to prohibit the same employee from being assigned to more than one store, regardless of whether the employee has a position or not.

Employee $i$ can only be assigned to one store at a time.
$$ \sum_{l \in S}L_{i,l} = 1 \:\:\:\: (\forall i\in W) $$

Each store $l$ is assigned a number of managerial employees $j \in \left\{0, 1 \right\}$ equal to its required number of managerial employees at each store.
$$ \sum_{i\in W}M_{i,j,l} = r_{j,l} \:\:\:\: (\forall l \in S, \forall j \in \left\{0, 1 \right\}) $$

Each store $l$ is assigned a number of employees equal to or greater than its required number of employees $r_l$
$$ \sum_{i\in W} L_{i,l} \geq \sum_{j\in R}r_{j,l} \:\:\:\: (\forall l \in S) $$
2.2. Data creation¶
Now we define the problem set to demonstrate the assignment problem. As an example, we will create the following data with 9 employees and 4 stores as an example.
import pandas as pd
# Set up information on the number of people requested for each store
dict_req = {
"location": ["tenjin", "hakata", "akasaka", "gakken"], # Store name
"num_managers": [
1,
1,
1,
1,
], # Number of required employees with manager position at each store
"num_submanagers": [
1,
0,
1,
1,
], # Number of requested employees with assistant manager position at each store
"num_employees_any_position": [
2,
2,
2,
2,
], # Number of employees requested for each store (all employees with or without managerial position)
}
df_req = pd.DataFrame.from_dict(dict_req, orient="index").T
# Set each employee's work location preference
dict_worker_loc = {
# ID of the employee
"worker_id": [0, 1, 2, 3, 4, 5, 6, 7, 8],
# Employee's work location preference for tenjin store
"tenjin": [2, 0, 0, 0, 1, 1, 2, 1, 1],
# Employee's work location preference for hakata store
"hakata": [1, 0, 0, 2, 2, 2, 1, 2, 1],
# Employee's work location preference for akasaka store
"akasaka": [1, 0, 0, 1, 0, 1, 1, 1, 2],
# Employee's work location preference for gakken store
"gakken": [1, 2, 2, 0, 0, 0, 0, 0, 0],
}
df_worker_loc = pd.DataFrame.from_dict(dict_worker_loc, orient="index").T
# Set each employee's position qualifications
dict_worker_skill = {
# ID of the employee
"worker_id": [0, 1, 2, 3, 4, 5, 6, 7, 8],
# Qualified as a manager 1 or not 0
"manager": [1, 1, 0, 0, 1, 1, 1, 0, 1],
# Qualified as an assistant manager 1 or not 0
"submanager": [1, 1, 1, 0, 1, 1, 1, 0, 1],
# Qualified as nonmanagerial position 1 or not 0
"staff": [1, 1, 1, 1, 1, 1, 1, 1, 1],
}
df_worker_skill = pd.DataFrame.from_dict(dict_worker_skill, orient="index").T
The number of required employees for the manager (manager
), assistant manager
(submanager
), and all employees (manager
+ submanager
+
staff
) for each store is stored in df_req
. The number of nonmanagerial
employees (staff
) to be assigned is
num_employees_any_position  num_managers  num_submanagers
.
print("Number of people requested by position per store")
display(df_req)
Each employee's work location preference for each store is stored in df_worker_loc
.
print("Work location preference for each store")
display(df_worker_loc)
The DataFrame df_worker_skill
contains the position qualification information for each
employee. If the value is $1$, it means that the employee can hold that position.
For example, an employee with worker_id = 1
can be a manager and an assistant manager. On
the
other hand, an employee with worker_id = 7
cannot be a store manager or assistant
manager.
print("Qualification by position for each employee")
display(df_worker_skill)
Now we set up the correspondence between employee IDs, store names, and position titles and indices as follows.
# Get employee ID, store name, and title
workers = df_worker_loc["worker_id"].values
locations = df_req["location"].values
positions = ["manager", "submanager", "staff"]
# Create a dictionary with a store index and its name as key and value, respectively
idx2loc = {i: v for i, v in enumerate(locations)}
# Create a dictionary with the store name and its index as key and value, respectively
loc2idx = {v: i for i, v in enumerate(locations)}
# Create a dictionary with the job title index and job title name as key and value, respectively
idx2position = {i: v for i, v in enumerate(positions)}
# Create a dictionary with the job title and its index as keys and values, respectively
position2idx = {v: i for i, v in enumerate(positions)}
# Get the size of each data
num_workers = len(workers)
num_locations = len(locations)
num_positions = len(positions)
# Binary variable indicating whether employee i is assigned 1 or not 0 to store l with position j
position_variables = BinarySymbolGenerator().array(
num_workers, num_positions, num_locations
)
# The decision variables are a 9x3x4 matrix.
print(position_variables)
Similar to Step 1, the decision variable for the store $l$ will be zeropadded if employee $i$ is "unavailable" in the work location preference attribute.
In addition, the elements that are not assignable in terms of "position" are also zeropadded. This reduces the size of the final problem to be solved.
for i, l in product(range(num_workers), locations):
worker_req = df_worker_loc.iloc[i][l]
if worker_req == 0:
# Employee i cannot be assigned at the store l based on their work location preference
position_variables[i, :, loc2idx[l]] = 0
for i, j in product(range(num_workers), positions):
worker_skill = df_worker_skill.iloc[i][j]
if worker_skill == 0:
# Employee i cannot be assigned to any store based on employee i's qualification for managerial positions
position_variables[i, position2idx[j], :] = 0
# Confirm that the decision variable elements for nonworking stores and positions are fixed at 0
print(position_variables)
For the location_variables
representing the decision variables $L$, the relation between
the
decision variables $M$ and $L$ can be used as follows (see 2.1
Formulation):
location_variables = position_variables.sum(axis=1)
display(location_variables)
Next, we implement the formulation of the fill rate $w_l$ for the required number of people in each store $l$. The fill rate $w_l$ is expressed as follows, as described in 2.1. Formulation:
$$ w_l = \frac{\displaystyle \sum_{i\in W} L_{i,l}}{\displaystyle \sum_{j\in R} r_{j,l}} $$
Here, the denominator $\sum_{j\in R} r_{j,l}$ is the number of all employees, regardless of position,
in
each store $l$, which corresponds to df_req["num_employees_any_position"]
.
# Calculation of the fill rate
w_l = location_variables.sum(axis=0) / df_req["num_employees_any_position"].values
With the fill rate defined above, we can now calculate each element of the objective function introduced in 2.1. Formulation. To maximize the function, we transform it into a minimization problem by considering its negative value.

Maximize the average of the fill rate $w_l$
(Convert to minimizing its negative value)
$$ \begin{matrix} {\rm minimize} & \langle w_l \rangle \end{matrix} $$

Minimize the variance of the fill rate $w_l$
$$ \begin{matrix} {\rm minimize} & \langle w_l^2 \rangle  \langle w_l \rangle^2 \end{matrix} $$

Maximize all employees' preferences of work location $c_{i,l}$ for assigned store $l$
(Convert to minimizing its negative value)
$$ \begin{matrix} {\rm minimize}& \displaystyle \sum_{i\in W}\sum_{l\in S}c_{i,l}L_{i,l} \end{matrix} $$
# Maximize average fill rate (minimize negative values of fill rate)
average_fill_rate_cost = ((w_l.sum() / w_l.size) ** 2)
# Minimize fill rate variance
variance_fill_rate_cost = (w_l * w_l).sum() / w_l.size  (w_l.sum() / w_l.size) ** 2
# Maximize all employees' preferences of work location for assigned store
location_cost = sum_poly(
num_workers,
lambda i: sum_poly(
num_locations,
lambda l: df_worker_loc.loc[i][idx2loc[l]] * location_variables[i][l],
),
)
Finally, we will implement the constraints introduced in 2.1. Formulation.
Employee $i$ can only be assigned to one store at a time.
$$ \sum_{l \in S}L_{i,l} = 1 \:\:\:\: (\forall i\in W) $$
Each store $l$ is assigned a number of managerial employees $j \in \left\{0, 1 \right\}$ equal to its required number of managerial employees at each store.
$$ \sum_{i\in W}M_{i,j,l} = r_{j,l} \:\:\:\: (\forall l \in S, \forall j \in \left\{0, 1 \right\}) $$
Each store $l$ is assigned a number of employees equal to or greater than its required number of employees $r_l$
$$ \sum_{i\in W} L_{i,l} \geq \sum_{j\in R}r_{j,l} \:\:\:\: (\forall l \in S) $$
The first and second constraints are implemented using one_hot
(or equal_to
since they are equality constraints). The third constraint is an inequality constraint, so we use
greater_equal
.
# Employee i can be assigned to only one store at a time
location_constarints = sum(one_hot(location_variables[i]) for i in range(num_workers))
# Assign the number of employees with position j required by each store l
req_manager_constraints = sum(
equal_to(position_variables[:, 0, l], df_req["num_managers"][l])
for l in range(num_locations)
)
req_submanager_constraints = sum(
equal_to(position_variables[:, 1, l], df_req["num_submanagers"][l])
for l in range(num_locations)
)
# Assign to each store l the number of employees (total number of all employees regardless of position) that is greater than or equal to the store's required number of employees r_l
req_employee_constraints = sum(
greater_equal(location_variables[:, l], df_req["num_employees_any_position"][l])
for l in range(num_locations)
)
The optimization model is created based on the objective function and constraint equations implemented above. Although it is necessary to set appropriate weights for the objective function and constraints for step 2 as well, the basic idea is as described in 1.3. Implementation by Amplify, and the same weights are given below.
# Coefficients of the objective function
loc_priority = 1
ave_fill_priority = 1
var_fill_priority = 10
# Objective function
cost_func = (
loc_priority * location_cost
+ ave_fill_priority * average_fill_rate_cost
+ var_fill_priority * variance_fill_rate_cost
)
# Weights of the penalty function representing the constraint
constraint_weight = 10
# Constraint
constraints = constraint_weight * (
location_constarints
+ req_manager_constraints
+ req_submanager_constraints
+ req_employee_constraints
)
# Add together the objective function and constraints to create the model to be optimized
model = cost_func + constraints
We have completed the implementation of the Step 2 formulation.
2.4. Solution¶
The model to be optimized is passed to the solver created in Step 1. After
solving, the solution is extracted using the decode
method to obtain the solution in the
form
corresponding to the decision variable matrices location_variables
and
position_variables
. Let location_solutions
and
position_solutions
be the obtained solutions, respectively.
# Pass model to the solver to solve and obtain the result
result = solver.solve(model)
# If a solution that satisfies the constraints is not obtained, RuntimeError is issued (adjust weights, etc., and rerun the solver)
if len(result) == 0:
raise RuntimeError("The given constraints are not satisfied")
values = result[0].values
# Retrieve the solution in the form corresponding to the `location_variables` matrix
location_solutions = location_variables.decode(values)
# Retrieve the solution in the form corresponding to the `position_variables` matrix
position_solutions = position_variables.decode(values)
Results¶
In the obtained optimal solution position_solutions
, if
position_solutions[i][j][l] = 1
, then employee $i$ works in store $l$ as position $j$.
Therefore, by retrieving the index of the matrix whose value is $1$, we can find out which employee is
assigned to which store and with which position.
import numpy as np
from collections import defaultdict
# Get the indices of positions and stores with position_solutions=1
(position_index_list, loc_index_list) = np.where(np.array(position_solutions) == 1)[1:]
dict_df = defaultdict(list)
for i, (j, l) in enumerate(zip(position_index_list, loc_index_list)):
worker_id = df_worker_loc.loc[i]["worker_id"]
# Assigned position
position = positions[j]
# Assigned store
loc = locations[l]
dict_df["worker_id"].append(worker_id)
dict_df["position"].append(position)
dict_df["location"].append(loc)
df_result = pd.DataFrame.from_dict(dict_df, orient="index").T
print("Store and position assignment for each employee")
display(df_result)
Finally, the fill rate for each position is visualized to verify that the required number of
employees
for each position is met in each store. Here, a cell in the table with a value of N/A
means
that the required number of employees for that position in that store is 0.
dict_result_alloc = defaultdict(lambda: defaultdict(int))
for loc, position in product(locations, positions):
dict_result_alloc[loc][position] = 0
for i in range(len(df_result)):
data = df_result.loc[i]
position = data["position"]
location = data["location"]
dict_result_alloc[location][position] += 1
df_result_alloc = pd.DataFrame.from_dict(dict_result_alloc, orient="index")
print("Number of people assigned by position")
display(df_result_alloc)
# Labels for the number of requested people for each store ['num_managers' 'num_submanagers' 'num_employees_any_position'].
num_positions_labels = df_req.columns.values[1 : 1 + num_positions]
dict_result_fill_rate = defaultdict(defaultdict)
# Calculate the fill rate for each store
for l in range(len(df_result_alloc)):
data = df_result_alloc.iloc[l] # df_result_alloc for store l
loc = data.name # Store name
num_req_non_staff = 0 # Variable to store the number of employees requested for each store by position
# Calculate the fill rate for each position.
for j in range(len(positions)):
# Number of employees requested for each store and each position
num_required = df_req[df_req["location"] == loc][num_positions_labels[j]].item()
# Number of employees required for each store. The last element of df_req is the number of all employees regardless of the position, so for the number of employees without positions, subtract the number of employees with positions num_req_non_staff from the number of all employees.
if j == len(positions)  1:
num_required = num_req_non_staff
else:
num_req_non_staff += num_required
# Number of employees assigned to each store and each position
num_allocated = data[positions[j]].item()
# Calculate the fill rate. If the number of employees required is zero, assign N/A
if num_required > 0:
dict_result_fill_rate[loc][f"{positions[j]} (fill rate)"] = (
num_allocated / num_required
)
else:
dict_result_fill_rate[loc][f"{positions[j]} (fill rate)"] = "N/A"
df_result_fill_rate = pd.DataFrame.from_dict(dict_result_fill_rate, orient="index")
print("Fill rate by position")
display(df_result_fill_rate)
We can see that the number of employees required for each position is met for all stores.
Step 3¶
In Step 3, in addition to the "each employee's work location preference", "the number of employees required for each store" and "required number of employees per position for each store" considered in Step 2, employee assignment is performed to meet the culinary skill requirements for each store based on each employee's role and skill level for each culinary skill.
Let us consider a sushi restaurant chain as an example. Each employee may have culinary skills such as "filleting, nigiri, soup cooking, and a la carte preparation," and the level of each skill is also quantified. On the other hand, each restaurant also has a required skill level for each skill type, and employees are assigned to meet that level.
For example, a sushi restaurant that requires a "filleting" skill of 10 requires that the sum of the "filleting" skills of all employees assigned to that restaurant must be at least 10.
While Step 2 used the fill rate defined based on the ratio of assigned employees to the required number of employees in each store without considering positions, Step 3 optimizes the fill rate based on each cooking skill requirement.
In addition, employees are assigned to either a "floor" or a "kitchen" role. The number of people who need to be assigned as floor staff is specified, and employees with zerocooking skills are automatically assigned as floor staff members.
3.1. Formulation¶
Redefine the variables and symbols used in the formulation.
Sets¶
 $W$: the set of employees (the symbol $i \in W$ is used to denote employees)
 $S$: the set of stores (the symbol $l \in S$ is used to denote stores)
 $R$: the set of positions (the symbol $j \in R$ is used to denote positions)
 $j=0$: manager (
manager
)  $j=1$: assistant manager (
submanager
)  $j=2$: staff (no position) (
staff
)
 $j=0$: manager (
 $K$: the set of cooking skills (use the symbol $k$ to denote skills)
 $k=0$: filleting skill (
filleting
)  $k=1$: nigiri (hand role) skill (
nigiri
)  $k=2$: soup cooking skill (
soup
)  $k=3$: skill in preparing a la carte (
a_la_carte
)
 $k=0$: filleting skill (
 $A$: the set of roles (use the symbol $h$ to denote a role)
 $h=0$: floor staff (
floor staff
)  $h=1$: kitchen staff (
kitchen staff
)
 $h=0$: floor staff (
Constants¶
 $t_{k,l}$: required skill level for cooking skill $k$ in restaurant $l$ ($l \in S$ and $k\in K$)
 $r_{l}$: required number of floor staff in store $l$ ($l \in S$)
 $c_{i,l}$: preference of employee $i$ for work location $l$ ($i \in W$ and $l \in S$)
 $m_{i,j}$: whether employee $i$ can be assigned to position $j$, 0: not possible, 1: possible ($i \in W$ and $j \in R$)
 $s_{i,k}$: the cooking skill level $k$ of employee $i$ has ($i \in W$ and $k\in K$)
Decision variables¶
 $M_{i,j,l}$: whether to assign employee $i$ to store $l$ as position $j$
1
or not0
($i\in W$ and $j\in R$, $l\in S$)  $P_{i,h,l}$: whether to assign employee $i$ to store $l$ as role $h$
1
or not0
($i\in W$, $h\in A$ and $l\in S$)  $L_{i,l}\in \{0,1\}$: whether to assign employee $i$ to store $l$
1
or not0
($i\in W$ and $l\in S$) There is a relation $L_{i,l} = \sum_{j \in R} M_{i,j,l}$.
 There is a relation $L_{i,l} = \sum_{h \in A} P_{i,h,l}$.
Objective functions¶
First, as in the previous steps, we define the fill rate as the basis for the objective function. In Step 3, we consider the fill rate $w_{k,l}$ of cooking skills $k$ to the total amount of skills needed $t_{k,l}$ at store $l$ as follows.
$$ w_{k,l} = \frac{1}{t_{k,l}} \displaystyle \sum_{i\in W} s_{i,k} P_{i,1,l} $$
Here, $s_{i,k} P_{i,1,l}$ yields the sum of the level of cooking skills $k$ of all employees assigned as kitchen staff members in store $l$, and $t_{k,l}$ is the requirements associated with those skill levels.
Also, as in the previous steps, the followings are used as the objective function.

Maximize the average of the fill rate $w_{k,l}$
$$ \begin{matrix} {\rm maximize} & \left< w_{k,l} \right> \end{matrix} $$

Minimize the variance of the fill rate $w_{k,l}$
$$ \begin{matrix} {\rm minimize} & \left< w_{k,l}^2 \right>  \left< w_{k,l} \right>^2 \end{matrix} $$

Maximize all employee preferences of work location $c_{i,l}$ for assigned store $l$
$$ \begin{matrix} {\rm maximize}& \displaystyle \sum_{i\in W}\sum_{l\in S}c_{i,l}L_{i,l} \end{matrix} $$
Constraints¶
The basic idea is the same as in Step 2, but we need an additional formulation that relates the rolerelated variables $P$ and $M$.

Employee $i$ can only be assigned to one store at a time
$$ \begin{align*} \sum_{l \in S}L_{i,l} = 1 \:\:\:\:(\forall i\in W) \end{align*} $$

Each store $l$ is assigned a number of managerial employees $j \in \left\{0, 1 \right\}$ equal to its required number of managerial employees at each store
$$ \forall l \in S, \forall j \in \left\{0, 1 \right\}, \sum_{i\in W}M_{i,j,l} = r_{j,l} $$

Each store $l$ is assigned a number of floor staff employees $h=0$ equal to the requirement
$$ \begin{align*} \forall l \in S, \sum_{i\in W} P_{i,0,l} = r_{l} \end{align*} $$

Constraints relating decision variables $P$ and $M$

Number of employees assigned to store $l$, regardless of position $j$, calculated from $M_{i,j,l}$:
$$ \sum_{j \in R} M_{i,j,l} $$

Number of employees assigned to store $l$, regardless of role $h$, calculated from $P_{i,h,l}$:
$$ \sum_{h \in A} P_{i,h,l} $$
Since these must be equal,
$$ \sum_{j \in R} M_{i,j,l} = \sum_{h \in A} P_{i,h,l} \:\:\:\:(\forall i\in W, \forall l \in S). $$

3.2. Data creation¶
Now, we will define the problem setting for the employee assignment problem for Step 3. As an example, we consider the following problem setting with 5 employees and 2 stores.
# Set up information on the number of people requested for each store
dict_req = dict(
location=["tenjin", "hakata"], # Store name
nun_managers=[
1,
1,
], # Number of people requested for each store with the manager position
num_submanagers=[
0,
1,
], # Number of required employees with the assistant manager position at each store
filleting=[1, 1], # Filleting skill level required
nigiri=[1, 2], # Nigiri skill level required
soup=[2, 2], # Soup cooking skill level required
a_la_carte=[2, 2], # A la carte preparation skill level required
num_floor_staff=[1, 1], # Number of required floor staff members in each store
)
df_req = pd.DataFrame.from_dict(dict_req, orient="index").T
# Set each employee's work location preference
dict_worker_loc = dict(
worker_id=[0, 1, 2, 50, 43], # ID of the employee
tenjin=[2, 1, 1, 1, 1], # Each employee's preference to work at tenjin store
hakata=[1, 2, 1, 1, 1], # Each employee's preference to work at hakata store
)
df_worker_loc = pd.DataFrame.from_dict(dict_worker_loc, orient="index").T
# Set each employee's position qualifications and skill information
dict_worker_skill = dict(
worker_id=[0, 1, 2, 50, 43], # ID of the employee
manager=[1, 1, 0, 0, 0], # Manager qualified 1 or not 0
submanager=[1, 1, 0, 1, 1], # Assistant manager qualified 1 or not 0
staff=[1, 1, 1, 1, 1], # Qualified as nonpositional employee 1 or not 0
filleting=[2, 2, 0, 1, 1], # Level of filleting skill
nigiri=[2, 2, 0, 2, 2], # Level of nigiri skill
soup=[2, 2, 0, 0, 0], # Level of soup cooking skill
a_la_carte=[2, 2, 0, 1, 1], # Level of a la carte preparation skill
)
df_worker_skill = pd.DataFrame.from_dict(dict_worker_skill, orient="index").T
The number of managers and assistant managers, the overall level of cooking skills required, and the
number of floor staffs required for each store are defined in df_req
.
print("Number of people requested by position")
display(df_req)
Each employee's work preference for each store is stored in df_worker_loc
.
print("Work preference for each store")
display(df_worker_loc)
The df_worker_skill
DataFrame contains the position qualification and cooking skill
information for each employee. For manager
and submanager
, if the value is
$1$,
the employee can take these positions. The constants filleting
, nigiri
,
soup
, and a_la_carte
represent their cooking skill level. If all the cooking
skill levels are $0$, the employee cannot be a kitchen staff.
print("Skill information by position for each employee")
display(df_worker_skill)
Now we set up the correspondence between employee IDs, store names, position titles, roles, cooking skills, and indices as follows.
# Get employee ID, store name, position name, role name, and cooking skill name
workers = df_worker_loc["worker_id"].values
locations = df_req["location"].values
positions = ["manager", "submanager", "staff"]
# Role name
assigns = ["floor", "kitchen"]
# Name of cooking skill
skills = ["filleting", "nigiri", "soup", "a_la_carte"]
# Create a dictionary with store indices and store names as keys and values, respectively
idx2loc = dict((i, v) for i, v in enumerate(locations))
# Create a dictionary with store names and their indices as keys and values, respectively
loc2idx = dict((v, i) for i, v in enumerate(locations))
# Create a dictionary with positions index and position names as keys and values, respectively
idx2position = dict((i, v) for i, v in enumerate(positions))
# Create a dictionary with position names and their indices as keys and values, respectively
position2idx = dict((v, i) for i, v in enumerate(positions))
# Create a dictionary with cooking skill indices and the cooking skill names as keys and values, respectively
idx2skill = dict((i, v) for i, v in enumerate(skills))
# Create a dictionary with cooking skill names and their indices as keys and values, respectively
skill2idx = dict((v, i) for i, v in enumerate(skills))
# Get the size of each data
num_workers = len(workers)
num_locations = len(locations)
num_positions = len(positions)
num_assigns = len(assigns)
num_skills = len(skills)
3.3. Implementation with Amplify¶
Let us implement the formulations with Amplify.
First, we will create position_variables
for the variable $M$ and
assign_variables
for the variable $P$ using BinarySymbolGenerator
. These are
3dimensional arrays of
[number of employees] x [number of positions] x [number of stores]
and [number of employees] x [number of roles] x [number of stores]
, respectively.
# Decision variable representing employee i working at store l with position j
gen = BinarySymbolGenerator()
position_variables = gen.array(num_workers, num_positions, num_locations)
# Decision variable representing employee i working in store l in role h
assign_variables = gen.array(num_workers, num_assigns, num_locations)
Similarly to the previous steps, the decision variable is zeropadded for the store $l$, where employee $i$ is "unavailable" in the work location preference attribute.
In addition, the elements that are not assignable in terms of position or role are also zeropadded. This reduces the size of the final problem to be solved.
for i, l in product(range(num_workers), locations):
worker_req = df_worker_loc.iloc[i][l]
if worker_req == 0:
# Store allocation is not possible for all positions for this employee
position_variables[i, :, loc2idx[l]] = 0
# Store allocation is not allowed for all roles for this employee
assign_variables[i, :, loc2idx[l]] = 0
for i, j in product(range(num_workers), positions):
worker_skill = df_worker_skill.iloc[i][j]
if worker_skill == 0:
# The employee i cannot be assigned for this particular position j
position_variables[i, position2idx[j], :] = 0
for i in range(num_workers):
if all(df_worker_skill.iloc[i][k] == 0 for k in skills):
# This employee i cannot take a kitchen role in any stores
assign_variables[i, 1, :] = 0
# Variables related to stores and positions that cannot be assigned are fixed to 0
print(position_variables)
# Variables related to nonassignable stores/roles are fixed to 0
print(assign_variables)
As for the location_variables
representing $L$, the relation between the decision
variables
$P$ and $L$ can be used as follows (3.1. Formulation.
location_variables = assign_variables.sum(axis=1)
display(location_variables)
Next, we calculate the fill rate $w_{k,l}$ for each store and each cooking skill. The fill rate $w_{k,l}$ is defined as follows, as explained in 3.1. Formulation:
$$ \begin{align*} w_{k,l} = \frac{1}{t_{k,l}} \displaystyle \sum_{i\in W} s_{i,k} P_{i,1,l} \end{align*} $$
from amplify import BinaryPolyArray
# Calculate the fill rate w_kl for each store and each cooking skill
w_kl = BinaryPolyArray(
[
sum_poly(
df_worker_skill[idx2skill[k]] * assign_variables[:, 1, l],
)
/ df_req[idx2skill[k]][l]
for k in range(num_skills)
for l in range(num_locations)
]
)
Next, compute each element of the objective function introduced in 3.1. Formulation. For the function to be maximized, we transform it into a minimization problem by considering its negative value.

Maximize the average of the fill rate $w_{k,l}$
(Convert to minimizing its negative value)
$$ \begin{matrix} {\rm minimize} & \langle w_{k,l} \rangle \end{matrix} $$

Minimize the variance of the fill rate
$$ \begin{matrix} {\rm minimize} & \langle w_{k,l}^2 \rangle  \langle w_{k,l} \rangle^2 \end{matrix} $$

Maximize all employees' preferences of work location $c_{i,l}$ for allocated store $l$
(Convert to minimizing its negative value)
$$ \begin{matrix} {\rm minimize}& \displaystyle \sum_{i\in W}\sum_{l\in S}c_{i,l}L_{i,l} \end{matrix} $$
# Maximize the average fill rate (minimize its negative value)
average_fill_rate_cost = ((w_kl.sum() / w_kl.size) ** 2)
# Minimize the fill rate variance
variance_fill_rate_cost = (w_kl * w_kl).sum() / w_kl.size  (
w_kl.sum() / w_kl.size
) ** 2
# Maximize employees' work location preference (minimize its negative value)
location_cost = sum_poly(
num_workers,
lambda i: sum_poly(
num_locations,
lambda l: df_worker_loc.loc[i][idx2loc[l]] * location_variables[i, l],
),
)
Finally, implement the following constraints as defined in 3.1. Formulation.
Employee $i$ can only be assigned to one store at a time
$$ \begin{align*} \forall i\in W, \sum_{l \in S}L_{i,l} = 1 \end{align*} $$
Each store $l$ is assigned a number of managerial employees $j \in \left\{0, 1 \right\}$ equal to its required number of managerial employees at each store
$$ \forall l \in S, \forall j \in \left\{0, 1 \right\}, \sum_{i\in W}M_{i,j,l} = r_{j,l} $$
Each store $l$ is assigned a number of floor staff employees $h=0$ equal to the requirement
$$ \begin{align*} \forall l \in S, \sum_{i\in W} P_{i,0,l} = r_{l} \end{align*} $$
Constraints relating decision variables $P$ and $M$
$$ \sum_{j \in R} M_{i,j,l} = \sum_{h \in A} P_{i,h,l} \:\:\:\:(\forall i\in W, \forall l \in S) $$
Use one_hot
or equal_to
since these are equality constraints.
# An employee i can be assigned to only one store at a time
location_constarints = sum(one_hot(location_variables[i]) for i in range(num_workers))
# The number of managerial employees (j=0 or 1) assigned is equal to the number of employees requested by store l
req_manager_constraints = sum(
equal_to(position_variables[:, 0, l], df_req["nun_managers"][l])
for l in range(num_locations)
)
req_submanager_constraints = sum(
equal_to(position_variables[:, 1, l], df_req["num_submanagers"][l])
for l in range(num_locations)
)
# Assign a number of floor staff employees (h=0) equal to the number of employees required by each store l
req_hall_constraints = sum(
equal_to(assign_variables[:, 0, l], df_req["num_floor_staff"][l])
for l in range(num_locations)
)
# Constraints associating decision variables P and M
role_assign_constraints = sum(
equal_to(
(position_variables.sum(axis=1))[i, l]  (assign_variables.sum(axis=1))[i, l], 0
)
for i in range(num_workers)
for l in range(num_locations)
)
The optimization model is created based on the objective function and constraint equations implemented above. Although it is necessary to set appropriate weights for the objective function and constraints for Step 2 as well, the basic idea is as described in 1.3. Implementation by Amplify, and the same weights are given below.
# Coefficients of the respective objective function
loc_priority = 1
ave_fill_priority = 1
var_fill_priority = 10
# Objective function
cost_func = (
loc_priority * location_cost
+ ave_fill_priority * average_fill_rate_cost
+ var_fill_priority * variance_fill_rate_cost
)
# weights of the penalty function representing the constraint
constraint_weight = 10
# Constraint
constraints = constraint_weight * (
location_constarints
+ req_manager_constraints
+ req_submanager_constraints
+ req_hall_constraints
+ role_assign_constraints
)
# Add together the objective function and constraints to create the model to be optimized
model = cost_func + constraints
This completes the implementation as far as the formulation of Step 3 is concerned.
3.4. Solution¶
The model to be optimized is passed to the solver created in Step 1. After
solving, the solution is extracted using the decode
method to obtain the solution in the
form
corresponding to the decision variable matrices location_variables
,
position_variables
, and assign_variables
. Let
location_solutions
,
position_solutions
, and assign_solutions
be the obtained solutions,
respectively.
# Pass the model to the solver to solve and obtain the result
result = solver.solve(model)
# If a solution that satisfies the constraints is not obtained, RuntimeError is issued (adjust weights, etc., and rerun the solver).
if len(result) == 0:
raise RuntimeError("The given constraints are not satisfied")
values = result[0].values
# Retrieve the solution in the form corresponding to the decision variable matrix `location_variables` for the assigned stores
location_solutions = location_variables.decode(values)
# Extract the solution in the form corresponding to the `role_variables` matrix of decision variables for the allocated stores and positions
position_solutions = position_variables.decode(values)
# Extract the solution in the form corresponding to the `assign_variables` matrix of decision variables for assigned stores and roles
assign_solutions = assign_variables.decode(values)
Results¶
In the obtained optimal solution position_solutions
, if
position_solutions[i][j][l] = 1
, then employee $i$ works in store $l$ as position $j$.
Therefore, by retrieving the index of the matrix whose value is $1$, we can find out which employee is
assigned to which store and as which position.
import numpy as np
from collections import defaultdict
(role_index_list, loc_index_list) = np.where(np.array(position_solutions) == 1)[1:]
dict_df = defaultdict(list)
for i, (j, l) in enumerate(zip(role_index_list, loc_index_list)):
## Assigned work location
worker_id = df_worker_loc.loc[i]["worker_id"]
position = positions[j]
loc = locations[l]
dict_df["worker_id"].append(worker_id)
dict_df["position"].append(position)
dict_df["location"].append(loc)
df_result = pd.DataFrame.from_dict(dict_df, orient="index").T
print("Store and position assignment for each employee")
display(df_result)
Next, we will check how well the required skill levels are met for each store. Whether the employee
is
assigned to floor
or kitchen
is taken from the result of
assign_solutions
, and in the case of kitchen
, the level of cooking skills of
each employee is accumulated for each store. In addition to the cooking skills, the number of floor
staff
members will also be accumulated for the purpose of calculating the fill rate.
In each cell of the table, the fill rate calculated by Total quantity / Required quantity is shown.
(assign_list, loc_index_list) = np.where(np.array(assign_solutions) == 1)[1:]
dict_result_loc = defaultdict(lambda: defaultdict(int))
for i, (j, l) in enumerate(zip(assign_list, loc_index_list)):
assign = assigns[j]
worker_id = df_worker_loc.loc[i]["worker_id"]
loc = locations[l]
if assign == "kitchen":
# If kitchen, add up all cooking skills.
for skill in skills:
dict_result_loc[loc][skill] += df_worker_skill.loc[i][skill]
else:
# also count the number of employees assigned as floor staff
dict_result_loc[loc]["floor"] += 1
df_result_loc = pd.DataFrame.from_dict(dict_result_loc, orient="index")
dict_result = defaultdict(defaultdict)
for i in range(len(df_result_loc)):
loc = df_result_loc.iloc[i].name
# Calculate the fill rate for all cooking skills
for skill in skills:
require_num_skill = df_req[df_req["location"] == loc][skill].item()
satisfy_num_skill = df_result_loc.iloc[i][skill].item()
dict_result[loc][
f"{skill} (fill rate)"
] = f"{satisfy_num_skill/require_num_skill}"
# Calculate the fill rate for the number of floor staff employees
require_num_skill = df_req[df_req["location"] == loc]["num_floor_staff"].item()
satisfy_num_skill = df_result_loc.iloc[i]["floor"].item()
dict_result[loc][
"floor staffs (fill rate)"
] = f"{satisfy_num_skill/require_num_skill}"
df_result_skills = pd.DataFrame.from_dict(dict_result, orient="index")
print("Fill rate for the amount of required skills")
display(df_result_skills)
The table above shows that the required skill levels and the number of floor staff members are satisfied in each store.
We will also verify that the required number of employees is met for each position in each store. The
fill rate is calculated for each position. Here, a cell in the table with N/A
means that
the
required number of employees for that position in that store is 0.
dict_result_alloc = defaultdict(lambda: defaultdict(int))
for loc, position in product(locations, positions):
dict_result_alloc[loc][position] = 0
for i in range(len(df_result)):
data = df_result.loc[i]
position = data["position"]
location = data["location"]
dict_result_alloc[location][position] += 1
df_result_alloc = pd.DataFrame.from_dict(dict_result_alloc, orient="index")
print("Number of employees assigned by position")
display(df_result_alloc)
# Labels for each store's requested managerial positions ['num_managers' 'num_submanagers']
num_positions_labels = df_req.columns.values[1:num_positions]
dict_result_fill_rate = defaultdict(defaultdict)
# Calculate fill rate for each store
for l in range(len(df_result_alloc)):
data = df_result_alloc.iloc[l] # df_result_alloc for store l
loc = data.name # Store name
# Calculate the fill rate for each position.
for j in range(len(positions)  1):
# Number of employees required for each store and each position
num_required = df_req[df_req["location"] == loc][num_positions_labels[j]].item()
# Number of employees assigned to each store and each position
num_allocated = data[positions[j]].item()
# Calculate the fill rate. If number of employees required is zero, assign N/A
if num_required > 0:
dict_result_fill_rate[loc][f"{positions[j]} (fill rate)"] = (
num_allocated / num_required
)
else:
dict_result_fill_rate[loc][f"{positions[j]} (fill rate)"] = "N/A"
df_result_fill_rate = pd.DataFrame.from_dict(dict_result_fill_rate, orient="index")
print("Fill rate by position for each store")
display(df_result_fill_rate)
It shows that the required number of employees with the required position have been successfully assigned in all stores.