安裝Google ORTools

#!python -m pip install --upgrade --user ortools

範例程式碼

import collections
from ortools.sat.python import cp_model
# sat是專門用來解條件優化的解
# Create the model.
model = cp_model.CpModel()

my_job_list = [  # task = (machine_id, processing_time). 0車床A 1車床B 2銑床C 3銑床D 4磨床E 5CMM
    [(0,1,0),(1,2,0),(4,4,0),(5,4,0)],    #wo#0
    [(0,1,1),(1,2,1),(4,4,1),(5,4,1)],    #wo#1
    [(0,1,2),(2,4,2),(4,6,2),(5,2,2)],    #wo#2
    [(2,1,3),(3,3,3),(5,1,3)],            #wo#3
    [(1,1,4),(3,7,4),(5,3,4)],            #wo#4
    [(1,1,5),(3,7,5),(5,3,5)]             #wo#5
]
jobs_count = 6
all_jobs = [0,1,2,3,4,5]

all_machines = [0,1,2,3,4,5]

# Compute horizon.
horizon = sum(task[1] for job in my_job_list for task in job)

task_type = collections.namedtuple('task_type', 'start end interval')
assigned_task_type = collections.namedtuple('assigned_task_type','start job index')

#NewIntVar設至非連續整數型變數
all_tasks = {}
for job in all_jobs:
    for task_id, task in enumerate(my_task[job]):
        start_var = model.NewIntVar(0, horizon,'start_%i_%i' % (job, task_id))
        duration = task[1]
        end_var = model.NewIntVar(0, horizon, 'end_%i_%i' % (job, task_id))
        interval_var = model.NewIntervalVar(start_var, duration, end_var, 'interval_%i_%i' % (job, task_id))
        all_tasks[job, task_id] = task_type(start=start_var, end=end_var, interval=interval_var)
        
# Create and add disjunctive constraints.
# AddNoOverlap使參數中時間 間格無法重疊
for machine in all_machines:
    intervals = []
    for job in all_jobs:
        for task_id, task in enumerate(my_job_list[job]):
            if task[0] == machine:
                intervals.append(all_tasks[job, task_id].interval)
    model.AddNoOverlap(intervals)
    
# Add precedence contraints.
for job in all_jobs:
    for task_id in range(0, len(my_job_list[job]) - 1):
        model.Add(all_tasks[job, task_id +1].start >= all_tasks[job, task_id].end)

# Makespan objective.
#AddMaxEquality Minimize做最大最小近似值
obj_var = model.NewIntVar(0, horizon, 'makespan')
model.AddMaxEquality(
    obj_var,
    [all_tasks[(job, len(my_job_list[job]) - 1)].end for job in all_jobs])
model.Minimize(obj_var)


# Solve model.
#CpSolver 模型中的求解器
solver = cp_model.CpSolver()
status = solver.Solve(model)


if status == cp_model.OPTIMAL:
    # Print out makespan.
    print('Optimal Schedule Length: %i' % solver.ObjectiveValue())
    print()

    # Create one list of assigned tasks per machine.
    assigned_jobs = [[] for _ in all_machines]
    for job in all_jobs:
        for task_id, task in enumerate(my_job_list[job]):
            machine = task[0]
            assigned_jobs[machine].append(
                assigned_task_type(
                    start=solver.Value(all_tasks[job, task_id].start),
                    job=job,
                    index=task_id))

    disp_col_width = 10
    sol_line = ''
    sol_line_tasks = ''

    print('Optimal Schedule', '\n')

    for machine in all_machines:
        # Sort by starting time.
        assigned_jobs[machine].sort()
        sol_line += 'Machine ' + str(machine) + ': '
        sol_line_tasks += 'Machine ' + str(machine) + ': '

        for assigned_task in assigned_jobs[machine]:
            name = 'job_%i_%i' % (assigned_task.job, assigned_task.index)
            # Add spaces to output to align columns.
            sol_line_tasks += name + ' ' * (disp_col_width - len(name))
            start = assigned_task.start
            duration = my_job_list[assigned_task.job][assigned_task.index][1]

            sol_tmp = '[%i,%i]' % (start, start + duration)
            # Add spaces to output to align columns.
            sol_line += sol_tmp + ' ' * (disp_col_width - len(sol_tmp))

        sol_line += '\n'
        sol_line_tasks += '\n'

    print(sol_line_tasks)
    print('Task Time Intervals\n')
    print(sol_line)