结合启发式算法与改进整数线性规划的有序逃逸布线
来源:计算机集成制造系统杂志2024年第12期北京时间:
作者:邓新国, 叶似锦, 陈家瑞
单位:1.福州大学计算机与大数据学院2.锐捷网络股份有限公司
摘要:在印刷电路板布线中,逃逸布线是重要的组成部分。随着器件引脚数量不断增加,引脚阵列规模不断扩大,有序逃逸布线问题变得愈发复杂。针对目前有序逃逸布线研究中布线时间与质量无法兼顾的问题,提出一种结合启发式算法与改进整数线性规划的布线方案。该方案分为构建初始解与拆线重布二个阶段。在第一个阶段,先利用最长公共子序列给出逃逸引脚初步布线顺序,接着利用分段代价预估函数的启发式算法,在短时间内对大部分引脚进行预布线。在第二个阶段,首先确定子图范围,然后给出改进的整数线性规划表达式,在初始布线的基础上进行拆线重布,提高布通率的同时达到局部最优。最后再使用最短路径算法进行拆线重布,进一步提高总体布通率。实验结果表明,提出的布线方案能够在较短的时间内得到最优或近似最优的布线结果,相较于使用整数线性规划方案来进行布线,CPU时间平均减少35.57%。
关键词:启发式算法,整数线性规划,有序逃逸布线,拆线重布,最短路径
基金资助:国家自然科学基金资助项目(61977017);中国福建光电信息科学与技术创新实验室(闽都创新实验室)基金(2021ZR142)。
2024年12期其他文献查阅:
人机混合智能驱动的产品创新设计评价决策研究进展及发展趋势
高维混合不确定条件下基于降维积分的产品关键结构可靠性优化设计
基于Petri网的动态可重构离散事件系统重构方案设计
面向人本智造的工业外骨骼:挑战、进展和展望
离散制造生产线可配置数字孪生数据系统设计
基于图像增强和自适应阈值的语义视觉SLAM系统
基于3D点云边界点特征的航空叶片位姿识别
基于区域的弱纹理零件三维跟踪方法
三维测量中面结构光视点简化与机械臂路径优化方法
基于地图像素化的改进快速搜索随机树机械臂运动规划
基于人工势场DDPG算法的移动机械臂协同避障轨迹规划
基于改进金枪鱼群算法的机械臂时间最优轨迹规划
结合启发式算法与改进整数线性规划的有序逃逸布线
基于知识驱动的航天复杂产品装配工艺重构方法
基于CWOA算法的激光熔覆工艺参数优化方法
基于递归分析和机器学习的小批量机械加工过程状态监测
考虑外协的作业车间无拖期调度问题多目标差分进化算法
考虑工人协作与学习效应的柔性作业车间调度
考虑生产与运输成本的准时制分布式预制构件生产调度
拖车式自动导引车系统通行顺序优化方法
基于改进VNDS算法的并行机批量流调度
基于VGG16-SVM-SSA的产品表面质量检测方法
基于工业算力网络的算力接入服务器部署算法
面向工业流程异常检测的均衡循环神经网络
基于数字孪生的塔式起重机结构性能在线监测方法
基于两阶段Gamma过程的工业机器人可靠性评估
基于多指标加权的滚动轴承故障特征选择方法
融合多传感器数据的系统相对密度高维核估计剩余寿命预测
能力受限下制造服务组合的多目标优化方法
面向云制造服务商选择的多源异构时序信息评价方法