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

摘要：

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

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

所属期刊栏目：20

分类号：TH165;TP301.6

资助基金：国家自然科学基金资助项目51205328;高等学校博士学科点专项科研基金资助项目200806131014;教育部人文社会科学研究青年基金资助项目12YJCZH296;中央高校基本科研业务费专项资金资助项目SWJTU09CX022.Project supported by the National Natural Science Foundation,China51205328;the Specialized Research Fund for Doctoral Program of Higher Education,China200806131014;the Youth Foundation for Humanities and Social Sciences of Ministry of Education,China12YJCZH296;the Fundamental Research Funds for the Central Universities,ChinaSWJTU09CX022

在线出版日期：2014-05-05（万方平台首次上网日期，不代表论文的发表时间）

页数：共10页

页码：559-568