The time complexity of b algorithm, one of the intelligent search algorithms, is discussed. by anatomizing some instances, it is pointed out that the cost of calculating the value of heuristic function should be inclu...
详细信息
ISBN:
(纸本)9780878492879
The time complexity of b algorithm, one of the intelligent search algorithms, is discussed. by anatomizing some instances, it is pointed out that the cost of calculating the value of heuristic function should be included in the range of time complexity analysis for b algorithm. And then, an algorithm of calculating the value of heuristic function is presented. by analyzing the cost of calculating the value of heuristic function, it is pointed out that the number of recursions in b algorithm is O(n!) in the worst case. Therefore, the time complexity of b algorithm is exponential instead of O(n(2)).
A widely used technique for predicting traffic flows in individual roads of a road traffic network is the user-equilibrium (UE) traffic assignment (TA). This technique assigns trips from origins to destinations in a r...
详细信息
A widely used technique for predicting traffic flows in individual roads of a road traffic network is the user-equilibrium (UE) traffic assignment (TA). This technique assigns trips from origins to destinations in a road traffic network so that all trips use the cheapest path. The cost of the path, which consists of roads (edges), is the sum of the roads costs. These costs increase with increasing flow in these roads. In this paper, we describe the parallelization of the b algorithm - a relatively new TA algorithm with a fast convergence to a solution. Since the nature of the algorithm and the nature of its fast convergence complicate the parallelization itself, we considered and implemented three parallel variants and tested them on real road traffic networks to investigate their convergence, usability, and speed. The parallelization is intended for a shared memory parallel computing environment. The description of the parallelization along with the performed tests is the main contribution of this paper. (C) 2021 THE AUTHORS. Published by Elsevier bV on behalf of Faculty of Engineering, Ain Shams University.
Single-machine scheduling problem with preventive maintenance is an non-deterministic polynomial-hard combinatorial optimisation problem, which has significant applications in the real world. To meet the realistic req...
详细信息
Single-machine scheduling problem with preventive maintenance is an non-deterministic polynomial-hard combinatorial optimisation problem, which has significant applications in the real world. To meet the realistic requirements, high-speed heuristic algorithms should be developed. In this study, a single-machine scheduling problem with flexible maintenance and non-resumable jobs is studied. Some properties for optimally solving this problem are first proposed, and then two mixed-integer programming (MIP) models are provided. Next, a branch-and-bound (b&b) algorithm, four heuristic algorithms and the procedures to improve the quality of their solution are developed based on the properties of the optimal solution. Experimental results indicate that the proposed heuristic algorithms can obtain near-optimal solutions within a very short computation time compared with the MIP and b&b methods. The heuristic algorithms of Minimum Waste and Lower bound Index are particularly satisfactory in terms of both solution efficiency and accuracy in solving the addressed problem.
暂无评论