ジョンソン法(python)

##ジョンソン法
各製品がそれぞれ2つの工程を経て完成されるときに、作業期間が最適になるスケジュールを求める手法のこと。

上の画像の例であれば、麺を茹でる順をどのようにすれば最適かを求める。
参考

##かいてみる

test.py

# -*- coding: utf-8 -*-
#ジョンソン法

def johnsonMethod(job_pair):
    
    front = []
    back = []
    process_1 = []
    process_2 = []
    sum_time = 0
    
    while True:
        
        min_jobs = [min(jobs) for jobs in job_pair]
        min_job = min(min_jobs)
    
        if min_job == 9999:
            sum_time += process_1[0] #一番最初の前工程を足して終了
            break
    
        job_pair_index = min_jobs.index(min_job)
        job_index = job_pair[job_pair_index].index(min_job)
        
        if job_index == 0:
            front.append(job_pair_index)
        else:
            back.append(job_pair_index)
            
        process_1.append(job_pair[job_pair_index][0])
        process_2.append(job_pair[job_pair_index][1])
        
        if sum(process_1) > sum(process_2):
            sum_time += job_pair[job_pair_index][0]
        else:
            sum_time += job_pair[job_pair_index][1]
            
        job_pair[job_pair_index] = [9999, 9999]
    
    front.extend(list(reversed(back)))
    order = ["J" + str(x + 1) for x in front]
    print(order)
    print("所要時間 : " + str(sum_time))
        
#"https://studying.jp/shindanshi/past-exam/exam20unei.html 第18問"
johnsonMethod([[5,5],[6,4],[4,3],[2,8],[5,7]])