排程逻辑详解概述本系统是一个基于约束规划 (Constraint Programming)的生产排程系统使用求解器来解决作业车间调度问题 (Job Shop Scheduling Problem, JSSP)。系统的核心目标是在满足所有约束条件的前提下找到使总完工时间makespan最小的排程方案。问题定义输入数据订单 (Orders)订单号、产品编码、数量、交期、优先级工艺路线 (Processes)产品编码、工序号、工序名称、工序顺序单件标准工时分钟、所需设备、前置工序设备 (Equipment)设备编号、状态、效率系数每日工作时长小时、可用时间窗口输出结果每个工序的开始时间、结束时间、分配设备总完工时间makespan设备利用率、交期达成率、瓶颈设备核心流程1. 数据预处理 (_preprocess_data)目的将原始数据转换为求解器可用的结构构建索引以提高查询效率。构建的数据结构# 产品到工艺路线的映射product_to_processes:Dict[str,List[Process]]# 例如: {P01: [工序1, 工序2, 工序3]}# 设备组到设备列表的映射equipment_group_to_equipment:Dict[str,List[Equipment]]# 例如: {M01,M02: [设备M01, 设备M02]}# 设备每日工作时长分钟equipment_daily_capacity:Dict[str,float]# 例如: {M01: 480.0} # 8小时 480分钟# 所有需要排程的(订单, 工序)对job_operations:List[Tuple[Order,Process]]时间范围估算# 计算总工作量total_work_minutesΣ(订单数量 × 单件工时)# 估算需要的天数添加2倍缓冲estimated_days(total_work_minutes/平均每日产能)×2estimated_daysmax(estimated_days,30)# 至少30天# 计算时间范围horizonhorizonestimated_days ×24小时 ×60分钟说明horizon 是求解器搜索空间的上界设置得太小可能无解太大会影响求解效率。2. 构建优化模型 (build_model)决策变量对每个工序(订单i, 工序j)创建以下变量变量类型说明取值范围----rt_var开始时间[0, horizon] 分钟end_------ 结束时间[0, horizon] 分钟–resence_var是否在设备k上执行{0, 1} 布尔值-----rval_var时间区间[start, duration, end]##--------制如果一个工序可以在多台设备上执行例如 “M01,M02”系统会为每台可用设备创建一个presence_var和interval_var添加约束sum(presence_vars) 1必须选择恰好一台设备求解器自动选择最优的设备分配示例工序:车削,可用设备:[M01,M02]变量:-presence_M01:是否在M01上执行-presence_M02:是否在M02上执行-interval_M01:在M01上的时间区间可选-interval_M02:在M02上的时间区间可选 约束:-presence_M01presence_M021工序持续时间计算duration单件标准工时 × 订单数量示例单件工时5分钟订单数量100件持续时间500分钟3. 添加约束 (add_constraints)约束1工艺顺序约束规则工序必须按照工艺路线的顺序执行# 对于同一订单的连续工序工序i的结束时间工序i1的开始时间# 对于有显式前置工序的情况前置工序的结束时间当前工序的开始时间示例订单SO001的工艺路线车削 → 铣削 → 检验 约束 - 车削.end_time 铣削.start_time - 铣削.end_time 检验.start_time约束2设备互斥约束规则同一台设备不能同时执行多个工序model.AddNoOverlap(设备k的所有区间变量)这个约束确保分配到同一设备的所有工序在时间上不重叠。示例设备M01上的工序 - 订单1的车削: [0, 500] - 订单2的车削: [500, 1000] ✓ 不重叠 - 订单3的车削: [450, 950] ✗ 与订单2重叠不允许约束3时间约束规则结束时间 开始时间 持续时间end_timestart_time(单件工时 × 订单数量)约束4时间窗口约束规则所有工序的开始时间必须非负start_time0扩展可以根据设备的available_start和available_end添加更复杂的时间窗口约束。4. 设置优化目标 (set_objective)目标函数最小化总完工时间makespanmakespanmax(所有工序的结束时间)minimize(makespan)目标变量# 创建makespan变量makespan_varmodel.NewIntVar(0,horizon,makespan)# 添加约束makespan 所有工序的结束时间foreach operation:model.Add(makespan_varoperation.end_time)# 设置优化目标model.Minimize(makespan_var)其他可能的优化目标虽然当前系统使用 makespan 作为目标但也可以考虑最小化总延期时间最小化设备切换次数最大化设备利用率多目标优化加权组合5. 求解 (solve)求解流程1.构建模型(build_model)2.添加约束(add_constraints)3.设置优化目标(set_objective)4.创建求解器5.设置求解器参数6.执行求解7.提取结果求解器参数solver.parameters.max_time_in_seconds60.0# 最大求解时间60秒求解状态状态说明---MAL找到最优解并证明了最优性F--- E找到可行解但未证明最优----- IBLE无可行解约束冲突OWN求解超时或其他原因#### |约束过于严格交期太紧设备产能不足工艺路线冲突数据错误工序顺序错误设备类型不匹配时间估算不合理6. 提取结果 (extract_solution)步骤1获取工序时间从求解器获取每个工序的开始和结束时间工作分钟start_timesolver.Value(start_var)# 例如: 0end_timesolver.Value(end_var)# 例如: 500durationend_time-start_time# 例如: 500分钟步骤2确定分配的设备检查哪个presence_var的值为 1forequipmentinavailable_equipment:ifsolver.Value(presence_var[equipment])1:assigned_equipmentequipmentbreak步骤3转换为日历时间核心函数_work_minutes_to_datetime转换逻辑# 输入工作分钟数连续时间# 输出日历datetime考虑每日工作时长# 1. 计算是第几个工作日work_day工作分钟//每日工作分钟# 2. 计算当天的工作分钟数minutes_in_day工作分钟%每日工作分钟# 3. 计算实际日期时间result_date基准日期work_day天 result_datetimeresult_date的8:00minutes_in_day示例设备M01每日工作:480分钟8小时 基准日期:2024-03-0608:00工作分钟1000work_day1000//4802第2天 minutes_in_day1000%48040result_datetime2024-03-0808:40为什么需要转换求解器使用连续时间工作分钟进行优化用户需要看到实际的日历时间考虑每天的工作时间转换确保结果符合实际生产场景步骤4计算 makespan# 找到最早开始和最晚结束min_start_timemin(op.start_timeforopinoperations)max_end_timemax(op.end_timeforopinoperations)# 计算日历时间跨度小时makespan(max_end_time-min_start_time).total_seconds()/3600.0算法特性✅ 优势全局最优CP-SAT 求解器能找到全局最优解在时间限制内不会陷入局部最优灵活的设备分配自动选择最优设备实现负载均衡支持设备组概念严格的约束保证100% 遵守工艺顺序绝对不会出现设备冲突保证所有约束条件考虑实际工作时间每台设备独立的工作时长自动跳过非工作时间结果以日历时间呈现批量生产支持正确处理订单数量工时 单件工时 × 数量⚠️ 局限性求解时间大规模问题可能需要较长时间当前限制60秒简化假设假设设备从时间0开始可用未考虑设备故障、维护未考虑人员限制优化目标单一仅优化 makespan未考虑成本、能耗等因素完整示例输入数据订单订单号: SO001 产品: P01 数量: 100件 交期: 2024-03-10工艺路线产品P011. 车削: 单件5分钟, 设备: M01,M02 2. 铣削: 单件3分钟, 设备: M03 3. 检验: 单件1分钟, 设备: M04设备M01: 车床, 每日8小时 M02: 车床, 每日8小时 M03: 铣床, 每日8小时 M04: 检验台, 每日8小时求解过程1. 数据预处理job_operations[(SO001,车削),(SO001,铣削),(SO001,检验)]总工作量(531)×100900分钟2. 构建模型# 为车削工序创建变量start_车削IntVar(0,horizon)end_车削IntVar(0,horizon)duration_车削5×100500分钟 presence_M01BoolVar()presence_M02BoolVar()约束:presence_M01presence_M0213. 添加约束# 工艺顺序end_车削start_铣削 end_铣削start_检验# 设备互斥AddNoOverlap(M01的所有区间)AddNoOverlap(M02的所有区间)...# 时间约束end_车削start_车削500end_铣削start_铣削300end_检验start_检验1004. 求解求解器找到最优解:-车削在M01上执行:0-500分钟-铣削在M03上执行:500-800分钟-检验在M04上执行:800-900分钟5. 转换为日历时间基准日期:2024-03-0608:00M01每日工作:480分钟 车削:start:0分钟 →2024-03-0608:00end:500分钟 →2024-03-0708:20(第1天:0-480,第2天:480-500)铣削:start:500分钟 →2024-03-0708:20end:800分钟 →2024-03-0809:40检验:start:800分钟 →2024-03-0809:40end:900分钟 →2024-03-0811:20输出结果订单: SO001 总完工时间: 51.33小时2天3小时20分 工序详情: ┌────────┬──────┬─────────────────┬─────────────────┬──────────┐ │ 工序 │ 设备 │ 开始时间 │ 结束时间 │ 工时(h) │ ├────────┼──────┼─────────────────┼─────────────────┼──────────┤ │ 车削 │ M01 │ 03-06 08:00 │ 03-07 08:20 │ 8.33 │ │ 铣削 │ M03 │ 03-07 08:20 │ 03-08 09:40 │ 5.00 │ │ 检验 │ M04 │ 03-08 09:40 │ 03-08 11:20 │ 1.67 │ └────────┴──────┴─────────────────┴─────────────────┴──────────┘ 设备利用率: - M01: 16.2% - M02: 0% - M03: 9.7% - M04: 3.2% 交期达成: ✓ (完工时间 交期)扩展方向1. 多目标优化# 加权目标函数objectivew1 × makespanw2 × 延期惩罚w3 × 设备切换成本2. 动态排程支持插单、急单实时调整排程考虑在制品状态3. 高级约束设备维护时间窗口人员技能匹配物料可用性能源消耗限制4. 启发式算法对于超大规模问题可以结合遗传算法模拟退火禁忌搜索5. 机器学习学习历史数据预测工时智能调整优先级预测瓶颈设备总结本排程系统通过约束规划技术将复杂的生产排程问题转化为数学优化问题由求解器自动找到最优解。系统的核心优势在于自动化无需手动编写复杂的调度规则最优性在时间限制内找到全局最优解灵活性易于添加新的约束和目标可靠性保证所有约束条件得到满足这使得系统能够高效地处理实际生产中的复杂排程问题。| |