プリント回路基盤の生産スケジューリング¶
イントロダクション¶
「マシニングセンタにおける生産計画」に続き、今回はプリント回路基盤（Printed Circuit Board, PCB）の生産スケジュール問題を取り扱います。
PCB の製造には 3 つのジョブが含まれており、それらを順番に行う必要があります。また、いくつかのジョブには複数の手順が含まれ、これらは中断なしに連続して行われる必要があります。このような制約条件をもつ設定のもとでスケジューリング問題を解いてみましょう。
以下で用いられている用語や Fixstars Amplify Scheduling Engine (Amplify SE) については、『Amplify SE とは』をご覧ください。
問題設定¶
PCB の製造には、1. 表面実装、2. 挿入実装、3. 検査という 3 つのジョブが含まれます。
以下、各ジョブについて説明します。
表面実装¶
表面実装では マウンタ によるはんだ付け行われます。マウンタは複数台あり、それぞれのマウンタは PCB を一つずつ実装することができます。今回、マウンタの数は 3 台（マウンタ A, マウンタ B, マウンタ C）とします。
挿入実装¶
挿入実装は 卓上型はんだ付けロボット（卓ロボ） によって行われます。
挿入実装は、複数の卓ロボを決められた順番で使って行われます。また、挿入実装は一度開始したら中断することができず、最後の卓ロボによる作業まで連続して実装する必要があります。
今回、卓上型はんだ付けロボットの数は 6 台(卓ロボ A, 卓ロボ B, 卓ロボ C, 卓ロボ D, 卓ロボ E, 卓ロボ F)とし、各 PCB はこの順番で挿入実装されるとします（使わない卓ロボがあってもよいとします）。
検査¶
検査では、作業員が PCB ごとに決められた 検査手順 を行います。検査は一度開始したら中断することができず、最後の手順まで終える必要があります。
検査には作業員 1 人と、PCB と手順ごとに決められた 検査治具 が必要です。検査治具の数には限りがあります。また、同じ作業員が一貫して検査を行うほうが効率がよく、作業員の入れ替えには時間コストがかかるとします（この入れ替え時間の間だけ、検査を中断してもよいことにします）。
今回、各 PCB に対して検査手順は 4 つ（手順 1、手順 2、手順 3、手順 4）とし、検査治具の数は各 3 個、作業員の入れ替えにかかる時間は 100 分とします。
問題設定のまとめ¶
上記をまとめると、以下の表のようになります。
| ジョブ | 内容 | 作業する機械・人 |
|---|---|---|
| 1. 表面実装 | 表面実装のはんだ付け | マウンタ |
| 2. 挿入実装 | 挿入実装のはんだ付け | 卓上型はんだ付けロボット |
| 3. 検査 | 部品の検査 | 作業員 |
実装¶
それでは、Amplify SE を用いた実装に移ります。
まず、今回使うライブラリをインポートします。
# ! pip install amplify_sched # Google Colab 場合、こちらのコメントアウトを外し、amplify_sched をインストールしてください。
from amplify_sched import *
import itertools
import pandas as pd
import numpy.random as rand
問題作成¶
まず、今回の問題設定に登場する要素（PCB、マウンタ、卓上ロボット、検査手順、作業員、治具）の情報をリストや数値として用意します。
# PCB
num_pcb = 15
pcb_list = pd.Index([f"PCB {i+1:0=2}" for i in range(num_pcb)], name="PCB")
# マウンタ
mounter_list = ["マウンタA", "マウンタB", "マウンタC"]
# 卓上ロボット
robot_list = ["卓ロボA", "卓ロボB", "卓ロボC", "卓ロボD", "卓ロボE", "卓ロボF"]
# 作業員
operator_list = ["作業員A", "作業員B", "作業員C"]
operator_exchange_time = 100 # 交代に掛かる時間（分）
# 検査手順
check_list = ["検査手順1", "検査手順2", "検査手順3", "検査手順4"]
# 治具
jig_list = [
[f"治具{i}" for i in range(1, 4)],
[f"治具{i}" for i in range(4, 7)],
[f"治具{i}" for i in range(7, 10)],
[f"治具{i}" for i in range(10, 15)],
] # 検査手順1, 2, 3, 4に必要な治具のリスト
jig_stock = 3 # 治具の在庫
次に、各ジョブに必要な時間を pandas.Dataframe として設定します。
今回、各ジョブの時間と検査手順に必要な治具は乱数で与えることにします。
まず、「1. 表面実装」に必要な時間を 10 分から 30 分の間の乱数で設定します （以下、各処理時間の単位は全て分とします）。
# 乱数のシードを固定(optional)
rand.seed(100)
# 表面実装（プロセス1）
df_job1 = pd.DataFrame(index=pcb_list, columns=mounter_list)
for mounter in mounter_list:
for pcb in pcb_list:
df_job1[mounter][pcb] = rand.randint(low=10, high=30) # 10から30の間の乱数
df_job1
次に、「2. 挿入実装工程」に必要な時間を設定します。
特定の卓ロボを使わない、という状況を想定するため、乱数の下限は 0 とします。
# 挿入実装（プロセス2）
df_job2 = pd.DataFrame(index=pcb_list, columns=robot_list)
for robot in robot_list:
for pcb in pcb_list:
df_job2[robot][pcb] = rand.randint(
low=0, high=30
) # 0から30の間の乱数（0はその卓ロボを使わないことを意味する）
df_job2
最後に、「3. 検査」に必要な時間（作業員ごと）と使用治具を設定します。
# 検査（プロセス3）
df_job3 = pd.DataFrame(
index=pcb_list,
columns=pd.MultiIndex.from_product([check_list, operator_list + ["治具"]]),
)
for i, check in enumerate(check_list):
for operator in operator_list:
for pcb in pcb_list:
df_job3[check, operator][pcb] = rand.randint(low=10, high=30) # 10から30の間の乱数
jigs = jig_list[i]
for pcb in pcb_list:
df_job3[check, "治具"][pcb] = rand.choice(jigs, len(jigs) // 2 + 1, replace=False)
df_job3
Amplify SE を用いた定式化¶
以上で用意したデータを使って、Amplify SE を使ったスケジューリングを行いましょう。
今回の問題における各要素と Amplify SE の用語は、それぞれ以下のように対応しています。
| 要素 | サブ要素 | 対応 |
|---|---|---|
| 表面実装 | ジョブ | |
| 挿入実装 | ジョブ | |
| 卓ロボ A を使う工程 | 工程 | |
| 卓ロボ B を使う工程 | 工程 | |
| $ \vdots $ | ||
| 検査 | ジョブ | |
| 手順 1 | 工程 | |
| 手順 2 | 工程 | |
| $ \vdots $ | ||
| マウンタ | マシン | |
| 卓上ロボット | マシン | |
| 作業員 | マシン | |
| 治具 | リソース |
まず、モデルを用意してマシン、リソース、ジョブを設定しましょう。
ジョブの検査においては、
- 各手順に必要な治具の設定（
add_required_resource） - 作業員の交代にかかる時間の設定（
add_transportation_time）
が必要です。
治具は required_resource、作業員の交代時間は transportation_time として表現します
（transportation_timeを直訳すると「輸送時間」ですが、これはジョブの対象をあるマシンから別のマシンに動かすことを想定した名前になっています。
これらの用語に関する詳細な説明は『Amplify SE
とは』をご参照ください）。
# モデルの宣言
model = Model()
# マシンの設定
for machine in mounter_list + robot_list + operator_list:
model.machines.add(machine)
# リソースの設定
for jig in itertools.chain.from_iterable(jig_list):
model.resources.add(jig)
# ジョブの設定
for pcb in pcb_list:
label_job1 = f"1. 表面実装（{pcb}）"
label_job2 = f"2. 挿入実装（{pcb}）"
label_job3 = f"3. 検査（{pcb}）"
model.jobs.add(label_job1)
model.jobs.add(label_job2)
model.jobs.add(label_job3)
# 表面実装
model.jobs[label_job1].append(Task()) # ジョブ1に表面実装タスクを追加
for mounter in mounter_list:
model.jobs[label_job1][0].processing_times[mounter] = int(
df_job1[mounter][pcb]
) # 表面実装タスクに対しそれぞれのマウンターを使う場合の処理時間を設定
# 挿入実装
for i, robot in enumerate(robot_list):
model.jobs[label_job2].append(Task()) # 各卓上ロボットによる挿入実装タスクを追加
model.jobs[label_job2][i].processing_times[robot] = int(
df_job2[robot][pcb]
) # 卓ロボ robot が実施するタスクにかかる処理時間を設定
# 検査
for i, check in enumerate(check_list):
model.jobs[label_job3].append(Task()) # ジョブ3における検査工程タスクを追加
# 検査にかかる時間を作業員ごとに設定
for operator in operator_list:
model.jobs[label_job3][i].processing_times[operator] = int(
df_job3[check, operator][pcb]
)
# 必要な治具の設定
for jig in jig_list[i]:
model.jobs[label_job3][i].add_required_resource(jig)
# 作業員の交代に掛かる時間コスト
for operator1, operator2 in itertools.combinations(operator_list, 2):
model.jobs[label_job3][i].add_transportation_time(
operator_exchange_time, operator1, operator2
)
model.jobs[label_job3][i].add_transportation_time(
operator_exchange_time, operator2, operator1
)
表面実装、挿入実装、検査はこの順番に行われる必要があります。
このようなジョブ間の依存関係は add_dependent_jobs によって表現することができます。
for pcb in pcb_list:
# 表面実装 -> 挿入実装の順番
model.jobs[f"2. 挿入実装（{pcb}）"].add_dependent_jobs(model.jobs[f"1. 表面実装（{pcb}）"])
# 挿入実装 -> 検査の順番
model.jobs[f"3. 検査（{pcb}）"].add_dependent_jobs(model.jobs[f"2. 挿入実装（{pcb}）"])
また、「挿入実装と検査は、それぞれのジョブを開始したら中断することができない」という制約があります。これは、Amplify SE における no wait 制約
を用いることで表現できます（no_wait に関する詳細はこちらをご参照ください）。
# no wait制約
for pcb in pcb_list:
model.jobs[f"2. 挿入実装（{pcb}）"].no_wait = True
model.jobs[f"3. 検査（{pcb}）"].no_wait = True
制約条件どうしの整合性について¶
勘のいい方は、「作業員の入れ替えがある場合、入れ替え時間（transportation_time）によって検査が中断するが、これはno_wait条件に反するのだろうか？」という点が気になったかもしれません。
Amplify SE では、今回のように transportation_time と no_wait
が両方存在する場合、transportation_time は待ち時間に含まれない、つまり transportation_time
の分だけタスク間の時間間隔が空いていても no_wait は満たされていると見なします。
詳細な説明や、他の制約条件間の関係性が気になった方はドキュメントの複数の制約がある場合を読んでください。
Amplify SE の実行¶
これで全ての準備が整いました。 トークンを設定し、スケジューリング問題を解いてみましょう。
token = "" # ローカル環境等で使用する場合は、Amplify SE のアクセストークンを入力してください。
result = model.solve(token=token, timeout=10) # ご自身のトークンを入力してください
print(result.status)
fig = result.timeline(width=1000, height=1000)
fig.show()
以下の制約が満たされているか確認してみましょう。
- 各 PCB について、表面実装 → 挿入実装 → 検査の順に処理されている
- 挿入実装および検査が中断されずに行われている（ただし作業員の入れ替えにかかる時間（100 分）は許容される）
また、machine_view=Trueとすることで、各マシンおよび作業員ごとのガントチャートを見てみましょう。
fig = result.timeline(width=1000, height=1000, machine_view=True)
fig.show()
まとめ¶
今回は、プリント回路基板の実装と検査を題材にして、
- 異なるジョブの間に順序関係がある
- ジョブの中の複数タスクを連続して行う必要がある
という制約がある場合のスケジューリング問題を取り扱いました。
今回説明したコードを 1 つにまとめると、以下のようになります。
from amplify_sched import *
import itertools
import pandas as pd
import numpy.random as rand
def schedule_print_circuit_board():
#
# 問題に現れる要素
#
# PCB
num_pcb = 15
pcb_list = pd.Index([f"PCB {i+1:0=2}" for i in range(num_pcb)], name="PCB")
# マウンタ
mounter_list = ["マウンタA", "マウンタB", "マウンタC"]
# 卓上ロボット
robot_list = ["卓ロボA", "卓ロボB", "卓ロボC", "卓ロボD", "卓ロボE", "卓ロボF"]
# 作業員
operator_list = ["作業員A", "作業員B", "作業員C"]
operator_exchange_time = 100 # 交代に掛かる時間（分）
# 検査手順
check_list = ["検査手順1", "検査手順2", "検査手順3", "検査手順4"]
# 治具
jig_list = [
[f"治具{i}" for i in range(1, 4)],
[f"治具{i}" for i in range(4, 7)],
[f"治具{i}" for i in range(7, 10)],
[f"治具{i}" for i in range(10, 15)],
] # 検査手順1, 2, 3, 4に必要な治具のリスト
jig_stock = 3 # 治具の在庫
#
# ジョブにかかる時間の設定
#
# 乱数のシードを固定(optional)
rand.seed(100)
# 表面実装（プロセス1）
df_job1 = pd.DataFrame(index=pcb_list, columns=mounter_list)
for mounter in mounter_list:
for pcb in pcb_list:
df_job1[mounter][pcb] = rand.randint(low=10, high=30) # 10から30の間の乱数
# 挿入実装（プロセス2）
df_job2 = pd.DataFrame(index=pcb_list, columns=robot_list)
for robot in robot_list:
for pcb in pcb_list:
df_job2[robot][pcb] = rand.randint(
low=0, high=30
) # 0から30の間の乱数（0はその卓ロボを使わないことを意味する）
# 検査（プロセス3）
df_job3 = pd.DataFrame(
index=pcb_list,
columns=pd.MultiIndex.from_product([check_list, operator_list + ["治具"]]),
)
for i, check in enumerate(check_list):
for operator in operator_list:
for pcb in pcb_list:
df_job3[check, operator][pcb] = rand.randint(
low=10, high=30
) # 10から30の間の乱数
jigs = jig_list[i]
for pcb in pcb_list:
df_job3[check, "治具"][pcb] = rand.choice(
jigs, len(jigs) // 2 + 1, replace=False
)
#
# Amplify SEによる定式化
#
# モデルの宣言
model = Model()
# マシンの設定
for machine in mounter_list + robot_list + operator_list:
model.machines.add(machine)
# リソースの設定
for jig in itertools.chain.from_iterable(jig_list):
model.resources.add(jig)
# ジョブの設定
for pcb in pcb_list:
label_job1 = f"1. 表面実装（{pcb}）"
label_job2 = f"2. 挿入実装（{pcb}）"
label_job3 = f"3. 検査（{pcb}）"
model.jobs.add(label_job1)
model.jobs.add(label_job2)
model.jobs.add(label_job3)
# 表面実装
model.jobs[label_job1].append(Task())
for mounter in mounter_list:
model.jobs[label_job1][0].processing_times[mounter] = int(
df_job1[mounter][pcb]
)
# 挿入実装
for i, robot in enumerate(robot_list):
model.jobs[label_job2].append(Task())
model.jobs[label_job2][i].processing_times[robot] = int(df_job2[robot][pcb])
# 検査
for i, check in enumerate(check_list):
model.jobs[label_job3].append(Task())
# 検査にかかる時間を作業員ごとに設定
for operator in operator_list:
model.jobs[label_job3][i].processing_times[operator] = int(
df_job3[check, operator][pcb]
)
# 必要な治具の設定
for jig in jig_list[i]:
model.jobs[label_job3][i].add_required_resource(jig)
# 作業員の交代に掛かる時間コスト
for operator1, operator2 in itertools.combinations(operator_list, 2):
model.jobs[label_job3][i].add_transportation_time(
operator_exchange_time, operator1, operator2
)
model.jobs[label_job3][i].add_transportation_time(
operator_exchange_time, operator2, operator1
)
for pcb in pcb_list:
# 表面実装 -> 挿入実装の順番
model.jobs[f"2. 挿入実装（{pcb}）"].add_dependent_jobs(model.jobs[f"1. 表面実装（{pcb}）"])
# 挿入実装 -> 検査の順番
model.jobs[f"3. 検査（{pcb}）"].add_dependent_jobs(model.jobs[f"2. 挿入実装（{pcb}）"])
# no wait制約
for pcb in pcb_list:
model.jobs[f"2. 挿入実装（{pcb}）"].no_wait = True
model.jobs[f"3. 検査（{pcb}）"].no_wait = True
#
# 求解
#
token = "" # ローカル環境等で使用する場合は、Amplify SE のアクセストークンを入力してください。
result = model.solve(token=token, timeout=10)
print(result.status)
fig = result.timeline(width=1000, height=1000)
fig.show()
