Try to solve the man-machine chart with Python
An attempt to solve a common MM chart problem with python instead of manually.
Theme "State the minimum cycle time and process allocation to workers in the circular process"
--The number of processes and the time required for each process are given in a list.
This time, there are 8 processes, and the time required for each process is [6, 3, 3, 10, 6, 8, 4, 5].
――The time it takes to move a worker is 1, skip one next to each other 2, 2, otherwise 3
--The number of workers is also variable. This time, there are three.
condition
process_time_lst = [6, 3, 3, 10, 6, 8, 4, 5]
move_cost_lst = [1, 2, 3]
num_of_workers = 3
What I want to know is, "Which process should bears, rabbits, and pigs take charge of?"
First, make a dictionary of process names and their man-hours.
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)}
Next, we will perform preprocessing for calculation.
Insert move, which means move to the next process, between all processes.
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)
Next, create an index list where the list process_and_move_lst is separated.
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)
Using the index list to be carved, a combination of process lists to be assigned to each worker is generated.
image
# Input
['process0', 'move', 'process1', 'move', ... , 'move', 'process7']
[(0, 1, 2), (0, 1, 3), ... , (11, 13, 14), (12, 13, 14)]
# Output(image)* It is a part of the actual output list because it is difficult to understand what you are doing.
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)
We will calculate the required man-hours for each worker.
image
# Input(image)* It's hard to understand what you're doing(Abbreviation
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)
Calculate the cycle time for each process allocation combination for each worker.
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]
Calculate which combination has the shortest cycle time and Get the index where the combination exists.
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]
Finally, the display of the minimum cycle time and The process allocation to the workers who achieve it is displayed.
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')
When all the codes are connected, it becomes as follows.
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')
So far, I tried to solve the man-machine chart using python.
Recommended Posts