An efficient submesh allocation scheme for two-dimensional mesheswith little overhead

This paper presents a submesh allocation scheme for two-dimensional mesh systems. The submesh detection process considers only those available free submeshes that border from the left on some allocated submeshes or have their left boundaries aligned with that of the mesh. Fragmentation in the system can be reduced as a result. More importantly, we present an efficient approach to facilitate the detection of such available submeshes. The basic idea of the approach is to place the allocated submeshes of the busy set in a certain order so as to reduce the complexity of subtraction operations required for submesh detection. The method is simple and causes an amount of overhead which is only a fraction of that produced by previous algorithms. Extensive simulation has been conducted to evaluate the performance of the proposed scheme. The results show that when allocation overhead is considered, the proposed scheme may outperform previous methods     

An efficient variable neighborhood search heuristic for very large scale vehicle routing problems

In this paper, we present an efficient variable neighborhood search heuristic for the capacitated vehicle routing problem. The objective is to design least cost routes for a fleet of identically capacitated vehicles to service geographically scattered customers with known demands. The variable neighborhood search procedure is used to guide a set of standard improvement heuristics. In addition, a strategy reminiscent of the guided local search metaheuristic is used to help escape local minima. The developed solution method is specifically aimed at solving very large scale real-life vehicle routing problems. To speed up the method and cut down memory usage, new implementation concepts are used. Computational experiments on 32 existing large scale benchmarks, as well as on 20 new very large scale problem instances, demonstrate that the proposed method is fast, competitive and able to find high-quality solutions for problem instances with up to 20,000 customers within reasonable CPU times.     

An improved NEH-based heuristic for the permutation flowshop problem

NEH is an effective heuristic for solving the permutation flowshop problem with the objective of makespan. It includes two phases: generate an initial sequence and then construct a solution. The initial sequence is studied and a strategy is proposed to solve job insertion ties which may arise in the construct process. The initial sequence which is generated by combining the average processing time of jobs and their standard deviations shows better performance. The proposed strategy is based on the idea of balancing the utilization among all machines. Experiments show that using this strategy can improve the performance of NEH significantly. Based on the above ideas, a heuristic NEH-D (NEH based on Deviation) is proposed, whose time complexity is O(mn²), the same as that of NEH. Computational results on benchmarks show that the NEH-D is significantly better than the original NEH.     

面向高效深度包检测的启发式正则表达式分组算法*

经过对正则表达式合并DFA状态爆炸问题的分析,采用正则表达式两两合并DFA的状态增加数之和衡量多个正则表达式合并后真实的状态增加情况,将正则表达式最优分组问题归约为带权无向图的k-最大割问题。在此基础上,提出一种面向高效深度包检测的启发式正则表达式分组算法REG-EDPI。采用贪婪策略构造初始解,引入移除参数进行迭代优化。实验表明相比于其他算法,REG-EDPI算法能够在合理的运行时间内,获得更优的分组策略,具有更强的实际应用价值。     

An energy-efficient permutation routing protocol for single-hop radio networks

A radio network (RN) is a distributed system where each station or node is a small hand-held commodity device called a station. Typically, each station has access to a few channels for transmitting and receiving messages. By RN(p, k), we denote a radio network with p stations, where each station has access to k channels. In a single-hop RN, every station is within the transmission range of every other station. Each station consumes power while transmitting or receiving a message, even when it receives a message that is not destined for it. It is extremely important that the stations consume power only when it is necessary since it is not possible to recharge batteries when the stations are on a mission. We are interested in designing an energy-efficient protocol for permutation routing, which is one of the most fundamental problems in any distributed system. An instance of the permutation routing problem involves p stations of an RN, each storing n/p items. Each item has a unique destination address which is the identity of the destination station to which the item should be sent. The goal is to route all the items to their destinations while consuming as little energy as possible. We show that the permutation routing problem of n packets on an RN(p, k) can be solved in 2n/k+(p/k)/sup 2/+p+2k/sup 2/ slots and each station needs to be awake for at most 6n/p+2p/k+8k slots. When k/spl Lt/p/spl Lt/n, our protocol is more efficient, both in terms of total number of slots and the number of slots each station is awake compared to a previously published protocol by Nakano et al. (2001).     

An efficient heuristic algorithm for selecting projects

Consider the problem of selecting a set of projects from a large number of available projects such that at least some specified levels of benefits of various types are realized at a minimum cost. This problem can be formulated in terms of the well-known 0–1 multi-dimensional knapsack problem, a special case of the general integer programming problems. In view of the NP-completeness of these problems, this paper proposes a polynomially bounded and efficient heuristic algorithm for its solution. The proposed algorithm proceeds as follows: an initial selection is found by prioritizing the projects according to a computed discard index. This initial selection set is then altered to reduce total costs by using project exchange operations. Computational results indicate that the proposed algorithm is quite effective in finding optimal or near optimal solutions.     

An efficient heuristic algorithm for rectangle-packing problem

Rectangle-packing problem involves many industrial applications, such as shipping, timber cutting, very large scale integration (VLSI) floor planning, and so on. This problem has shown to be NP hard, and many algorithms such as genetic algorithm, simulated annealing and other heuristic algorithms are presented to solve it. Based on the wisdom and experience of human being, an efficient heuristic algorithm is proposed in this paper. Two group benchmarks are used to test the performance of the produced algorithm, 19 instances of first group and 3 instances of second group having achieved optimal solutions. The experimental results demonstrate that the presented algorithm is rather efficient for solving the rectangle-packing problem.     

An approach for efficient ship routing

Ship routing problems are a particular kind of routing problems where the vehicles to be routed are vessels or ships, usually in maritime environments. In contrast to land routing, ship routing has unique features, including overnight trips, disjoint time windows, not necessarily prespecified routes, and a great uncertainty derived from weather conditions. In this work we present a special ship routing problem, which incorporates many features present in general ship routing settings. We discuss aspects related with data gathering and updating, which are particularly difficult in the context of ship routing. Additionally, we present a GRASP algorithm to solve this problem. We apply our solution approach to a salmon feed supplier based in southern Chile, and present computational results on real data.     

An improved heuristic for the capacitated arc routing problem

The capacitated arc routing problem (CARP) is an important and practical problem in the OR literature. In short, the problem is to identify routes to service (e.g., pickup or deliver) demand located along the edges of a network such that the total cost of the routes is minimized. In general, a single route cannot satisfy the entire demand due to capacity constraints on the vehicles. CARP belongs to the set of NP-hard problems; consequently numerous heuristic and metaheuristic solution approaches have been developed to solve it. In this paper an “ellipse rule” based heuristic is proposed for the CARP. This approach is based on the path-scanning heuristic, one of the mostly used greedy-add heuristics for this problem. The innovation consists basically of selecting edges only inside ellipses when the vehicle is near the end of each route. This new approach was implemented and tested on three standard datasets and the solutions are compared against: (i) the original path-scanning heuristic; (ii) two other path-scanning heuristics and (iii) the three best known metaheuristics. The results indicate that the “ellipse rule” approach lead to improvements over the three path-scanning heuristics, reducing the average distance to the lower bound in the test problems by about 44%.     

Hot-potato algorithms for permutation routing

We develop a methodology for the design of hot-potato algorithms for routing permutations. The basic idea is to convert existing store-and-forward routing algorithms to hot-potato algorithms. Using it, we obtain the following complexity bounds for permutation routing: n×n Mesh: 7n+o(n) steps; 2ⁿ hypercube: O(n²) steps; n×n Torus: 4n+o(n) steps. The algorithm for the two-dimensional grid is the first to be both deterministic and asymptotically optimal. The algorithm for the 2ⁿ-nodes Boolean cube is the first deterministic algorithm that achieves a complexity of o(2ⁿ) steps     

An efficient placement heuristic for three-dimensional rectangular packing

By embodying the spirit of “gold corner, silver side and strawy void” directly on the candidate packing place such that the searching space is reduced considerably, and by utilizing the characteristic of weakly heterogeneous problems that many items are in the same size, a fit degree algorithm (FDA) is proposed for solving a classical 3D rectangular packing problem, container loading problem. Experiments show that FDA works well on the complete set of 1500 instances proposed by Bischoff, Ratcliff and Davies. Especially for the 800 difficult strongly heterogeneous instances among them, FDA outperforms other algorithms with an average volume utilization of 91.91%, which to our knowledge is 0.45% higher than current best result just reported in 2010.     

An efficient heuristic for reliability design optimization problems

This paper develops an efficient heuristic to solve two typical combinatorial optimization problems frequently met when designing highly reliable systems. The first one is the redundancy allocation problem (RAP) of series-parallel binary-state systems. The design goal of the RAP is to select the optimal combination of elements and redundancy levels to maximize system reliability subject to the system budget and to the system weight. The second problem is the expansion-scheduling problem (ESP) of multi-state series-parallel systems. In this problem, the study period is divided into several stages. At each stage, the demand is represented as a piecewise cumulative load curve. During the system lifetime, the demand can increase and the total productivity may become insufficient to assume the demand. To increase the total system productivity, elements are added to the existing system. The objective in the ESP is to minimize the sum of costs of the investments over the study period while satisfying availability constraints at each stage. The heuristic approach developed to solve the RAP and the ESP is based on a combination of space partitioning, genetic algorithms (GA) and tabu search (TS). After dividing the search space into a set of disjoint subsets, this approach uses GA to select the subspaces, and applies TS to each selected subspace. Numerical results for the test problems from previous research are reported and compared. The results show the advantages of the proposed approach for solving both problems.     

An efficient deterministic heuristic for two-dimensional rectangular packing

This paper proposes a deterministic heuristic, a best fit algorithm (BFA), for solving the NP-hard two-dimensional rectangular packing problem to maximize the filling rate of a rectangular sheet. There are two stages in this new approach: the constructive stage and the tree search stage. The former aims to rapidly generate an initial solution by employing the concepts of action space and fit degree in evaluating different placements. The latter seeks to further improve the solution and searches for promising placements by a partial tree search procedure. We then compare BFA with other approaches in terms of solution quality and computing time. We carry out computational experiments on two sets of well-known benchmark instances, C21 proposed by Hopper and Turton, and N13 proposed by Burke et al. BFA gained an average filling rate of 100% for the C21 instances within short times, indicating that all the layouts obtained are optimal. To the best of our knowledge, this is the first time that optimal layouts on all the 21 instances were obtained by a deterministic algorithm. As for the N13 instances, to date, researchers have found optimal solutions to the first three instances, whereas BFA solved seven, including the first three, within a reasonable period. An additional work is to adapt BFA to solve a relevant problem, the constrained two-dimensional cutting (or packing) problem (CTDC). Though BFA is not for the CTDC in the original design such that some specific characteristics of CTDC are not considered, the adapted algorithm still performed well on 21 public CTDC instances.     

An efficient stochastic hybrid heuristic for flowshop scheduling

The paper addresses the problem of flowshop scheduling in order to minimize the makespan objective. Three probabilistic hybrid heuristics are presented for solving permutation flowshop scheduling problem. The proposed methodology combines elements from both constructive heuristic search and a stochastic improvement technique. The stochastic method used in this paper is simulated annealing (SA). Experiments have been run on a large number of randomly generated test problems of varying jobs and machine sizes. Our approach is shown to outperform best-known existing heuristics, including the classical NEH technique (OMEGA, 1983) and the SA based on (OMEGA, 1989) of Osman and Potts . Statistical tests of significance are performed to substantiate the claims of improvement.     

An efficient LP-based admissible heuristic for cost-based abduction

Cost-based abduction (CBA) is an important problem in reasoning under uncertainty. The CBA problem is NP-hard, and existing techniques have exponential worst-case complexity. This paper presents an admissible heuristic for CBA based on the use of linear programming to obtain an optimistic estimate of the cost-to-goal. The article then presents empirical results that indicate that the authors' method is efficient in comparison to Santos‘ integer linear programming method.     

An efficient Lagrangean heuristic for rental vehicle scheduling

In this article we present a heuristic based on Lagrangean relaxation for scheduling rental vehicles. The scheduling problem can be formulated as a set of large assignment problems with linking constraints. We discuss the theory behind the heuristic, including the ability to obtain lower bounds. The heuristic is based on ideas first introduced by D. Wedelin.     

An efficient buffer memory system for subarray access

Many current graphical display systems utilize a buffer memory system to contain a two-dimensional image array to be modified and displayed. In order to speed up the update of the buffer memory system, it is required that the buffer memory system accesses many image points within an image subarray in parallel. This paper proposes an efficient buffer memory system for a fast and high-resolution graphical display system. The memory system provides parallel accesses to pq image points within a block(p×q), a horizontal (1×pq), a vertical (pq×1), a forward-diagonal, or a backward-diagonal subarray in a two-dimensional image array, M×N, where the design parameters p and q are all powers of two. In the address calculation and routing circuit of the proposed buffer memory system, the address differences of the five subarrays are prearranged according to the index numbers of memory modules and stored in two static random access memories (SRAMs), so that the address differences are simply added to the base address to obtain the addresses according to the index numbers of memory modules. In addition, for the fast address calculation, one single multiplication operation in the base address calculation is replaced by a SRAM access, so that the multiplication operation can be performed during the SRAM access for the address differences for the case when N is not a power of two. The address calculation and routing circuit proposed in this paper is improved in the hardware cost, the complexity of control, and the speed over the previous circuits     

基于能量优化的Ad hoc认知无线电网络组播路由启发式算法研究*

提出了两个Ad hoc认知无线电网络中基于能量优化的组播路由启发式算法。一个是基于经典的最短路径树的组播算法（shortest path tree algorithm,SPTA）,另一个是基于能量函数的组播启发式算法(energy function based heuristic algorithm,EFHA)。这两个算法都在考虑了认知无线电网络特性的基础上建立能量优化的组播树,从应用例子可以看出, EFHA算法明显优于SPTA算法,并且复杂度较低。     

An efficient implementation of the Min-Min heuristic

Min—Min is a popular heuristic for scheduling tasks to heterogeneous computational resources, which has been applied either directly or as part of more sophisticated heuristics. However, for large scenarios such as grid computing platforms, the time complexity of a straightforward implementation of Min—Min, which is quadratic in the number of tasks, may be prohibitive. This has motivated the development of high performance computing (HPC) implementations, and the use of simpler heuristics for the sake of acceptable execution times. We propose a simple algorithm that implements Min—Min requiring only O(mn) operations for scheduling n tasks on m machines. Our experiments show, in practice, that a straightforward sequential implementation of this algorithm significantly outperforms other state of the art implementations of Min—Min, even compared to HPC implementations. In addition, the proposed algorithm is at least as suitable for parallelization as a direct implementation of Min—Min.