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

来源：计算机集成制造系统杂志2014年第3期北京时间：

作者：张则强,程文明

单位：西南交通大学机械工程学院

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

关键词：双行布局问题,设施布局,问题分解,启发式方法,线性规划

基金资助：国家自然科学基金资助项目(51205328);高等学校博士学科点专项科研基金资助项目(200806131014);教育部人文社会科学研究青年基金资助项目(12YJCZH296);中央高校基本科研业务费专项资金资助项目(SWJTU09CX022)。