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

Decomposition strategies and heuristic for double row layout problem

作　　者：张则强[1] 程文明[1] 

机构地区：[1]西南交通大学机械工程学院,四川成都610031

出　　处：《计算机集成制造系统》2014年第3期559-568,共10页Computer Integrated Manufacturing Systems

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

摘　　要：为克服现有方法在求解大规模双行布局问题时存在的计算时间长、性能不稳定等问题,提出了结合问题特征的分解策略,将大规模双行布局问题分解为较易求解的组合优化问题与线性规划问题两个子问题,并分别建立了相应的数学模型.提出了3种基于不同优先规则的启发式求解方法,该方法的特征是机器成对分配,且结合了线性规划法.对大量不同规模（6～36台机器）的测试问题进行了验算与对比.试验结果表明,所提启发式方法尤其是其中的heuristic3启发式方法,能快速有效地求解双行布局问题,与现有方法相比,在运行效率和求解偏差上具有优势.To overcome the disadvantages such as long computing time and unstable performance of traditional algorithms in solving large-scale Double Row Layout Problem （DRLP）,the decomposition strategies was proposed.DRLP was decomposed into two sub-problems of combinatorial optimization problem and linear problem,and the corresponding mathematical models were presented respectively.Three types of heuristic solving methods were proposed based on different precedence rules,whose characteristics were integrated with linear programming and distributed in pairs.A series of numerical experiments based on differently sized test problems （from 6 to 36 machines）were conducted,and the computational results showed that the proposed methods,especially the heuristic3 method could solve the double row layout problem effectively.It had good performance in running efficiency and solving gap compared to the existing methods.

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

分 类 号：TH165[机械工程—机械制造及自动化] TP301.6[自动化与计算机技术—计算机系统结构]