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 co...
详细信息
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.
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 ...
详细信息
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.
The Global Food Supply Chain (GFSC) often encounters challenges in maintaining the continuous flow of essential food products such as rice and wheat. In this paper, we consider possible disruptions in supply and trans...
详细信息
The Global Food Supply Chain (GFSC) often encounters challenges in maintaining the continuous flow of essential food products such as rice and wheat. In this paper, we consider possible disruptions in supply and transportation in GFSC. Disruptions may cause severe food shortages in some parts of the world. Moreover, a disruption is not necessarily a single independent event, as multiple disruptions may occur sequentially or simultaneously. After any interruption, it is essential to reoptimize the remaining flow activities in a short period under the changed conditions. Although both the initial flow plan and post-disruption plan can be generated by formulating them as Mixed Integer Linear Programming (MILP) models, such a mitigation plan is challenging because of time constraints and when multiple disruptions are considered. To address this issue, we proposed a novel heuristic algorithm that revises the ideal plan in the event of a disruption. The developed heuristic can deal with different types of disruptions, as well as a series of disruptions. The performance of the heuristic was judged by solving 300 problem instances and comparing the results with those obtained from the exact method. To demonstrate the applicability of the proposed algorithm in practice, we have solved three real-world disruption Scenarios. The analysis of results uncovered crucial managerial insights, recommending strategies for disruption mitigation, and proved to be an effective method for post-disruption planning.
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 stud...
详细信息
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.
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 groupi...
详细信息
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.
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 collabor...
详细信息
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.
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 e...
详细信息
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.
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 gantr...
详细信息
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.
Active magnetic bearing (AMB) is an advanced contactless bearing system for high rotation speed equipment but cannot work stably without closed-loop control. Normally multiple proportional integral derivative (PID) co...
详细信息
Active magnetic bearing (AMB) is an advanced contactless bearing system for high rotation speed equipment but cannot work stably without closed-loop control. Normally multiple proportional integral derivative (PID) controllers are used to control the multiaxis AMB system. However, existing AMB PID controller tuning methods mainly focus on optimization and cannot turn an AMB system from unstable to stable. In this article, a model-free AMB PID tuning method is proposed to solve this problem for the first time, which imitates an experienced AMB engineer and utilizes physical information from runtime data. The effects of varying PID controller parameters on rotor displacements are analyzed in the time domain and meta-parameters are proposed to describe the parameters' performance. The effectiveness of the proposed tuning method is supported by the time-domain analysis and is also verified through experiments. For an unknown and untuned AMB system, the proposed tuning method provides a parameters solution in a short time with acceptable performance. With the tuned AMB system provided by the proposed tuning method, further works like system identification or optimization can be carried out more easily.
. In this paper, we consider the drone rural postman problem (DRPP). Unlike a vehicle in the traditional rural postman problem, a drone can travel directly between any two points without following the edges of the gra...
详细信息
. In this paper, we consider the drone rural postman problem (DRPP). Unlike a vehicle in the traditional rural postman problem, a drone can travel directly between any two points without following the edges of the graph. Thus, a drone can start (or restart) and end (or pause) the service of an edge at any two points of it, and an edge can be serviced separately (e.g., from an end point to the middle point in the first visit and the remaining half in the second visit). This property implies that a lower cost solution may be obtained by using a drone. In DRPP instances, the input data are represented by approximating each edge that have to be traversed by a polygonal chain with a finite number of vertices, allowing the drone to enter and exit each edge at these vertices. For this problem, we propose a heuristic algorithm consisting of two phases. In the first phase, we reduce the size of the original graph by considering the degree of each vertex and the cheapest travel costs between connected components. In the second phase, we solve the rural postman problem on the resulting graph. We show that the proposed two-phase heuristic has a performance guarantee of ratio 2. The experimental results on benchmark instances show that the proposed algorithm outperforms other existing algorithms.
暂无评论