生产订单排程方案咨询：递归算法VS背包算法？

你遇到的产线过载问题，核心原因是贪心递归（逐优先级顺序分配）只追求局部最优——简单的UNION ALL递归会按优先级把订单挨个往当前产线塞，直到触发数量或工时限制才切换到下一条产线，但这种策略完全没考虑全局的资源适配性，比如B0029003（BikeG）明明可以分配到支持BikeG的Line4，却可能因为前面的产线被低优先级订单塞满过载，导致它被错误分配。

结论：确实需要改用多约束背包算法 #

你的场景属于双约束的0-1背包问题变种（每个订单是一个"物品"，产线的150件数量和8工时是两个"背包容量"，优先级是物品的"价值"），目标是在不超过两个容量的前提下，为每条产线选择价值（优先级）最高的订单组合，实现全局最优的分配，避免产线过载。

实现思路 #

1. 预处理订单与产线映射：基于#priorityOrders表，为每个产品明确可分配的产线优先级排序，确保高优先级的产线优先被考虑；
2. 动态规划（DP）实现多约束背包：
   • 对每条产线，初始化一个二维DP数组dp[qty][hour]，记录达到该数量和工时组合时，已分配订单的最高优先级总和；
   • 遍历所有可分配给该产线的订单，更新DP数组，确保每个状态都保留最优的订单组合；
   • 回溯DP数组，得到该产线可容纳的最优订单集合，标记为"合规（状态1）"；
3. 处理剩余订单：所有产线分配完成后，未被选中的订单标记为"超限（状态2）"。

测试SQL代码 #

declare @Linelimit int; 
declare @WorkingTime int; 
set @Linelimit = 150; 
set @WorkingTime = 8; 

drop table if exists #avaliableOrders 
create table #avaliableOrders ( 
    Batch nvarchar(50), 
    Product nvarchar(50), 
    Qty int, 
    HourTarget decimal(4,2) 
); 

insert into #avaliableOrders(Batch,Product,Qty,HourTarget) 
values 
('B002801','BikeA','20','0.69'), 
('B002801','BikeA','1','0.03'), 
('B002801','BikeA','1','0.03'), 
('B002801','BikeA','7','0.24'), 
('B002804','BikeA','1','0.03'), 
('B002804','BikeA','3','0.1'), 
('B0028010','BikeA','20','0.69'), 
('B0028010','BikeA','1','0.03'), 
('B0028010','BikeA','4','0.14'), 
('B0028010','BikeA','2','0.07'), 
('B0028010','BikeA','3','0.1'), 
('B0028010','BikeA','1','0.03'), 
('B0028010','BikeA','13','0.45'), 
('B0029002','BikeA','2','0.07'), 
('B0029002','BikeA','3','0.1'), 
('B0029002','BikeA','1','0.03'), 
('B0029002','BikeA','7','0.24'), 
('B0029002','BikeA','9','0.31'), 
('B0029002','BikeA','1','0.03'), 
('B0029002','BikeA','3','0.1'), 
('B002802','BikeB','30','0.68'), 
('B002802','BikeB','1','0.02'), 
('B002803','BikeC','2','0.05'), 
('B002803','BikeC','580','13.18'), 
('B002805','BikeD','24','0.49'), 
('B002805','BikeD','120','2.45'), 
('B002806','BikeE','3','0.17'), 
('B002806','BikeE','1','0.06'), 
('B002807','BikeE','1','0.06'), 
('B002808','BikeF','244','13.56'), 
('B002809','BikeF','10','0.56'), 
('B0029001','BikeG','2','0.05'), 
('B0029001','BikeG','2','0.05'), 
('B0029001','BikeG','1','0.03'), 
('B0029001','BikeG','6','0.16'), 
('B0029001','BikeG','10','0.27'), 
('B0029001','BikeG','2','0.05'), 
('B0029001','BikeG','24','0.65'), 
('B0029001','BikeG','40','1.08'), 
('B0029001','BikeG','6','0.16'), 
('B0029001','BikeG','1','0.03'), 
('B0029001','BikeG','15','0.41'), 
('B0029003','BikeG','3','0.08'), 
('B0029003','BikeG','3','0.08'), 
('B0029003','BikeG','3','0.08'), 
('B0029003','BikeG','50','1.35'), 
('B0029003','BikeG','2','0.05'), 
('B0029003','BikeG','1','0.03'), 
('B0029003','BikeG','1','0.03'), 
('B0029003','BikeG','1','0.03'), 
('B0029003','BikeG','1','0.03'), 
('B0029003','BikeG','1','0.03'), 
('B0029003','BikeG','50','1.35'), 
('B0029003','BikeG','2','0.05'), 
('B0029003','BikeG','2','0.05'), 
('B0029003','BikeG','10','0.27'), 
('B0029003','BikeG','2','0.05'), 
('B0029003','BikeG','1','0.03'), 
('B0029003','BikeG','3','0.08'), 
('B0029003','BikeG','4','0.11'), 
('B0029003','BikeG','1','0.03'), 
('B0029003','BikeG','1','0.03'), 
('B0029003','BikeG','12','0.32');

create table #priorityOrders ( 
    Product nvarchar(50), 
    Line nvarchar(50), 
    Priority int 
); 

insert into #priorityOrders(Product,Line,Priority) 
values 
('Line1','BikeA','1'), 
('Line1','BikeB','2'), 
('Line1','BikeC','3'), 
('Line1','BikeG','4'), 
('Line2','BikeD','1'), 
('Line2','BikeF','2'), 
('Line2','BikeB','3'), 
('Line3','BikeE','1'), 
('Line3','BikeC','2'), 
('Line3','BikeA','3'), 
('Line4','BikeB','1'), 
('Line4','BikeH','3'), 
('Line4','BikeF','4'), 
('Line4','BikeG','4');

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