文件名称：分析 ATO 系统的原始对偶方法-研究论文
文件大小：654KB
文件格式：PDF
更新时间：2024-06-29 10:30:15
论文研究
我们从文献中研究按订单组装 (ATO) 问题。 众所周知，具有一般结构和完整性约束的 ATO 问题很难解决，我们通过原始对偶分析和线性规划 (LP) 舍入建立最坏情况近似保证，从而为这些问题提供了新的见解。 首先，我们使用自然报文供应商分解来放松单周期 ATO 问题，并使用对偶解决方案进行放松以推导出最优成本的下限，提供随着系统中最大产品尺寸而增长的严格近似保证。 然后，我们提出了一种 LP 舍入算法，该算法在需求变大时实现渐近最优性，并为任何问题实例实现 1.8 的近似因子。 除了理论保证外，我们还进行了全面的数值模拟，发现我们的舍入算法优于现有技术并且接近最优。 最后，我们证明了我们的单周期 LP 舍入结果可用于为具有积压和相同组件提前期的动态 ATO 问题开发渐近最优积分策略。