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 daily-changing 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.

  • 1.1. Formulation → 1.2. Data creation → 1.3. Implementation by Amplify → 1.4. Solve.

• 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.

  • 2.1. Formulation → 2.2. Data creation → 2.3. Implementation by Amplify → 2.4. Solve.

• 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.

  • 3.1. Formulation → 3.2. Data creation → 3.3. Implementation by Amplify → 3.4. Solve.

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$ and 0 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.

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 VariableGenerator class.

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.

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*} $$

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} $$

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.

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 high-priority 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.

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.

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).

Next, a solver is created from the configured client to optimize the formulated model. After solving, the solution is retrieved using the evaluate method to obtain the solution in the form corresponding to the decision variable matrix location_variables. The obtained solution is stored in 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.

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.

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)

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 not 0 ($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 not 0 ($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.

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 non-managerial employees (staff) to be assigned is num_employees_any_position - num_managers - num_submanagers.

Each employee's work location preference for each store is stored in 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.

Now we set up the correspondence between employee IDs, store names, and position titles and indices as follows.

2.3. Implementation with Amplify¶

Now we will implement the formulations using Amplify.

First, create the variable position_variables representing the decision variable $M$ using VariableGenerator. Note that unlike Step 1, this is a three-dimensional array of employees, positions, and stores.

Similar to Step 1, the decision variable for the store $l$ will be zero-padded 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 zero-padded. This reduces the size of the final problem to be solved.

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):

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"].

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} $$

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.

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.

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 evaluate 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.

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.

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.

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 zero-cooking 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)
• $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)
• $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)

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 not 0 ($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 not 0 ($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 not 0 ($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 role-related 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.

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.

Each employee's work preference for each store is stored in 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.

Now we set up the correspondence between employee IDs, store names, position titles, roles, cooking skills, and indices as follows.

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 VariableGenerator. These are 3-dimensional 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.

Similarly to the previous steps, the decision variable is zero-padded 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 zero-padded. This reduces the size of the final problem to be solved.

As for the location_variables representing $L$, the relation between the decision variables $P$ and $L$ can be used as follows (3.1. Formulation.

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*} $$

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} $$

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.

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.

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 evaluate 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.

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.

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.

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.

It shows that the required number of employees with the required position have been successfully assigned in all stores.