检索结果-内蒙古大学图书馆

Two stage Ordered Escape Routing combined with LP and heuristic algorithm for large scaled PCB

INTEGRATION-THE VLSI JOURNAL 2025年 100卷

作者： Lin, Disi Chen, Chuandong Wei, Rongshan Liu, Qinghai He, Huan Zhu, Ziran Lin, Zhifeng Chen, Jianli Fuzhou Univ Coll Comp & Data Sci Fuzhou 350108 Peoples R China Fuzhou Univ Sch Microelect Fuzhou 350108 Peoples R China Fuzhou Univ Ctr Appl Math Fujian Prov Fujian Sci & Technol Innovat Lab Optoelect Informa Fuzhou 350108 Peoples R China Fuzhou Univ Ctr Discrete Math Fuzhou 350108 Peoples R China Hangzhou Huawei Enterprises Telecommun Technol Co Hangzhou 310000 Peoples R China Southeast Univ Natl ASIC Syst Engn Ctr Nanjing 210096 Peoples R China Fuzhou Univ Ctr Discrete Math & Theoret Comp Sci Fuzhou 350108 Peoples R China Fudan Univ Sch Microelect Shanghai 200433 Peoples R China

The Ordered Escape Routing (OER) problem, which is an NP-hard problem, is critical to PCB design. Primary methods based on integer linear programming (ILP) work well on small-scale PCBs with fewer pins. However, when dealing with large-scale instances, traditional ILP strategies frequently cause time violations as the number of variables increases due to time-consuming preprocessing. In addition, heuristic algorithms have a time advantage when dealing with specific problems. In this paper, We propose an efficient two-stage escape routing method that employs LP for global routing and uses a heuristic algorithm to deal with the path intersection problem to minimize wiring length and runtime for large-scale PCBs. We first model the OER problem as a min-cost multi-commodity flow problem and use ILP to solve it. Then, we relax the non-crossing constraints and transform the ILP model into an LP model to reduce the runtime. we also construct a crossing graph according to the intersection of routing paths and propose a heuristic algorithm to locate congestion quickly. Finally, we reduce the local area capacity and allow global automatic congestion optimization. Compared with the state-of-the-art work, experimental results show that our method can reduce the routing time by 60% and handle larger-scale PCB escape routing problems.

关键词： Ordered escape routing Min-cost multi-commodity flow Linear programming heuristic algorithm

来源：评论

学校读者我要写书评

暂无评论

Formulating capstone project groups using lexicographical analysis and heuristic algorithm

引用

ALEXANDRIA ENGINEERING JOURNAL 2025年 115卷 334-342页

作者： Albashabsheh, Nibal T. Almasarwah, Najat Shbool, Mohammad A. Eltoukhy, Mohamed Meselhy Univ Jordan Dept Ind Engn Amman Jordan Mutah Univ Dept Ind Syst Engn Alkarak Jordan Amer Univ Bahrain Coll Engn & Comp Ind Engn Riffa Bahrain Univ Jeddah Coll Comp & Informat Technol Khulais Dept Informat Technol Jeddah Saudi Arabia

Capstone design course prepares students for career advancement and professional practice, where it mainly focuses on collaborative team settings. One of the main challenges facing the capstone design course is grouping the students into teams based on their professional and assigning the formulated groups to faculty members based on their preferences and teaching load. This study uses lexicographical analysis and a heuristic algorithm to handle this challenge, considering two performance measures: the students' and faculty members' satisfaction levels. The lexicographical analysis is an approach that prioritizes multiple performance measures in a strict hierarchical order. Meanwhile, the heuristic algorithm is used to find the near optimal solution. The students' satisfaction levels are measured based on their preferences, which are determined based on grade point average (GPA). On the other hand, the faculty member satisfaction levels are estimated based on the value of the overload resulting from assigning the capstone course students to faculty members. The results conclude that the propounded lexicographical analysis could be utilized when the faculty member satisfaction levels have more weight than the students' satisfaction levels. Meanwhile, the proposed heuristic algorithm could be applied when the students' satisfaction levels are more important than the faculty members' satisfaction levels.

关键词： Lexicographical analysis Capstone design course heuristic algorithm Student satisfaction level Faculty member satisfaction level

来源：评论

学校读者我要写书评

暂无评论

An adaptive heuristic algorithm with a collaborative search framework for multi-UAV inspection planning

引用

APPLIED SOFT COMPUTING 2025年 174卷

作者： He, Chang Ouyang, Haibin Huang, Weiqing Li, Steven Zhang, Chunliang Ding, Weiping Zhan, Zhi-Hui Guangzhou Univ Sch Mech & Elect Engn Guangzhou 510006 Peoples R China Guangzhou Univ Guangzhou Key Lab Condit Monitoring & Control Mech Guangzhou 510006 Peoples R China RMIT Univ Grad Sch Business & Law Melbourne 3000 Australia Nantong Univ Sch Artificial Intelligence & Comp Sci Nantong 226019 Peoples R China Nankai Univ Coll Artificial Intelligence Tianjin 300350 Peoples R China

Multi-UAV inspection path planning has become an important research topic for completing inspection tasks before the data acquisition deadline. In this study, we propose an adaptive heuristic algorithm with a collaborative search framework named Sa-VCO to solve the multi-UAV inspection path planning problem. Our study includes three main novelties. First, we design a region-gridding disperse approach that transforms the primitive target regions into a set of standard target subregions, allowing the target regions with greater costs to be inspected by multiple UAVs. Second, we propose an adaptive initial solution generation strategy using the information of graph structure constructed by all targets to reduce redundant computing. Third, we established a collaborative search framework to enhance search efficiency and increase population diversity. A large number of multiple-perspective comparative experiments are provided to test Sa-VCO's performance, and the comparison results demonstrate that Sa-VCO achieves better results than other advanced algorithms, especially on large-scale data sets.

关键词： heuristic algorithm Adaptive initialization strategy Collaborative search framework UAV path planning

来源：评论

学校读者我要写书评

暂无评论

A heuristic algorithm for rainbow matchings and its application in rainbow Ramsey number for matchings

引用

DISCRETE APPLIED MATHEMATICS 2025年 368卷 153-161页

作者： Jin, Zemin Zhejiang Normal Univ Sch Math Sci Jinhua 321004 Peoples R China

It is well known that a maximum matching in a given graph can be found in polynomial time. The maximum rainbow matching problem is to find a rainbow matching of maximum size in an edge-colored graph. This problem is equivalent to the multiple choice matching problem which is NP-Complete. Moreover, it is surprising that the rainbow matching problem is even APX-Complete for paths. So far, there is few efficient algorithm for rainbow matchings. The only positive result is to reduce it to the maximum independent sets in K-1,K-4-free graphs, which can be approximated by a polynomial algorithm with approximation ratio 2/3-& varepsilon;for every & varepsilon;>0. In this paper, we give a heuristic polynomial algorithm to find a large rainbow matching in an edge-colored K-n. For any given integer k, we can find either a rainbow kK(2), or a Kn-3i with at most k-i-1 colors for some 0 <= i <= k-2. It is interesting that our result is useful for the existence of a monochromatic G against a rainbow matching in Kn. We give applications of the algorithm and, based on it, we generalize the previous results about the rainbow Ramsey number for matchings. (c) 2025 Elsevier B.V. All rights are reserved, including those for text and data mining, AI training, and similar technologies.

关键词： heuristic algorithm Rainbow matching Rainbow Ramsey number

来源：评论

学校读者我要写书评

暂无评论

Finite Potential Game heuristic algorithm for Workload Allocation in Dual-Gantry Placement Machines

引用

IEEE TRANSACTIONS ON INDUSTRIAL INFORMATICS 2025年第3期21卷 2064-2073页

作者： Pi, Qiqi Yu, Jinyong Sun, Hao Yu, Xinghu Li, Zhengkai Qiu, Jianbin Rodriguez-Andina, Juan Gao, Huijun Harbin Inst Technol Res Inst Intelligent Control & Syst Harbin 150001 Peoples R China Yongjiang Lab Res Ctr Intelligent Control & Syst Ningbo 315202 Peoples R China Ningbo Yitang Intelligent Technol Co Ltd Ningbo 315202 Peoples R China Yongjiang Lab Intelligent Control & Syst Res Ctr Ningbo 315202 Peoples R China Ningbo Inst Intelligent Equipment Technol Co Ltd Ningbo 315201 Peoples R China Ningbo Univ Technol Res Inst Interdisciplinary Intelligent Sci Ningbo 315211 Peoples R China Univ Vigo Dept Elect Technol Vigo 36310 Spain Ningbo Univ Technol Ningbo 315211 Peoples R China

Dual-gantry surface mount optimization effectively improves the productivity of printed circuit board assembly (PCBA), but also brings new challenges. Optimizing workload allocation to balance the front and rear gantry placement completion time is a significant challenge for improving PCBA productivity. This study proposes a finite potential game heuristic algorithm (FPGHA) to solve the workload allocation problem. The algorithm generates game agents by analyzing the feeding characteristics of the dual-gantry placement machine and using an improved bisection K-means clustering method. Agent utility is calculated based on metrics affecting productivity of the pick-and-place process, including the number of simultaneous pickups, nozzle changes, cycles, and mounting points. Nash equilibrium of FPGHA is obtained by a best-response dynamics and heuristic algorithm. Then, the effectiveness of FPGHA in solving the workload allocation problem is first demonstrated in simulated experiments with different nozzle and feeder configurations. Finally, FPGHA is compared with the hierarchical restricted balance algorithm, adaptive clustering algorithm, and the popular industrial optimizer software in actual placement experiments using real-world industrial printed circuit boards. The effectiveness and accuracy of FPGHA are verified by analyzing the correlation between three variables: The FPGHA estimated value, the actual assembly value, and the PCB assembly time.

关键词： Dual-gantry placement machine finite potential game heuristic algorithm workload allocation Dual-gantry placement machine finite potential game heuristic algorithm workload allocation

来源：评论

学校读者我要写书评

暂无评论

A New heuristic algorithm for Student-Project Allocation with Lecturer Preferences and Ties

引用

ASIA-PACIFIC JOURNAL OF OPERATIONAL RESEARCH 2025年

作者： Nguyen, Uyen T. Tran, Sang X. Pham, Canh V. Vinh Univ Inst Engn & Technol 182 Duan St Vinh City Nghe An Vietnam Vinh Univ Cyber Sch 182 Duan St Vinh City Nghe Vietnam Phenikaa Univ ORLab Fac Comp Sci Hanoi Vietnam

The problem of The Student-Project Allocation problem with lecturer preferences over the Students containing Ties (SPA-ST) has attracted the attention of researchers because of its wide applications in allocating students to projects at many universities. So far, many methods have been proposed to solve the SPA-ST problem, such as the approximation algorithms, integer programming models, and local search. However, the problem of finding a stable matching of maximum size (MAX-SPA-ST) is NP-hard. These methods are yet to reach the optimal solution quality and the execution time is still a bottleneck for large-scale MAX-SPA-ST problems. In this paper, we propose a new algorithm for solving the MAX-SPA-ST problem. Our algorithm designs two heuristic functions to improve the solution quality and execution time. Experimental results on large randomly generated instances show that our algorithm is more efficient than the existing methods in terms of execution time and solution quality.

关键词： Student-Project allocation problem heuristic algorithm blocking pairs weakly stable matching MAX-SPA-ST large sizes

来源：评论

学校读者我要写书评

暂无评论

heuristic algorithm based on the principle of minimum total potential energy(HAPE):a new algorithm for nesting problems

引用

Journal of Zhejiang University-Science A(Applied Physics & Engineering) 2011年第11期12卷 860-872页

作者： Xiao LIU Jia-wei YE School of Civil and Transportation Engineering South China University of Technology Guangzhou 510640 China

We present a new algorithm for nesting *** equally spaced points are set on a sheet,and a piece is moved to one of the points and rotated by an *** the point and the rotation angle constitute the packing attitude of the *** propose a new algorithm named HAPE(heuristic algorithm based on the principle of minimum total Potential Energy) to find the optimal packing attitude at which the piece has the lowest center of *** addition,a new technique for polygon overlap testing is proposed which avoids the time-consuming calculation of no-fit-polygon(NFP).The detailed implementation of HAPE is presented and two computational experiments are *** first experiment is based on a real industrial problem and the second on 11 published benchmark *** a hill-climbing(HC) search method,the proposed algorithm performs well in comparison with other published solutions.

关键词： Packing Cutting Nesting Irregular heuristic algorithm Minimum total potential energy

来源：评论

学校读者我要写书评

暂无评论

heuristic algorithm for an optimal solution of fully fuzzy transportation problem

引用

COMPUTING 2024年第10期106卷 3195-3227页

作者： Kartli, Nermin Bostanci, Erkan Guzel, Mehmet Serdar Ankara Univ Comp Engn Dept TR-06830 Ankara Turkiye

Several problems involving uncertainties can be modeled with fuzzy numbers according to the type of these uncertainties. It is natural to express the solution to such a problem with fuzzy numbers. In this study, we consider the fully fuzzy transportation problem. All input parameters of the problem are expressed with fuzzy numbers given in the parametric form. We propose a new heuristic algorithm to approximate the fuzzy optimal solution. The fuzzy problem is solved by transforming it into two independent parametric problems with the proposed method. We first divide the interval [0, 1] into a sufficiently large number of equal intervals, then write a linear programming problem for each partition point and solve these problems by transforming them into transportation problems. The proposed algorithm is supported by examples.

关键词： Transportation problem Fuzzy numbers heuristic algorithm Optimal solution

来源：评论

学校读者我要写书评

暂无评论

heuristic algorithm for RPAMP with central rectangle and its application to solve oil-gas treatment facility layout problem

引用

ENGINEERING APPLICATIONS OF ARTIFICIAL INTELLIGENCE 2018年 72卷 294-309页

作者： Wu, Lei Liu, Qi Wang, Fengde Xiao, Wensheng Yang, Yaowen China Univ Petr Coll Mech & Elect Engn Qingdao 266580 Peoples R China Nanyang Technol Univ Sch Civil & Environm Engn Maritime Inst Singapore 639798 Singapore

In this study, we address a specific 2D rectangle packing area minimization problem with central rectangle (CR-RPAMP). The most distinguishing feature of CR-RPAMP is that there exists at least one central rectangle among the candidate rectangles. The proposed MHACR (modified heuristic algorithm for CR-RPAMP) includes three new strategies which are strategy of monitoring the aspect ratio, strategy of decreasing computational complexity and strategy of filling the marginal inner space. The computational complexity analyses show that MHACR has a lower computational complexity than the existing algorithms IHACR (improved heuristic algorithm for CR-RPAMP) and HACR (heuristic algorithm for CR-RPAMP). Then, a series of experiments based on 34 benchmark instances are carried out, and the experimental results show that MHACR can produce better solutions as compared with IHACR and HACR, especially under a narrow limited scope of aspect ratio. Finally, MHACR is used to solve the facility layout problem of oil gas treatment factory, and the final layout generated by MHACR is more suitable than that obtained by IHACR. Therefore, we can conclude that MHACR is a remarkable heuristic algorithm to solve CR-RPAMP.

关键词： Two-dimensional rectangle packing problem heuristic algorithm Central rectangle Aspect ratio Computational complexity Facility layout problem

来源：评论

学校读者我要写书评

暂无评论

heuristic algorithm FOR THE MINIMIZATION OF GENERALIZED BOOLEAN FUNCTIONS

引用

IEE PROCEEDINGS-E COMPUTERS AND DIGITAL TECHNIQUES 1988年第2期135卷 108-116页

作者： CARUSO, G Dipartimento di Ingegneria Elettrica Università di Palermo Palermo Italy

Generalised Boolean functions are useful in the design of programmable logic arrays. In this paper a heuristic algorithm suitable to minimise such functions is presented. The algorithm generates an irredundant cover by using a local approach to select generalised prime implicants. A benefit of such a method is that the preliminary generation of the set of all the generalised prime implicants is not required. Experimental results are presented, showing a favourable comparison with an already established minimisation algorithm as far as computing speed is concerned.

关键词： Logic circuits Logic and switching circuits minimisation Optimisation techniques cellular arrays Formal logic programmable logic arrays generalised Boolean functions Boolean functions heuristic algorithm

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：