上記urlからの写経です。
ジョンソン法は、特に「2工程(=taskが2コ)」にしか適用できないようですので、 利用シーンは少ないはずです。
# -*- coding: utf-8 -*- is_complete = 9999 def main(): jobs = [ [5,5],[6,4],[4,3],[2,8],[5,7] ] johnson_scheduling( jobs ) # ジョンソン法とは、 # 2工程(=taskが2コ)のフローショップ (≠ジョブショップ)において # 最も時間の短い作業(task)を探し、それが # 前工程のものであれば、そのジョブを前から割り付け # 後工程のものであれば、そのジョブを後から割り付ける # スケジューリング def johnson_scheduling( jobs ): front = [] back = [] process_1 = [] process_2 = [] sum_time = 0 while True: # 各ジョブの組から、小時間のタスクを列挙 min_tasks = [] for tasks in jobs: min_tasks.append( min(tasks) ) # 上記の中から最小タスクを算出 min_task = min( min_tasks ) if min_task == is_complete: sum_time += process_1[0] #一番最初の前工程を足して終了 break # 最小タスクのあるジョブ job_no = min_tasks.index( min_task ) task_no = jobs[job_no].index( min_task ) # 前工程 → ジョブを前から割り付け if task_no == 0: front.append(job_no) # 後工程 → そのジョブを後から割り付け else: back.append(job_no) process_1.append( jobs[job_no][0] ) process_2.append( jobs[job_no][1] ) if sum(process_1) > sum(process_2): sum_time += jobs[job_no][0] else: sum_time += jobs[job_no][1] jobs[job_no] = [is_complete, is_complete] front.extend( list(reversed(back)) ) order = ["Job No" + str(x + 1) for x in front] print(order) print("所要時間 : " + str(sum_time)) if __name__ == '__main__': main()
