如何使用PuLP构建含清洁时间约束的订单-机器分配线性规划模型

问题背景 #

需按顺序处理一系列订单，每个订单包含若干可由多台机器加工的物品，需构建LP模型并通过PuLP实现，核心要求如下：

• 约束条件：
  • 每台机器每订单仅能加工一个物品
  • 每个订单的每个物品至少由一台机器加工
• 目标：最小化总运行时间，总运行时间包含物品固定运行时间，以及机器加工不同物品时的清洁时间

给定数据 #

1. 订单-物品-机器可分配关系 #

仅表格内的组合允许分配：

order item machine
1     A      1
1     A      2
1     B      1
1     B      2
2     A      1
2     A      2
2     D      1
2     D      2 
3     E      1
3     E      2

2. 物品固定运行时间表 #

item runtime      
A    50
B    60
C    70
D    80
E    90

3. 物品转换清洁时间表 #

行代表当前加工物品，列代表前一个加工物品，单元格值为所需清洁时间：

prev item
         A B C D E
curr   A 0 0 1 1 2
item   B 0 0 2 1 0
       C 0 0 0 1 1
       D 0 0 0 0 1
       E 1 0 0 0 0

示例：若机器1先加工物品A，再加工物品E，需额外增加2秒清洁时间

建模疑问与验证 #

用户自行简化建模后提出以下问题：

请问以下模型是否覆盖所有约束？另外，如何不使用min函数构建清洁时间约束？

用户提出的模型公式 #

Variables:
A(oim) - 订单o、物品i、机器m的分配变量（二进制）
D(oim) - 订单o、物品i、机器m的加工时长
D(oi) - 订单o、物品i的加工时长
C(oim) - 订单o、物品i、机器m的清洁时间

Constants:
R(oi) - 订单o中物品i的固定运行时间
C(xy) - 从物品x转换到物品y的固定清洁时间
M - 远大于总运行时间的大M值

Formulation:
min sum( D(oim) + C(oim) )
s.t. 
1. D(oim) ≤ M * A(oim)  （所有o,i,m）
2. sum( A(oim) ) ≥ 1  （所有o,i）—— 注：是否因时长约束而冗余？
3. sum( D(oim) ) = R(oi)  （所有o,i）
4. M * A(oim) - D(oi) + D(oim) ≤ M  （所有o,i,m）
5. M * A(oim) + D(oi) - D(oim) ≤ M  （所有o,i,m）
6. sum( A(oim) ) ≤ 1  （所有o,m）
7. C(xy) * min(A(-oim),A(oim)) ≤ C(oim)  （所有o,i,m，其中A(-oim)为机器m上的前一订单分配变量）

模型验证与优化建议 #

1. 约束覆盖情况检查 #

• 约束6：sum(A(oim)) ≤1（所有o,m）—— 正确覆盖「每台机器每订单仅能加工一个物品」的要求，同一订单、机器下最多分配一个物品。
• 约束2：sum(A(oim)) ≥1（所有o,i）—— 并非冗余，约束3要求sum(D(oim))=R(oi)，但LP求解时变量可能出现松弛，必须显式约束确保至少有一台机器分配该物品，避免出现无分配但凑出时长的不合理情况。
• 约束3、4、5：逻辑存在矛盾，物品固定运行时间是每台加工该物品的机器都要消耗对应时长，而非所有机器加工时长总和等于固定值。且D(oi)变量属于冗余，可直接通过分配变量关联固定时长。
• 约束7：min函数是非线性表达式，无法直接用于LP模型，必须进行线性化改造。

2. 清洁时间约束的线性化方案 #

通过引入辅助二进制变量消除min函数，核心思路是直接表示「机器连续加工两个物品」的状态：

• 定义变量：
  • assign(o, i, m)：二进制变量，1表示订单o的物品i分配给机器m加工（等价于A(oim)）
  • trans(m, o_prev, o_curr, x, y)：二进制变量，1表示机器m在订单o_prev加工物品x，在后续订单o_curr加工物品y（仅当o_curr = o_prev +1时生效，因为订单按顺序处理）
• 添加约束：
  1. 对于所有机器m、订单o（o>1）、物品x、y：trans(m, o-1, o, x, y) ≤ assign(o-1, x, m)
  2. 对于所有机器m、订单o（o>1）、物品x、y：trans(m, o-1, o, x, y) ≤ assign(o, y, m)
  3. 对于所有机器m、订单o（o>1）、物品y：sum(x, trans(m, o-1, o, x, y)) = assign(o, y, m)
• 清洁时间计算：总清洁时间为sum(m, o>1, x, y) C(x,y)*trans(m, o-1, o, x, y)，无需额外C(oim)变量。

3. 简化后的模型变量与约束建议 #

变量

• assign(o, i, m)：二进制变量，仅允许数据中存在的订单-物品-机器组合取值
• trans(m, o_prev, o_curr, x, y)：二进制变量，仅允许相邻订单、且x/y属于对应订单可加工物品的组合取值

约束

1. 每台机器每订单仅加工一个物品：sum(i, assign(o,i,m)) ≤ 1（所有订单o、机器m）
2. 每个订单的每个物品至少分配一台机器：sum(m, assign(o,i,m)) ≥ 1（所有订单o、物品i）
3. 转换变量与分配变量关联：
   • trans(m, o-1, o, x, y) ≤ assign(o-1, x, m)（所有机器m、订单o>1、物品x,y）
   • trans(m, o-1, o, x, y) ≤ assign(o, y, m)（所有机器m、订单o>1、物品x,y）
   • sum(x, trans(m, o-1, o, x, y)) = assign(o, y, m)（所有机器m、订单o>1、物品y）
4. 分配可行性约束：若订单o的物品i不能分配给机器m，则assign(o,i,m) = 0

目标函数

minimize (sum(o,i,m) assign(o,i,m)*R(i)) + (sum(m,o>1,x,y) trans(m,o-1,o,x,y)*C(x,y))

其中：

• R(i)为物品i的固定运行时间
• C(x,y)为从物品x转换到y的清洁时间

PuLP实现步骤概要 #

1. 导入PuLP库：import pulp
2. 创建LP问题实例：prob = pulp.LpProblem("OrderProcessingLP", pulp.LpMinimize)
3. 定义变量：
   • 基于允许的组合创建assign二进制变量
   • 基于相邻订单的允许物品组合创建trans二进制变量
4. 添加目标函数：按照上述简化后的目标函数添加
5. 添加约束：依次添加上述4类约束
6. 求解模型：prob.solve(pulp.PULP_CBC_CMD(msg=0))
7. 输出结果：打印分配变量、转换变量的取值，以及总运行时间

内容的提问来源于stack exchange，提问作者J. Doe