problems of the past

current achievements

condition data

• Time required for each task
• Number of employees required for each task
• Workable hours for each employee

The table below shows two files of condition data that we have prepared.

In addition, this time, in order to introduce it on the blog, I will replace the employee name and work content with dummy content.

📄 Working hours per employee (employee_dummy.csv)

📄 Time required for each task and number of employees (task_dummy.csv)

Prepare variables

We put real staffing problems into the world of formulas.

Specifically, I created an objective function to be maximized/minimized and a constraint expression that sets the constraint conditions for each variable.

$\mathrm{<!--wovn-src:n-->n}$人の社員$\mathrm{<!--wovn-src:E-->E}=\left\{1, 2, ..., \mathrm{<!--wovn-src:n-->n}\right\}$に$\mathrm{<!--wovn-src:m-->m}$個の業務$\mathrm{<!--wovn-src:J-->J}=\left\{1, 2, ..., \mathrm{<!--wovn-src:m-->m}\right\}$を割り当てます。

各業務を終えるのに必要な時間$\mathrm{<!--wovn-src:T-->T}=\left\{{\mathrm{<!--wovn-src:t-->t}}_1, {\mathrm{<!--wovn-src:t-->t}}_2, ..., {\mathrm{<!--wovn-src:t-->t}}_{\mathrm{<!--wovn-src:m-->m}}\right\}$および、各業務に従事させる社員数$\mathrm{<!--wovn-src:P-->P}=\left\{{\mathrm{<!--wovn-src:p-->p}}_1, {\mathrm{<!--wovn-src:p-->p}}_2, ..., {\mathrm{<!--wovn-src:p-->p}}_{\mathrm{<!--wovn-src:m-->m}}\right\}$、そして各社員の労働可能時間$\mathrm{<!--wovn-src:W-->W}=\left\{{\mathrm{<!--wovn-src:w-->w}}_1, {\mathrm{<!--wovn-src:w-->w}}_2, ..., {\mathrm{<!--wovn-src:w-->w}}_{\mathrm{<!--wovn-src:n-->n}}\right\}$が与えられている状況を作ります。

Prepare Objective Function and Constraints

社員$\mathrm{<!--wovn-src:i-->i}$に業務$\mathrm{<!--wovn-src:j-->j}$を割り当てた際の割り当て$\forall {\mathrm{<!--wovn-src:x-->x}}_{\mathrm{<!--wovn-src:i-->i}\mathrm{<!--wovn-src:j-->j}}\in \{0,1\}$のとき、社員ごとの割り当て業務に必要な時間と労働可能時間の差の絶対値${\mathrm{<!--wovn-src:z-->z}}_{\mathrm{<!--wovn-src:i-->i}}$は

${\mathrm{<!--wovn-src:z-->z}}_{\mathrm{<!--wovn-src:i-->i}}=\left|{\sum }_{\mathrm{<!--wovn-src:j-->j}=1}^{\mathrm{<!--wovn-src:m-->m}} {\mathrm{<!--wovn-src:t-->t}}_{\mathrm{<!--wovn-src:j-->j}} {\mathrm{<!--wovn-src:x-->x}}_{\mathrm{<!--wovn-src:i-->i}\mathrm{<!--wovn-src:j-->j}}-{\mathrm{<!--wovn-src:w-->w}}_{\mathrm{<!--wovn-src:i-->i}}\right|$(1)

becomes.

なお全社員に割り当てられた業務の合計時間と労働可能時間がピッタリ一致するとき、$\sum _{\mathrm{<!--wovn-src:i-->i}=1}^{\mathrm{<!--wovn-src:n-->n}}{\mathrm{<!--wovn-src:z-->z}}_{\mathrm{<!--wovn-src:i-->i}}=0$となります。

However, there was a point to be aware of here.

For example, in the two tables A and B below, the total overtime of the working hours of two people is both two hours.

Table A has an unfair allocation and Table B has a fair allocation.

In this example, as shown in Table B, it cannot be said to be a fair allocation unless work β is handed over to Mr. B to​ ​balance the overtime hours.

Table A. Unfair Allocation (Total Overtime: 2 Hours)

Table B. Fair allocation (total overtime: 2 hours)

Therefore, we set the objective function using the minimax criterion, which minimizes the maximum value.

The minimax criterion allows us to balance (remove the unfairness here) by reducing the maximum difference between workable hours and quotas as small as possible.

By formulating based on the conditions that have come up so far, the assignment of work this time can be expressed by the following formula.

Equation (4) requires that the number of employees required for each task is met, and Equation (5) requires that each employee be assigned one or more tasks.

Convert to a form that can be solved by a solver

Once the formulation is done, the next step is to pass the formula to the solver to solve the formula.

However, in fact, the formulas we have prepared so far are in a format that is easy for humans to understand, but they cannot be solved by the solver program as they are.

Before passing it to the solver, convert the equation expressed in the minimax criterion into a form that can be solved by the solver​.

Since the minimax cannot be expressed as the objective function as it is, the minimax criterion is expressed as follows by combining minimize and inequality.

$$
v​By preparing a new variable, we were able to divide the minimax formula into the objective function for minimization and the constraint formula.

This can be solved by any solver that supports Mixed-Integer Nonlinear Problems (MINLP), but in the next section we linearly​will rewrite the constraints so that they can be expressed .

Convert non-linear formula to linear formula*1

As it stands now, the constraint formula contains an absolute value, so by rewriting the same content with a linear formula, the formula is simple, beautiful, and can be calculated quickly.

Constraint (7) can be expressed as a linear inequality without absolute values by decomposing it into the following constraints (9) and (10).

Now, let's pass the completed objective function and constraint to the solver.

code explanation

今回定式化した最適化問題は、割当結果を保持する$\mathrm{<!--wovn-src:v-->v}$が連続的な値を持ち、割当を意味する${\mathrm{<!--wovn-src:x-->x}}_{\mathrm{<!--wovn-src:i-->i}\mathrm{<!--wovn-src:j-->j}}$が離散的な値を持つため、混合整数線形計画問題（Mixed-Integer Linear Programing ; MILP）と呼ばれます。

Of the solvers that can solve MILP, I used Xpress this time.

If you want to know how to use Xpress in detail, there is little information written in Japanese, so I think you should read the official document, although it is written in English.

Xpress is installed in the environment with the following code.

Specify the Python module to use.

When executed, a file upload button will be displayed on Colab.

shown as a table at the beginning of the article employee_dummy.csv and task_dummy.csv Two CSV files created in the format of upload To do.

uploadedemployee_dummy.csvandtask_dummy.csvboth files inpandas.DataFrameread asPrepare data to be substituted into variables for mathematical optimization.

​Declare variables in mathematical optimization.

The theory part at the top of the article used the sigma symbol to represent summation.

But when implementing numpy of matrix operation Python's for code than loop simple become execution speed be advantageous in terms of must.

in mathematical optimizationObjective function declarationto hold.

in mathematical optimizationDeclaring Constraintsto hold.

So far, we have done the following three things.

• Prepare variables
• Setting the objective function
• Constraint setting

Now we can finally solve thisequation with Solver.

Since the result of optimization is assigned to df_out, thefollowing result is obtained when displayed.

between optimized results and actual workable hours for each employee difference ShowLet's try.

The result was that the difference was within 2 hours​.

Since there was no such thing as an allocation where the difference is completely 0, it is in a state where the difference is optimized to be as close to 0 as possible.

Full code executable on Colab

At the end

So far, I have introduced an example of the mathematical optimization logic that I created to create a work flow that does not cause problems in staffing within the company.

By copying the above source code and preparing a little data, you can try optimizing the allocation of tasks at your fingertips, so please give it a try.

In the sequel article, I plan to introduce the content of this time when prototyping as a web application using Docker and Streamlit, and my experiences when proceeding with in-house DX, so if you are interested, please read that as well. I would be happy to receive it.

Kazuki Igeta

*1 We received useful advice on Twitter that it is possible to formulate within the linear range, so we added a section and changed the surrounding content accordingly. In the non-linear approach before the modification, the above code was executed on Colab and the execution time after reading CSV was 462 msec, while the current linear approach was able to execute in 455 msec. Larger data will likely make a bigger difference.