OR |
您所在的位置：网站首页 › output案例 › OR |
OR
|
目录
前言一、调度问题介绍二、案例分析2-1、护士调度问题2-2、作业车间调度问题
三、知识库3-1、collection3-2、CpModel().AddNoOverlap()3-3、CpModel().AddMaxEquality()3-4、cp_model.CpModel().NewIntVar()3-5、cp_model.CpModel().NewIntervalVar
总结
前言
调度问题是一类重要且常见的组合优化问题，涉及在有限资源和时间约束下，合理地安排任务或活动的顺序和时间，以优化某种目标函数。调度问题广泛应用于生产制造、物流运输、项目管理、计算机任务调度、作业调度等领域。
一、调度问题介绍
调度问题是一类重要且常见的组合优化问题，涉及在有限资源和时间约束下，合理地安排任务或活动的顺序和时间，以优化某种目标函数。调度问题广泛应用于生产制造、物流运输、项目管理、计算机任务调度、作业调度等领域。 常见的调度问题包括： 作业车间调度问题（Job Shop Scheduling Problem）：给定一组作业和一组可并行执行的机器，每个作业需要在不同的机器上按照特定的顺序完成。目标是最小化完成所有作业所需的时间或最大化生产效率。流水线调度问题（Flow Shop Scheduling Problem）：类似于作业车间调度问题，但在流水线调度问题中，每个作业需要按照相同的顺序通过一组机器。车辆路径问题（Vehicle Routing Problem）：给定一组客户点和一组配送车辆，车辆需要从一个中心出发，访问每个客户点，并返回中心，以最小化总配送成本或最小化车辆的总行驶距离。资源约束项目调度问题（Resource-Constrained Project Scheduling Problem）：在项目中有多个任务，每个任务需要特定的资源和时间才能完成。目标是在满足资源和时间约束的情况下，最小化项目的总工期或最大化资源利用率。多处理器任务调度问题（Multiprocessor Task Scheduling Problem）：将一组任务分配给多个处理器，并尽量平衡负载，以最小化任务完成时间或最大化处理器利用率。工人任务调度问题（Job Allocation Problem）：在工人和任务之间建立对应关系，以最大化完成任务的总价值或最小化工人的总工作时间。解决调度问题的方法通常包括贪心算法、启发式算法、精确的优化算法（如整数线性规划和约束编程）以及元启发式算法（如遗传算法和模拟退火算法）。调度问题的复杂性通常取决于任务和资源之间的约束条件，有些调度问题是 NP-hard 问题，意味着找到最优解可能需要指数级的时间。 二、案例分析 2-1、护士调度问题护士调度问题： 员工轮班多次轮班的组织需要为每天的轮班安排足够的工作器。通常，时间表会有一些限制，例如“任何员工都不应在一个班次中连续两次班次”。查找满足所有约束的时间表可能在计算上很困难。 护士调度问题： 在下一个示例中，医院主管需要根据 3 天条件为 4 位护士创建时间表： 一天每天轮班，一天三次。每天，每个班次都会分配给一位护士，没有超过一个班次的护士工作。在这 3 天里，每位护士都至少分配到两个班次。接下来，我们将展示根据以下约束条件为护士的轮班分配护士： 每个班次分配给每天一名护士。一名护士每天最多只会轮班一次。代码中的约束条件图解： 具体代码如下： #导入所需库，定义护士数量、轮班次数、天数 from ortools.sat.python import cp_model num_nurses = 4 num_shifts = 3 num_days = 3 all_nurses = range(num_nurses) all_shifts = range(num_shifts) all_days = range(num_days) # 创建模型、创建Bool类型变量数组(n, d, s)-->（护士编号，哪一天，哪一个轮班），定义了针对护士的轮班分配。 #即如果将 shift s 分配给 d 天中的护士 n，shifts[(n, d, s)] 的值为 1，否则为 0。 model = cp_model.CpModel() 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)) # 确保每一天的每一个轮班只有一个护士 for d in all_days: for s in all_shifts: model.AddExactlyOne(shifts[(n, d, s)] for n in all_nurses) # 确保每一名护士每天最多轮班一次。 for n in all_nurses: for d in all_days: model.AddAtMostOne(shifts[(n, d, s)] for s in all_shifts) # 尽量分配均匀，设定每个护士应该上的最小轮班次数和最大轮班次数。 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 # 指定每一个护士的最小轮班数为2，最大轮班数为3。 for n in all_nurses: shifts_worked = [] for d in all_days: for s in all_shifts: shifts_worked.append(shifts[(n, d, s)]) model.Add(min_shifts_per_nurse solver.ObjectiveValue()}') print(output) else: print('No solution found.') # Statistics. print('\nStatistics') print(' - conflicts: %i' % solver.NumConflicts()) print(' - branches : %i' % solver.NumBranches()) print(' - wall time: %f s' % solver.WallTime()) if __name__ == '__main__': main()输出： *Solution: Optimal Schedule Length: 11.0 Machine 0: job_1_task_0 job_0_task_0 [0,2] [2,5] Machine 1: job_2_task_0 job_0_task_1 job_1_task_2 [0,4] [5,7] [7,11] Machine 2: job_1_task_1 job_2_task_1 job_0_task_2 [2,3] [4,7] [7,9] Statistics conflicts: 0branches : 0wall time: 0.018851 s* 三、知识库 3-1、collection在 Python 中，collections 是一个标准库模块，提供了一些有用的数据结构和工具，用于扩展内置数据类型的功能。collections 模块包含了多种集合类型，这些类型可以用于更高效地管理和处理数据。一些常用的集合类型包括： namedtuple（命名元组）：namedtuple 是一个工厂函数，用于创建一个具名的元组子类。命名元组的每个元素都有自己的字段名，这使得元组的每个位置都有一个易于理解的名称。它可以使代码更具可读性。deque（双向队列）：deque 是双向队列，支持在队列两端进行高效的插入和删除操作。与列表相比，deque 在头部插入和删除元素的时间复杂度是 O(1)，而列表是 O(n)。Counter（计数器）：Counter 是一个简单的计数器工具，用于统计可哈希对象的出现次数。它可以用于计算列表、字符串等中元素的频率。OrderedDict（有序字典）：OrderedDict 是一个有序字典类型，它会维护插入元素的顺序，可以按照插入顺序遍历字典。defaultdict（默认字典）：defaultdict 是一个字典类型，它可以指定默认值，当访问字典中不存在的键时，会返回指定的默认值，而不是抛出异常。ChainMap（链式映射）：ChainMap 可以将多个字典或映射对象链接在一起，形成一个逻辑上的映射链。Counter（计数器）：Counter 是一个简单的计数器工具，用于统计可哈希对象的出现次数。它可以用于计算列表、字符串等中元素的频率。下边以namedtuple（命名元组为例来进行介绍）：创建命名元组子类的工厂函数，生成可以使用名字来访问元素内容的tuple子类 参数介绍 namedtuple(typename,field_names,*,verbose=False, rename=False, module=None) typename：该参数指定所创建的tuple子类的类名，相当于用户定义了一个新类。 field_names：该参数是一个字符串序列，如 [‘x’，‘y’]。此外，field_names 也可直接使用单个字符串代表所有字段名，多个字段名用空格、逗号隔开，如 ‘x y’ 或 ‘x,y’。任何有效的 Python 标识符都可作为字段名（不能以下画线开头）。有效的标识符可由字母、数字、下画线组成，但不能以数字、下面线开头，也不能是关键字（如 return、global、pass、raise 等）。 rename：如果将该参数设为 True，那么无效的字段名将会被自动替换为位置名。例如指定 [‘abc’,‘def’,‘ghi’,‘abc’]，它将会被替换为 [‘abc’, ‘_1’,‘ghi’,‘_3’]，这是因为 def 字段名是关键字，而 abc 字段名重复了。 verbose：如果该参数被设为 True，那么当该子类被创建后，该类定义就被立即打印出来。 module：如果设置了该参数，那么该类将位于该模块下，因此该自定义类的 module 属性将被设为该参数值。 案例分析： from collections import namedtuple # 定义命名元组类型 task_type = namedtuple('task_type', 'start end interval') # 创建一个命名元组实例 start_var = 0 end_var = 10 interval_var = 5 task_instance = task_type(start=start_var, end=end_var, interval=interval_var) # 访问命名元组的字段值 print(task_instance.start) # 输出: 0 print(task_instance.end) # 输出: 10 print(task_instance.interval) # 输出: 5 # 定义了一个命名元组 task_type，它有三个字段：start、end 和 interval。 # 接下来，task_type(start=start_var, end=end_var, interval=interval_var) 这行代码实际上是在创建一个 task_type 命名元组的实例，并将参数 start_var、end_var 和 interval_var 分别赋值给相应的字段。 # 这样的命名元组实例可以像普通的元组一样被访问和操作，但是由于每个字段都有一个名字，所以可以通过字段名来获取元组的值，使得代码更加清晰易读 3-2、CpModel().AddNoOverlap()含义：是用来添加一个“无重叠”约束的方法。"无重叠"约束通常用于安排一组任务或活动在时间上不会发生重叠。这可以确保在特定时间段内，只有一个任务或活动会被安排。 案例分析： from ortools.sat.python import cp_model model = cp_model.CpModel() # 任务1，开始时间为0，持续时间为2，结束时间为2 start_1 = model.NewIntVar(0, 10, 'start_1') duration_1 = 2 end_1 = model.NewIntVar(0, 10, 'end_1') interval_1 = model.NewIntervalVar(start_1, duration_1, end_1, 'interval_1') # 任务2，开始时间为0，持续时间为2，结束时间为2 start_2 = model.NewIntVar(0, 10, 'start_2') duration_2 = 2 end_2 = model.NewIntVar(0, 10, 'end_2') interval_2 = model.NewIntervalVar(start_2, duration_2, end_2, 'interval_2') # 任务3，开始时间为0，持续时间为2，结束时间为2 start_3 = model.NewIntVar(0, 10, 'start_3') duration_3 = 2 end_3 = model.NewIntVar(0, 10, 'end_3') interval_3 = model.NewIntervalVar(start_3, duration_3, end_3, 'interval_3') model.AddNoOverlap([interval_1, interval_2, interval_3]) solver = cp_model.CpSolver() status = solver.Solve(model) if status == cp_model.OPTIMAL: print('任务1开始于：', solver.Value(start_1)) print('任务2开始于：', solver.Value(start_2)) print('任务3开始于：', solver.Value(start_3))输出： 含义：model.AddMaxEquality() 是一个约束编程（Constraint Programming）模块（cp_model）中提供的方法，用于将一组变量的最大值相等的约束添加到模型中。 语法 model.AddMaxEquality(target_var, variable_array) target_var：表示目标变量，它是一个整数变量（IntVar），用于存储变量数组中的最大值。variable_array：表示变量数组，即需要求最大值的一组整数变量。AddMaxEquality() 方法会将目标变量 target_var 的值设置为变量数组 variable_array 中的最大值。案例如下： # Import the required module from ortools.sat.python import cp_model # Instantiate the CP-SAT model. model = cp_model.CpModel() # Define the capacities br1_cap = 5 br2_cap = 4 br3_cap = 6 # Given tasks tasks = 10 # Define variables for the tasks assigned to each branch br1_tasks = model.NewIntVar(0, br1_cap, 'br1') br2_tasks = model.NewIntVar(0, br2_cap, 'br2') br3_tasks = model.NewIntVar(0, br3_cap, 'br3') # Define the variable for the maximum tasks max_tasks = model.NewIntVar(0, max(br1_cap, br2_cap, br3_cap), 'max_tasks') # Tell the model that max_tasks is the maximum number of tasks assigned to any branch model.AddMaxEquality(max_tasks, [br1_tasks, br2_tasks, br3_tasks]) # Add constraints that the tasks assigned to all branches should equal the given tasks model.Add(br1_tasks + br2_tasks + br3_tasks == tasks) # Create a solver solver = cp_model.CpSolver() status = solver.Solve(model) # Print the assignments if status == cp_model.OPTIMAL: print("Branch 1 tasks: ", solver.Value(br1_tasks)) print("Branch 2 tasks: ", solver.Value(br2_tasks)) print("Branch 3 tasks: ", solver.Value(br3_tasks)) print("Maximum tasks assigned to a branch: ", solver.Value(max_tasks))输出如下： Branch 1 tasks: 0 Branch 2 tasks: 4 Branch 3 tasks: 6 Maximum tasks assigned to a branch: 6 3-4、cp_model.CpModel().NewIntVar()含义：cp_model.CpModel().NewIntVar() 是用于创建一个新的整数变量（IntVar）的方法。整数变量是用于建模整数类型的未知数，可以代表问题中的状态、决策变量或者其他需要求解的值。 语法： NewIntVar(lb, ub, name)参数说明： lb（lower bound）：整数变量的下界，表示整数变量的取值范围最小值。ub（upper bound）：整数变量的上界，表示整数变量的取值范围最大值。name：整数变量的名称（可选），用于在输出中标识和识别变量。案例分析： from ortools.sat.python import cp_model def simple_integer_variable_example(): # 创建约束编程模型 model = cp_model.CpModel() # 创建整数变量 x，范围为 [0, 10] x = model.NewIntVar(0, 10, 'x') # 创建约束条件：x >= 5 model.Add(x >= 5) # 创建求解器并求解模型 solver = cp_model.CpSolver() status = solver.Solve(model) if status == cp_model.OPTIMAL: print('x 的值：', solver.Value(x)) else: print('找不到可行解。') if __name__ == '__main__': simple_integer_variable_example()输出的值： x 的值： 5 3-5、cp_model.CpModel().NewIntervalVar含义：cp_model.CpModel().NewIntervalVar() 是用于创建一个时间区间变量（IntervalVar）的方法。时间区间变量用于表示任务或活动在时间上的开始和结束。 NewIntervalVar() 方法的语法如下： NewIntervalVar(start_var, duration, end_var, name)参数说明： start_var：表示任务开始时间的整数变量（IntVar）或整数值。通常为一个整数变量，但也可以是一个固定的整数值，表示任务的开始时间。duration：表示任务持续时间的整数值或整数变量。任务持续时间可以是固定的整数值，也可以是一个整数变量，其值在运行时确定。end_var：表示任务结束时间的整数变量（IntVar）或整数值。通常为一个整数变量，但也可以是一个固定的整数值，表示任务的结束时间。name：时间区间变量的名称（可选），用于在输出中标识和识别变量。时间区间变量的特点是它们允许任务的开始和结束时间在求解时进行灵活地调整，从而满足给定的约束条件，例如任务之间不重叠、任务的持续时间等。 案例分析： from ortools.sat.python import cp_model def simple_interval_variable_example(): # 创建约束编程模型 model = cp_model.CpModel() # 创建整数变量表示任务的开始时间和结束时间 start_var = model.NewIntVar(0, 100, 'start_var') end_var = model.NewIntVar(0, 100, 'end_var') # 创建整数变量表示任务的持续时间 duration = model.NewIntVar(10, 50, 'duration') # 创建时间区间变量 task_interval = model.NewIntervalVar(start_var, duration, end_var, 'task_interval') # 创建约束条件：任务的开始时间和结束时间之间存在关系 model.Add(end_var == start_var + duration) # 创建求解器并求解模型 solver = cp_model.CpSolver() status = solver.Solve(model) if status == cp_model.OPTIMAL: print('任务开始时间：', solver.Value(start_var)) print('任务结束时间：', solver.Value(end_var)) print('任务持续时间：', solver.Value(duration)) else: print('找不到可行解。') if __name__ == '__main__': simple_interval_variable_example()输出： 任务开始时间： 0 任务结束时间： 10 任务持续时间： 10 参考文章： OR-Tools官网. 【万字长文详解】Python库collections，让你击败99%的Pythoner. 总结要经历过多少次，才不会反反复复踏入同一条河流。 |
【本文地址】
今日新闻 |
点击排行 |
|
推荐新闻 |
图片新闻 |
|
专题文章 |