双行布局问题的分解策略及启发式求解方法

为克服现有方法在求解大规模双行布局问题时存在的计算时间长、性能不稳定等问题,提出了结合问题特征的分解策略,将大规模双行布局问题分解为较易求解的组合优化问题与线性规划问题两个子问题,并分别建立了相应的数学模型。提出了3种基于不同优先规则的启发式求解方法,该方法的特征是机器成对分配,且结合了线性规划法。对大量不同规模(6～36台机器)的测试问题进行了验算与对比。试验结果表明,所提启发式方法尤其是其中的heuristic3启发式方法,能快速有效地求解双行布局问题,与现有方法相比,在运行效率和求解偏差上具有优势。