マンマシンチャートをPythonで解いてみる

よくあるMMチャートの問題を手作業じゃなくて, python で解いてみよう，という試み．

お題『円座状の工程において最小サイクルタイムと作業者への工程割付を述べよ』

• 工程数および各工程に掛かる時間はリストで与えられる.
  
  今回は8工程で，各工程に掛かる時間は，[6, 3, 3, 10, 6, 8, 4, 5].
• 作業者の移動に掛かる時間は隣同士で1, 1つ飛ばしで2, それ以外は3
• 作業者の数も可変.今回は3人．

condition

process_time_lst = [6, 3, 3, 10, 6, 8, 4, 5]
move_cost_lst = [1, 2, 3]
num_of_workers = 3

知りたいのは，『クマ，ウサギ，ブタにどの工程を担当して貰えばよいか』

まず，工程名とその工数を辞書にします．

image

# Input:
[6, 3, 3, 10, 6, 8, 4, 5]
# Output:
{'process0':6, 'process1':3, ... , 'process7':5}

code

def generate_process_lst(process_time_lst):
    lst = ['process'+str(val) for val in range(len(process_time_lst))]
    return lst

process_lst = generate_process_lst(process_time_lst)
process_time_dict = {process:cost for process, cost in zip(process_lst, process_time_lst)}

続いて，計算をしていくための前処理を施していきます．
次工程への移動を意味する move を全工程間に挿入します．

image

# Input
['process0', 'process1', ... , 'process7']
# Output
['process0', 'move', 'process1', 'move', ... , 'move', 'process7']

code

def generate_process_and_move_lst(process_lst):
    len_lst = len(process_lst) - 1
    process_and_move_lst = process_lst.copy()
    for i in range(len_lst):
        process_and_move_lst.insert(len_lst - i, 'move')
    return process_and_move_lst

process_and_move_lst = generate_process_and_move_lst(process_lst)

次に，リストprocess_and_move_lst を切り分ける場所のインデックスリストを作成します．

image

# Input
['process0', 'move', 'process1', 'move', ... , 'move', 'process7']
# Output
[(0, 1, 2), (0, 1, 3), ... , (11, 13, 14), (12, 13, 14)]

code

import itertools

def generate_combi_lst(process_and_move_lst, num_of_workers):
    len_lst = len(process_and_move_lst)
    idx_lst = [x for x in range(len_lst)]
    combi_lst = list(itertools.combinations(idx_lst, num_of_workers))
    return combi_lst

combi_lst = generate_combi_lst(process_and_move_lst, num_of_workers)

切り分けるインデックスリストを使って，各作業者に割り当てる工程リストの組合せを生成します．

image

# Input
['process0', 'move', 'process1', 'move', ... , 'move', 'process7']
[(0, 1, 2), (0, 1, 3), ... , (11, 13, 14), (12, 13, 14)]
# Output(image) ※何してるか分かりにくいので実際の出力リストの一部です．
worker0 : ['move', 'process1', 'move']
worker1 : ['process2', 'move', 'process3', 'move', 'process4', 'move', 'process5', 'move', 'process6', 'move']
worker2 : ['process7', 'move', 'process0']

code

def generate_process_group_lst(process_and_move_lst, combi_lst):
    process_group_lst = []
    for combi in combi_lst:
        if combi[0] != 0:
            tmplst = [process_and_move_lst[0:combi[0]]]
        else:
            tmplst = []
        for idx, val in enumerate(combi):
            start = val
            if idx == len(combi) - 1:
                end = len(process_and_move_lst)
            else:
                end = combi[idx + 1]
            tmplst.append(process_and_move_lst[start:end])
        
        if combi[0] != 0:
            tmplst[-1].append('move')
            tmplst[-1] = tmplst[-1] + tmplst[0]
            tmplst = tmplst[1:]
        process_group_lst.append(tmplst)
    return process_group_lst

process_group_lst = generate_process_group_lst(process_and_move_lst, combi_lst)

各作業者ごとの必要工数を算出していきます．

image

# Input(image) ※何してるか分かりにくいので(略
worker0 : ['move', 'process1', 'move']
worker1 : ['process2', 'move', 'process3', 'move', 'process4', 'move', 'process5', 'move', 'process6', 'move']
worker2 : ['process7', 'move', 'process0']

# Output(image)
[7, 39, 13] # move:1, process1:3, move:1, return_cost:2 → total 7

code

def calc_return_cost(process_set, process_time_dict, move_cost_lst):
    tmplst = [val for val in process_set if val in process_time_dict.keys()]
    if len(tmplst) == 0:
        return_cost = move_cost_lst[0]
    elif len(tmplst) == 1:
        if len(process_set) == 2:
            return_cost = move_cost_lst[0]
        else:
            return_cost = move_cost_lst[1]
    else:
        start_num = int(tmplst[0][-1])
        end_num = int(tmplst[-1][-1])
        if process_set[0] == 'move':
            start_num -= 1
        if process_set[-1] == 'move':
            end_num += 1
        tmp = abs(start_num - end_num)
        distance = min( tmp,  (len(process_time_dict.keys()) - tmp) )
        if distance == 1:
            return_cost = move_cost_lst[0]
        elif distance == 2:
            return_cost = move_cost_lst[1]
        else:
            return_cost = move_cost_lst[2]
    return return_cost

def calc_cycleTime(process_group_lst, process_time_dict, move_cost_lst):
    ct_lst = []
    for process_group in process_group_lst:
        ct_tmp_lst = []
        for process_set in process_group:
            ct = 0
            ct += process_set.count('move') * move_cost_lst[0]
            ct += sum([process_time_dict[val] for val in process_set if val in process_time_dict.keys()])
            ct += calc_return_cost(process_set, process_time_dict, move_cost_lst)
            ct_tmp_lst.append(ct)
        ct_lst.append(ct_tmp_lst)
    return ct_lst

ct_lst = calc_cycleTime(process_group_lst, process_time_dict, move_cost_lst)

各作業者への工程割付組合せごとのサイクルタイムを算出する．

image

# Input
[[8, 2, 47], [8, 5, 44], ... ,[6, 2, 49], [6, 2, 49]]
# Output
[47, 44, ..., 49, 49]

code

max_ct_lst = [max(lst) for lst in ct_lst]

どの組み合わせが最も少ないサイクルタイムかを算出し，
その組み合わせが存在するインデックスを取得．

image

# Input
[47, 44, ..., 49, 49]
# Output
[58, 211]

code

min_ct = min(max_ct_lst)
min_ct_idx_lst = [idx for idx, val in enumerate(max_ct_lst) if val == min_ct]

最後に，最小サイクルタイムの表示と，
それを達成する作業者への工程割付を表示する．

image

# Output
minimumCT:21s
condition:
Worker0:['process0', 'move', 'process1', 'move', 'process2', 'move'], time=18s
Worker1:['process3', 'move', 'process4', 'move'], time=20s
Worker2:['process5', 'move', 'process6', 'move', 'process7'], time=21s
condition:
Worker0:['process1', 'move', 'process2', 'move', 'process3'], time=20s
Worker1:['move', 'process4', 'move', 'process5', 'move'], time=20s
Worker2:['process6', 'move', 'process7', 'move', 'process0', 'move'], time=21s

code

print(f'minimumCT:{min_ct}s')
for idx in min_ct_idx_lst:
    print('condition:')
    for worker, process in enumerate(process_group_lst[idx]):
        print(f'Worker{worker}:{process}, time={ct_lst[idx][worker]}s')

---

全てのコードを繋げると，以下のようになる．

code

import itertools

def generate_process_lst(process_time_lst):
    lst = ['process'+str(val) for val in range(len(process_time_lst))]
    return lst

def generate_process_and_move_lst(process_lst):
    len_lst = len(process_lst) - 1
    process_and_move_lst = process_lst.copy()
    for i in range(len_lst):
        process_and_move_lst.insert(len_lst - i, 'move')
    return process_and_move_lst

def generate_combi_lst(process_and_move_lst, num_of_workers):
    len_lst = len(process_and_move_lst)
    idx_lst = [x for x in range(len_lst)]
    combi_lst = list(itertools.combinations(idx_lst, num_of_workers))
    return combi_lst

def generate_process_group_lst(process_and_move_lst, combi_lst):
    process_group_lst = []
    for combi in combi_lst:
        if combi[0] != 0:
            tmplst = [process_and_move_lst[0:combi[0]]]
        else:
            tmplst = []
        for idx, val in enumerate(combi):
            start = val
            if idx == len(combi) - 1:
                end = len(process_and_move_lst)
            else:
                end = combi[idx + 1]
            tmplst.append(process_and_move_lst[start:end])
        
        if combi[0] != 0:
            tmplst[-1].append('move')
            tmplst[-1] = tmplst[-1] + tmplst[0]
            tmplst = tmplst[1:]
        process_group_lst.append(tmplst)
    return process_group_lst

def calc_return_cost(process_set, process_time_dict, move_cost_lst):
    tmplst = [val for val in process_set if val in process_time_dict.keys()]
    if len(tmplst) == 0:
        return_cost = move_cost_lst[0]
    elif len(tmplst) == 1:
        if len(process_set) == 2:
            return_cost = move_cost_lst[0]
        else:
            return_cost = move_cost_lst[1]
    else:
        start_num = int(tmplst[0][-1])
        end_num = int(tmplst[-1][-1])
        if process_set[0] == 'move':
            start_num -= 1
        if process_set[-1] == 'move':
            end_num += 1
        tmp = abs(start_num - end_num)
        distance = min( tmp,  (len(process_time_dict.keys()) - tmp) )
        if distance == 1:
            return_cost = move_cost_lst[0]
        elif distance == 2:
            return_cost = move_cost_lst[1]
        else:
            return_cost = move_cost_lst[2]
    return return_cost

def calc_cycleTime(process_group_lst, process_time_dict, move_cost_lst):
    ct_lst = []
    for process_group in process_group_lst:
        ct_tmp_lst = []
        for process_set in process_group:
            ct = 0
            ct += process_set.count('move') * move_cost_lst[0]
            ct += sum([process_time_dict[val] for val in process_set if val in process_time_dict.keys()])
            ct += calc_return_cost(process_set, process_time_dict, move_cost_lst)
            ct_tmp_lst.append(ct)
        ct_lst.append(ct_tmp_lst)
    return ct_lst

process_time_lst = [6, 3, 3, 10, 6, 8, 4, 5]
move_cost_lst = [1, 2, 3]
num_of_workers = 3

process_lst = generate_process_lst(process_time_lst)
process_time_dict = {process:cost for process, cost in zip(process_lst, process_time_lst)}
process_and_move_lst = generate_process_and_move_lst(process_lst)
combi_lst = generate_combi_lst(process_and_move_lst, num_of_workers)
process_group_lst = generate_process_group_lst(process_and_move_lst, combi_lst)
ct_lst = calc_cycleTime(process_group_lst, process_time_dict, move_cost_lst)
max_ct_lst = [max(lst) for lst in ct_lst]
min_ct = min(max_ct_lst)
min_ct_idx_lst = [idx for idx, val in enumerate(max_ct_lst) if val == min_ct]

print(f'minimumCT:{min_ct}s')
for idx in min_ct_idx_lst:
    print('condition:')
    for worker, process in enumerate(process_group_lst[idx]):
        print(f'Worker{worker}:{process}, time={ct_lst[idx][worker]}s')

以上，マンマシンチャートをpythonを使って解いてみた，でした．