OR-Tools:5-调度问题（Scheduling）

OR-Tools 解决的问题类型： 

Linear optimizationConstraint optimizationMixed-integer optimizationBin packingNetwork flowsAssignmentSchedulingRouting

调度问题：

调度：在特定时间为任务分配人员和资源。例如

安排员工进行多班制，但须遵守一系列复杂的约束和人员配置要求安排一个制造流程，该流程涉及在一组有限的计算机上执行许多任务，每台计算机一次只能执行一项任务。

这个看起来在CP-SAT里面有提到用约束编程进行解决

 

from ortools.sat.python import cp_model def main(): # This program tries to find an optimal assignment of nurses to shifts # (3 shifts per day, for 7 days), subject to some constraints (see below). # Each nurse can request to be assigned to specific shifts. # The optimal assignment maximizes the number of fulfilled shift requests. num_nurses = 5 num_shifts = 3 num_days = 7 all_nurses = range(num_nurses) all_shifts = range(num_shifts) all_days = range(num_days) shift_requests = [[[0, 0, 1], [0, 0, 0], [0, 0, 0], [0, 0, 0], [0, 0, 1], [0, 1, 0], [0, 0, 1]], [[0, 0, 0], [0, 0, 0], [0, 1, 0], [0, 1, 0], [1, 0, 0], [0, 0, 0], [0, 0, 1]], [[0, 1, 0], [0, 1, 0], [0, 0, 0], [1, 0, 0], [0, 0, 0], [0, 1, 0], [0, 0, 0]], [[0, 0, 1], [0, 0, 0], [1, 0, 0], [0, 1, 0], [0, 0, 0], [1, 0, 0], [0, 0, 0]], [[0, 0, 0], [0, 0, 1], [0, 1, 0], [0, 0, 0], [1, 0, 0], [0, 1, 0], [0, 0, 0]]] # Creates the model. model = cp_model.CpModel() # Creates shift variables. # shifts[(n, d, s)]: nurse 'n' works shift 's' on day 'd'. shifts = {} for n in all_nurses: for d in all_days: for s in all_shifts: shifts[(n, d, s)] = model.NewBoolVar('shift_n%id%is%i' % (n, d, s)) # Each shift is assigned to exactly one nurse in . for d in all_days: for s in all_shifts: model.Add(sum(shifts[(n, d, s)] for n in all_nurses) == 1) # Each nurse works at most one shift per day. for n in all_nurses: for d in all_days: model.Add(sum(shifts[(n, d, s)] for s in all_shifts) <= 1) # Try to distribute the shifts evenly, so that each nurse works # min_shifts_per_nurse shifts. If this is not possible, because the total # number of shifts is not divisible by the number of nurses, some nurses will # be assigned one more shift. min_shifts_per_nurse = (num_shifts * num_days) // num_nurses if num_shifts * num_days % num_nurses == 0: max_shifts_per_nurse = min_shifts_per_nurse else: max_shifts_per_nurse = min_shifts_per_nurse + 1 for n in all_nurses: num_shifts_worked = 0 for d in all_days: for s in all_shifts: num_shifts_worked += shifts[(n, d, s)] model.Add(min_shifts_per_nurse <= num_shifts_worked) model.Add(num_shifts_worked <= max_shifts_per_nurse) # pylint: disable=g-complex-comprehension model.Maximize( sum(shift_requests[n][d][s] * shifts[(n, d, s)] for n in all_nurses for d in all_days for s in all_shifts)) # Creates the solver and solve. solver = cp_model.CpSolver() solver.Solve(model) for d in all_days: print('Day', d) for n in all_nurses: for s in all_shifts: if solver.Value(shifts[(n, d, s)]) == 1: if shift_requests[n][d][s] == 1: print('Nurse', n, 'works shift', s, '(requested).') else: print('Nurse', n, 'works shift', s, '(not requested).') print() # Statistics. print() print('Statistics') print(' - Number of shift requests met = %i' % solver.ObjectiveValue(), '(out of', num_nurses * min_shifts_per_nurse, ')') print(' - wall time : %f s' % solver.WallTime()) if __name__ == '__main__': main() Day 0 Nurse 1 works shift 0 (not requested). Nurse 2 works shift 1 (requested). Nurse 3 works shift 2 (requested). Day 1 Nurse 0 works shift 0 (not requested). Nurse 2 works shift 1 (requested). Nurse 4 works shift 2 (requested). Day 2 Nurse 1 works shift 2 (not requested). Nurse 3 works shift 0 (requested). Nurse 4 works shift 1 (requested). Day 3 Nurse 2 works shift 0 (requested). Nurse 3 works shift 1 (requested). Nurse 4 works shift 2 (not requested). Day 4 Nurse 0 works shift 2 (requested). Nurse 1 works shift 0 (requested). Nurse 4 works shift 1 (not requested). Day 5 Nurse 0 works shift 2 (not requested). Nurse 2 works shift 1 (requested). Nurse 3 works shift 0 (requested). Day 6 Nurse 0 works shift 1 (not requested). Nurse 1 works shift 2 (requested). Nurse 4 works shift 0 (not requested). Statistics - Number of shift requests met = 13 (out of 20 ) - wall time : 0.003571 s

个常见的调度问题是作业车间，其中多个作业在多台计算机上处理。每个作业都包含一系列任务，这些任务必须按给定顺序执行，并且每个任务都必须在特定计算机上处理。例如，作业可能是单个消费品（如汽车）的制造。问题是在计算机上安排任务，以便最大限度地减少计划的长度，即完成所有作业的时间。

作业车间问题有几个限制因素：

在该作业的上一个任务完成之前，不能启动作业的任务。一台计算机一次只能处理一项任务。任务一旦启动，必须运行到完成。 from __future__ import print_function import collections # Import Python wrapper for or-tools CP-SAT solver. from ortools.sat.python import cp_model def MinimalJobshopSat(): """Minimal jobshop problem.""" # Create the model. model = cp_model.CpModel() jobs_data = [ # task = (machine_id, processing_time). [(0, 3), (1, 2), (2, 2)], # Job0 [(0, 2), (2, 1), (1, 4)], # Job1 [(1, 4), (2, 3)] # Job2 ] machines_count = 1 + max(task[0] for job in jobs_data for task in job) all_machines = range(machines_count) # Computes horizon dynamically as the sum of all durations. horizon = sum(task[1] for job in jobs_data for task in job) # Named tuple to store information about created variables. task_type = collections.namedtuple('task_type', 'start end interval') # Named tuple to manipulate solution information. assigned_task_type = collections.namedtuple('assigned_task_type', 'start job index duration') # Creates job intervals and add to the corresponding machine lists. all_tasks = {} machine_to_intervals = collections.defaultdict(list) for job_id, job in enumerate(jobs_data): for task_id, task in enumerate(job): machine = task[0] duration = task[1] suffix = '_%i_%i' % (job_id, task_id) start_var = model.NewIntVar(0, horizon, 'start' + suffix) end_var = model.NewIntVar(0, horizon, 'end' + suffix) interval_var = model.NewIntervalVar(start_var, duration, end_var, 'interval' + suffix) all_tasks[job_id, task_id] = task_type( start=start_var, end=end_var, interval=interval_var) machine_to_intervals[machine].append(interval_var) # Create and add disjunctive constraints. for machine in all_machines: model.AddNoOverlap(machine_to_intervals[machine]) # Precedences inside a job. for job_id, job in enumerate(jobs_data): for task_id in range(len(job) - 1): model.Add(all_tasks[job_id, task_id + 1].start >= all_tasks[job_id, task_id].end) # Makespan objective. obj_var = model.NewIntVar(0, horizon, 'makespan') model.AddMaxEquality(obj_var, [ all_tasks[job_id, len(job) - 1].end for job_id, job in enumerate(jobs_data) ]) model.Minimize(obj_var) # Solve model. solver = cp_model.CpSolver() status = solver.Solve(model) if status == cp_model.OPTIMAL: # Create one list of assigned tasks per machine. assigned_jobs = collections.defaultdict(list) for job_id, job in enumerate(jobs_data): for task_id, task in enumerate(job): machine = task[0] assigned_jobs[machine].append( assigned_task_type( start=solver.Value(all_tasks[job_id, task_id].start), job=job_id, index=task_id, duration=task[1])) # Create per machine output lines. output = '' for machine in all_machines: # Sort by starting time. assigned_jobs[machine].sort() sol_line_tasks = 'Machine ' + str(machine) + ': ' sol_line = ' ' 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 += '%-10s' % name start = assigned_task.start duration = assigned_task.duration sol_tmp = '[%i,%i]' % (start, start + duration) # Add spaces to output to align columns. sol_line += '%-10s' % sol_tmp sol_line += '\n' sol_line_tasks += '\n' output += sol_line_tasks output += sol_line # Finally print the solution found. print('Optimal Schedule Length: %i' % solver.ObjectiveValue()) print(output) MinimalJobshopSat()

 

Optimal Schedule Length: 11 Optimal Schedule Machine 0: job_0_0 job_1_0 Machine 1: job_2_0 job_0_1 job_1_2 Machine 2: job_1_1 job_0_2 job_2_1 Task Time Intervals Machine 0: [0,3] [3,5] Machine 1: [0,4] [4,6] [7,11] Machine 2: [5,6] [6,8] [8,11]