Python＋Pulpで作業工程表を自動作成する

作業工程表とは

(▼ChatGPT生成、一部編集▼)

「作業工程表」とは、一連の作業や工程を順序立てて記載した表のことで、製品の生産やサービス提供において非常に重要な役割を担っています。例えば、自動車の製造工程では、フレーム組み立てやエンジン取り付けなどの作業が順序立てて記載された作業工程表が作成されます。

この作業工程表には、どの作業いつを割り当てていくのか、どの作業をどの機械で行うかなどの細かいスケジューリングの問題が潜んでいます。この問題を「ジョブショップスケジューリング問題」と呼びます。いわゆるガントチャートです。

ジョブショップスケジューリング問題

(▼ChatGPT生成、一部編集▼)

ジョブショップスケジューリング問題とは、複数のジョブ（作業やタスク）を複数の機械に割り当てる問題を扱うための数理モデルです。この問題は、多くの産業分野で生じるスケジューリング問題の中でも、特に複雑な問題の一つとされています。

ジョブショップスケジューリングでは、各ジョブに必要な加工時間や機械に対する制約条件などを考慮しながら、ジョブが完了するまでの最適なスケジュールを導き出すことが目的となります。このような問題を解決することで、生産ラインの生産性や利益を最大化することが可能となります。

調理工程表ので作成

シンプルな条件で定式化します。
すべての作業を可能な限り最短時間で完了させたい。（メイクスパンの最小化）
作業は作業者の誰が行ってもいい。
作業に納期は存在しない
特定の作業はそれに対応する特定の作業が終わった後でなければ取り掛かることはできない。
今回の例では冷却作業_0を行うためにはそれより先に誰かが焼き作業_0を完了させておかなければならない。

定式化

集合

$N:n個のタスク集合$
$M:m人の従業員集合$

変数

$x_{ijk}:作業員_kがタスク_iをタスク_jより先に実施するなら1、そうでないなら0をとるバイナリ変数$
$y_{ik}:作業員_kがタスク_iを実施するなら1、そうでないなら0をとるバイナリ変数$
$z_{i}:タスクiが完了する時間を表す非負変数$

定数

$time_i:タスク_iにかかる作業時間$
$fintime:すべてのタスクが完了する時間$
$M:十分に大きな値(9999など)$

制約条件の定式化

すべてのタスクは必ず実行される

$\sum_{k}^{m} y_{ik} = 1 \qquad(\forall i\in N)$

作業員_kがタスク_i,タスク_jをともに実行するとき必ずどちらかのタスクを先に行う

$2(x_{ijk}+x_{jik})+1 \geq y_{ik} + y_{jk} \qquad(\forall i,j\in N :i\neq j)$
$2(x_{ijk}+x_{jik}) \leq y_{ik} + y_{jk} \qquad\qquad(\forall i,j\in N :i\neq j)$
$x_{ijk}+x_{jik}=0 \qquad\qquad\qquad\qquad(\forall i,j\in N :i=j)$

タスク_jの完了時間は先行するタスク_iがすべてが完了した後に実施される

$\sum_{i}^{n}(time_i *x_{ijk})+time_j \leq z_j \qquad(\forall k\in M,\forall j\in N)$

タスク_jの開始時間は先行するタスク_iの完了時間より後に実施される

$z_i \leq z_j - time_j + M(1-x_{ijk})\qquad(\forall i,j\in N)$

タスク_iの完了後にしか行えないタスク_jとの関係

$z_i \leq z_j - time_j$

タスク_iとすべてのタスクが完了する時間との関係式

$z_i \leq fintime \qquad(i\in N)$

目的関数

$fintimeを最小化する$

python+pulpでモデリング

pulpをインストール

#pipでインストール
pip install pulp
pip install ortoolpy

インポート

from pulp import LpProblem , LpMinimize , LpVariable, lpSum , LpStatus , PULP_CBC_CMD 
from ortoolpy import addvar #LpVariableだけでも可能だけど変数をさっと追加したいときはaddvarが便利
from datetime import datetime, timedelta
import plotly.express as px
import pandas as pd

タスクデータの作成

#各タスクの作業時間
time = {
    "Bake":58,
    "Cut":21,
    "Cooling":34,
    }

#各タスク,従業員の数
n_bake = 2
n_cut = 5
n_Cooling = n_bake
n_worker = 3

#タスク,従業員リストの作成
task_Bake = [f'Bake_{i}' for i in range(n_bake)]
task_Cut = [f'Cut_{i}' for i in range(n_cut)] 
task_Cooling = [f'Cooling_{i}' for i in range(n_Cooling)]
workers = [f'Worker_{i}' for i in range(n_worker)] 

#タスクリスト
task = task_Bake + task_Cut + task_Cooling

#作業とその作業時間
task_time = {t:time[t.split("_")[0]] for t in task}

変数の作成

#モデルインスタンスの作成
model = LpProblem("jobshop",sense=LpMinimize)

#変数の設定
#作業員wにおいて作業iが作業jより先行するか否か
x = LpVariable.dicts("x",[(i,j,k) for i in task for j in task for k in workers], cat="Binary" )
#作業員wにおいて作業iが実施されるか否か
y = LpVariable.dicts("y",[(i,k) for i in task for k in workers], cat="Binary" )
#作業iの完了時間
z = LpVariable.dicts("z",[(i) for i in task],cat="Continuous", lowBound=0)
#すべてのタスクが完了する時間
fintime = addvar()
M = 9999

制約条件の作成

#必ず作業が誰かに割り当てられる
for i in task:
  model += lpSum(y[i,k]  for k in workers) == 1

#作業iが作業jに先行するとき1、そうでないとき0
for k in workers:
  for i in task:
    for j in task:
      if i != j:
        #ijの両方のJobを行う時のみ先行関係が発生する
        #どちらかのJobが先行するとき、もう片方のJobは必ず後行するためijの関係が分かればjiの関係もわかる
        #作業i,jともに後先の関係が無ければ作業員wは作業i,jを両方とも担当していない#
        model += 2*(x[i,j,k] + x[j,i,k])+1 >= y[i,k] + y[j,k]
        model += 2*(x[i,j,k] + x[j,i,k])   <= y[i,k] + y[j,k]
      elif i == j:
        model += x[i,j,k] == 0 #同一のJobに先行の関係はない

#作業jが完了する時間z[i]
for j in task:
  for k in workers:
    model += lpSum(task_time[i] * x[i,j,k] for i in task) + task_time[j] <= z[j]

#仕事iと仕事jの終了時間の関係式
for k in workers:
  for i in task:
    for j in task:
      if i != j:
        model += z[i] <= z[j] - task_time[j] + M * (1-x[i,j,k])

#冷却作業は対応する焼き作業より必ず後に行う
for i, j in zip(task_Bake, task_Cooling):
  model += z[i] <= z[j] - task_time[j] 

#z[i]の最大を最小化
for i in task:
  model += z[i] <= fintime 

#目的関数
model.objective = fintime

求解

#求解
#Jobの数や作業員の数によって計算に時間がかかる
pulpCBC_setting = PULP_CBC_CMD(msg=1, threads=4, timeLimit=6000)
status = model.solve(pulpCBC_setting)

解の確認

出力結果（誰がどの作業を行うか）

#確認
print(LpStatus[status]) #Optimalなら最適解が得られている >> Optimal
print(model.objective.value()) #目的関数の結果を確認　>>100.0


#結果の確認
df = pd.DataFrame(index= workers,columns=task)
for k in workers:
  for j in task:
    if y[j,k].value() == 1:
      df.loc[k,j] ="○"
    else:
      df.loc[k,j] = "-"
display(df)

index	Bake_0	Bake_1	Cut_0	Cut_1	Cut_2	Cut_3	Cut_4	Cooling_0	Cooling_1
Worker_0	○	-	○	-	○	-	-	-	-
Worker_1	-	-	-	○	-	○	○	○	-
Worker_2	-	○	-	-	-	-	-	-	○

スケジュールの可視化

def add_minutes_to_datetime( minute_to_add):
    # 指定された日時をdatetimeオブジェクトに変換
    dt = datetime(2023, 1, 1, 10, 00)
    # 指定された分数を加算
    later = dt + timedelta(minutes=minute_to_add)
    # 結果を返す
    return later

#各作業者の作業一覧とその作業完了時間
result = {"作業者":[],"作業":[],"作業開始時間":[],"作業完了時間":[]}
for k in workers:
  for i in task:
    if(y[i,k].value()==1):
      result["作業者"].append(k)
      result["作業"].append(i)
      result["作業開始時間"].append(z[i].value() - task_time[i])
      result["作業完了時間"].append(z[i].value())

#データフレームの作成
data = []
for i in range(len(result["作業"])):
  data.append(dict(
      Worker     = result["作業者"][i], 
      Start      = add_minutes_to_datetime(result["作業開始時間"][i]), 
      Finish     = add_minutes_to_datetime(result["作業完了時間"][i]), 
      Task       = result["作業"][i])
  )
df = pd.DataFrame(data)

#ガントチャートの描画
fig = px.timeline(df, x_start="Start", x_end="Finish", y="Worker", color="Task")
fig.update_yaxes(autorange="reversed")
fig.show()

最適なスケジュールが出力されました。
今回の業務量を3人で行うと12時にはみんなでそろってお昼ご飯を食べられそうです。
BakeタスクとCoolingタスクの順序関係の制約も守られています。

課題

(▼ChatGPT出力、一部編集▼)
ジョブショップスケジューリング問題を線形計画問題として定式化しPythonを用いて解を求めることができましたが、タスクの量が少し増えただけで計算時間が膨大になってしまうという課題があります。（タスクや作業者の数を増やすと永遠に計算しだす。。。）そのため、より大規模な問題に対応するためには、メタヒューリスティック解法を模索する必要があります。

例えば、SA法（Simulated Annealing）は、大規模な問題に対しても高い探索性能を発揮することが知られています。SA法は、現在の解を少しずつ変化させながら最適解を探索する手法であり、非常に効率的なアルゴリズムです。次回はこのようなメタヒューリスティック解法にて同じ問題を解いてみたいと思います。