如何解决产品至装配线的分配问题（求可行方案）

• N条装配线，容量分别为C₁、C₂……Cₙ
• M个产品P₁、P₂……Pₘ，每个产品对应一个有限Item集合{I₁、I₂……Iₖ}，产品间可共享Item

约束条件：

1. 每个产品必须分配至恰好一条装配线
2. 每条装配线分配的所有产品对应的去重后Item总数不得超过其容量

已尝试方案（未得到可行解） #

• 优先分配杰卡德相似度高的产品对至装配线，再补充其他产品
• 通过LSH Min Hash生成高相似度产品桶后分配

以上两种方法均无法完成全部分配，仍有部分产品无法适配任何装配线。

可行次优方案思路 #

1. 按产品Item规模从大到小的贪心策略 #

• 先计算每个产品的Item集合大小size(Pᵢ)，将产品按size(Pᵢ)降序排序
• 优先处理大产品：遍历所有装配线，找到剩余容量≥当前产品Item数且加入后剩余容量最优（可选剩余最大/最小，两种策略都可尝试）的装配线，分配该产品并更新装配线的已用容量（即已分配产品去重Item集合与当前产品Item集合合并后的大小）
• 处理完小产品后，对未分配产品逐一尝试插入到各装配线，若加入后去重Item总数不超过容量则分配；若无法插入，尝试调整已分配产品（如将某线中与其他线重叠多的产品移走，腾出空间）

2. 按装配线容量从大到小的贪心策略 #

• 将装配线按容量降序排序
• 对每条装配线，优先选择与已分配产品Item重叠最多的产品（这样新增Item数最少），计算合并后的去重Item总数是否≤容量，满足则加入；重复此过程直到无法再加入任何产品，再处理下一条线
• 最后对剩余产品，尝试插入到各线剩余空间，或调整已分配产品组合

3. 随机分配+迭代调整的启发式方法 #

• 先随机将所有产品分配到各装配线（暂不考虑容量约束）
• 计算每条线的超容量值（去重Item数 - 容量，正数为超量）
• 对超容量的线，逐步移除产品：优先移除那些在其他线中Item重叠最多的产品（移到其他线时新增Item数最少），直到该线满足容量约束
• 重复上述调整过程，直到所有线都符合约束；若仍有未分配产品，再单独寻找可容纳的装配线

4. 基于增量Item数的贪心匹配 #

• 对每个产品，预计算它加入到各装配线时会新增的Item数（即该产品Item集合减去目标线已有的Item集合的大小）
• 每次选择新增Item数最少的产品-装配线组合进行分配，更新对应装配线的已用容量；重复直到所有产品分配完成

5. 元启发式方法（模拟退火/遗传算法） #

模拟退火

• 初始状态：随机生成一个全部分配的方案
• 邻域操作：随机交换两个产品的装配线，或把一个产品移到另一条线
• 接受准则：计算操作后的总超容量（所有线超量之和），若更优则直接接受；若更差，按当前温度对应的概率接受（温度越高，接受差解的概率越高）
• 逐步降低温度，直到收敛到可行解

遗传算法

• 编码：每个个体代表一个分配方案（每个产品对应一条装配线）
• 适应度函数：总超容量的负数（超容量越小，适应度越高）
• 进化操作：选择适应度高的个体进行交叉（交换部分产品的分配）、变异（随机修改单个产品的分配线）
• 迭代多代，直到找到可行解

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