[GO] Johnson method (python)

Johnson method

A method of finding a schedule that optimizes the work period when each product is completed through two processes. スクリーンショット 2020-10-04 19-50-56.png

In the example of the image above, find the optimum order for boiling the noodles. Reference

Try to write

test.py



# -*- coding: utf-8 -*-
#Johnson method

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] #Add the very first pre-process and finish
            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("Time required: " + str(sum_time))
        
#"https://studying.jp/shindanshi/past-exam/exam20unei.html 18th question"
johnsonMethod([[5,5],[6,4],[4,3],[2,8],[5,7]])

Recommended Posts

Johnson method (python)
[Python] Semi-Lagrange method
Kernel Method with Python
Python installation method Windows
Simplex method (simplex method) in Python
Python
[Python] Calculation method with numpy
Implement method chain in Python
Python Design Pattern --Template method
Try implementing extension method in python
Implemented label propagation method in Python
Simulate Monte Carlo method in Python
Hash method (open address method) in Python
[python] -1 meaning of numpy's reshape method
Manim's method 7
Let's build a belief propagation method (Python)
Manim's method 2
Python basics ⑤
python + lottery 6
Manim's method 18
Python Summary
Built-in python
Python comprehension
Python technique
Studying python
Python 2.7 Countdown
Python memorandum
Manim's method 17
Python FlowFishMaster
Python service
python tips
Method to build Python environment in Xcode 6
[Introduction to Udemy Python3 + Application] 25. Dictionary-type method
Manim's method 5
python function ①
Python basics
ufo-> python (3)
[Introduction to Udemy Python3 + Application] 13. Character method
Python + Selenium Frequently used operation method summary
Manim's method 3
Python comprehension
Manim's method 15
[Python] [scikit-learn] k-nearest neighbor method introductory memo
install python
Python Singleton
Manim's method 11
python memo
Automatic update method with python Pyinstaller exe
Python Jinja2
atCoder 173 Python
[Python] function
Python installation
Electron Microscopy Simulation in Python: Multislice Method (1)
Manim's method 16
python tips
Manim's method 20
Binary method
Installing Python 3.4.3.
Try python
Python memo
Python algorithm