Google OR Tools求解大规模FJSSP的可行性探究

10×10 规模场景 #

• 可扩展性：这类小规模问题对绝大多数实现（哪怕是基础启发式算法）都完全适配，无论是精确算法（如分支定界）还是元启发式算法（遗传、蚁群等），都不会出现内存或算力瓶颈，能稳定输出结果。
• 求解耗时：精确算法几秒到几十秒就能得到最优解；元启发式算法毫秒级就能生成可行解，收敛到最优解也不会超过1分钟，完全能在你要求的时间范围内完成。

100×100 规模场景 #

• 可扩展性：这属于大规模复杂调度问题，精确算法会因组合爆炸直接失效，必须依赖优化后的元启发式或混合算法。如果你的代码是基础实现，可能会出现内存占用飙升、迭代效率骤降的情况；但如果做了关键优化（比如紧凑的工序-机器编码、并行化种群更新、剪枝无效解），就能较好适配这个规模。
• 求解耗时：
  • 基础元启发式实现：可能需要30分钟以上才能得到较优解，很难在10-15分钟内达到可接受的解质量。
  • 优化后的实现：若加入并行计算（多线程处理种群个体）、启发式剪枝、自适应参数调整等优化，大概率能在10-15分钟内输出符合工业要求的次优解；要是用GPU加速或更高效的混合算法框架（如禁忌搜索+遗传算法），耗时还能进一步压缩。

关键影响因素 #

• 算法类型：精确算法仅适用于小规模场景，大规模必须用元启发式或混合算法。
• 代码优化：编码方式的紧凑性、局部搜索策略的有效性、并行化程度，直接决定了求解性能。
• 解质量要求：仅需可行解时耗时会大幅缩短；若追求接近最优解，耗时会显著增加。

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