如何在OR-Tools CP-SAT生产排程中允许并惩罚交付延迟？

背景信息 #

我基于NewIntervalVar开发OR-Tools CP-SAT生产排程优化系统，核心需求是通过不同延迟等级设置差异化售价，最大化排程利润（不禁止生产/交付延迟）。相关数据定义如下：

客户订单数据 #

按产品编号存储为字典，每个产品对应多组「数量+期望交付日」的订单：

order_per_product = {
0:[[25,0],[75,2],[15,3]],  #产品0：[[数量,期望交付日],[订单2...]]
1:[[112,0],[240,5]],       #产品1：...
2:[[785,4]],
3:[[25,1],[425,3],[78,4]],
4:[[155,3],[78,6],[45,7]] 
}

延迟等级售价 #

不同延迟天数对应不同单价：

sales_price = {
0:12, #无延迟→单价12€
1:11, #延迟1天→单价11€
2:9,
3:7,
4:5}

生产计划变量 #

定义50个生产批次的变量列表，每个批次包含产品编号、生产数量、生产日：

production_schedle = []
for i in range(50):
   NrProduct = solver.IntVar(0, 4, f'NrProduct_{i}')
   quantity = solver.IntVar(1, 55, f'quantity_{i}')
   day = solver.IntVar(0, 30, f'day_{i}')
   production_schedle.append([NrProduct, quantity, day])

示例逻辑 #

若产品0的生产计划为[[0,45,1], [0,150,3]]，结合其订单[[25,0],[75,2],[15,3]]，需输出包含延迟明细与剩余库存的结果：

delay_list=[[
[25,1], #[数量,延迟/提前天数]，此处延迟1天
[20,-1], #此处提前1天
[55,1],
[15,0]],
[80]] #剩余库存数量（可设置不同售价）

问题解答 #

1. 是否有其他集成延迟的思路？OR-Tools已有相关函数？ #

OR-Tools CP-SAT没有专门的「延迟计算」函数，但可以通过基础建模逻辑实现更高效的延迟集成，推荐以下思路：

• 库存+时间维度追踪：为每个产品按天创建库存变量，关联生产入库与订单出库，通过实际交付日（库存满足订单的日期）与期望日的差值计算延迟。这种方式贴合CP-SAT的变量约束体系，能直接把延迟与利润目标绑定。
• 分段线性利润映射：将延迟天数对应的单价转化为分段线性函数，直接作为目标函数的一部分。CP-SAT支持用AddPiecewiseLinearConstraint或分段逻辑定义目标，简化利润计算的约束复杂度。
• 订单级延迟变量：为每个订单创建实际交付日变量，通过约束确保交付发生在库存足够的日期，再直接计算交付日与期望日的差值作为延迟变量，关联售价计算利润。

2. 如何按上述思路让OR-Tools返回延迟列表？ #

需分建模和结果提取两个阶段实现：

阶段1：建模关联生产、库存与订单

• 为每个产品按天定义库存变量：inventory[p][d]，表示产品p在第d天结束时的库存，初始库存设为0。
• 添加库存流转约束：

  # 假设最大天数为30
  max_day = 30
  for p in order_per_product.keys():
      # 第一天库存 = 当天生产数量 - 当天订单需求
      solver.Add(inventory[p][0] == sum(prod[1] for prod in production_schedle if prod[0] == p and prod[2] == 0) - sum(order[0] for order in order_per_product[p] if order[1] == 0))
      # 后续天数库存 = 前一天库存 + 当天生产 - 当天订单
      for d in range(1, max_day+1):
          solver.Add(inventory[p][d] == inventory[p][d-1] + sum(prod[1] for prod in production_schedle if prod[0] == p and prod[2] == d) - sum(order[0] for order in order_per_product[p] if order[1] == d))
      # 库存非负约束
      for d in range(max_day+1):
          solver.Add(inventory[p][d] >= 0)
  

• 为每个订单的实际交付逻辑添加约束（可选，用于直接追踪交付日）：比如对每个订单，定义actual_delivery[order_idx]，约束当库存累计到足够覆盖订单数量时，交付日为对应天数。

阶段2：求解后提取并计算延迟列表

求解完成后，先提取生产计划的实际值，再按时间顺序匹配订单需求计算延迟：

def get_delay_list(solution, production_schedle, order_per_product):
    # 提取生产计划的实际值
    actual_production = []
    for prod in production_schedle:
        p = solution.Value(prod[0])
        qty = solution.Value(prod[1])
        day = solution.Value(prod[2])
        if qty > 0:  # 过滤未执行的批次
            actual_production.append([p, qty, day])
    
    delay_result = {}
    for product, orders in order_per_product.items():
        # 按生产日排序该产品的生产批次
        sorted_prods = sorted([p for p in actual_production if p[0] == product], key=lambda x: x[2])
        # 复制订单避免修改原数据
        remaining_orders = [order.copy() for order in orders]
        delays = []
        remaining_inventory = 0
        
        for prod_qty, prod_day in [(p[1], p[2]) for p in sorted_prods]:
            available = prod_qty + remaining_inventory
            remaining_inventory = 0
            
            while available > 0 and remaining_orders:
                order_qty, order_day = remaining_orders[0]
                if available >= order_qty:
                    # 完全覆盖当前订单
                    delay = prod_day - order_day
                    delays.append([order_qty, delay])
                    available -= order_qty
                    remaining_orders.pop(0)
                else:
                    # 部分覆盖当前订单
                    delay = prod_day - order_day
                    delays.append([available, delay])
                    remaining_orders[0][0] -= available
                    available = 0
            
            # 剩余库存结转
            if available > 0:
                remaining_inventory = available
        
        delay_result[product] = [delays, remaining_inventory]
    return delay_result

关键注意事项

• 建模时需确保生产批次变量的取值范围合理，避免出现无效解。
• 提取变量值时必须调用solution.Value(var)获取实际求解结果。
• 若订单存在多个可能的交付时间点，可通过约束优先匹配最早能满足库存的日期，或结合利润目标自动选择最优交付时机。

内容的提问来源于stack exchange，提问作者Vincente