An adaptive tabu search approach for buffer allocation problem in unreliable non-homogenous production lines

The buffer allocation problem, i.e. how much buffer storage to allow and where to place it within the line, is an important research issue in designing production lines. In this study, a novel adaptive tabu search approach is proposed for solving buffer allocation problem in unreliable and non-homogeneous production lines. The objective is to maximize the throughput of the line, which is constrained by the capacity of each buffer space and also the total buffer capacity to allocate to these spaces. Besides proposing a new strategy to tune the parameters of tabu search adaptively during the search, an experimental study is carried out to select an intelligent initial solution scheme among three alternatives so as to decrease the search effort to obtain the best solutions. The performance of the proposed approach is evaluated by computational tests and very promising results are obtained.     

Hybrid approach for buffer allocation in open serial production lines

The buffer allocation problem is an NP-hard combinatorial optimization problem involving the determination of the number of buffers in buffer locations required to increase the efficiency of a production line. Researchers in this field have proposed various optimization techniques to solve the problem for different types of production system configurations. In this study, a hybrid approach-based simulation optimization is proposed to determine the buffer sizes required in open serial production lines to maximize the average production rate of the system. This approach involves the use of a search tool and an evaluative tool. A hybrid approach using a genetic algorithm and simulated annealing is used as a search tool to create candidate buffer sizes. As an evaluative tool, discrete event simulation modeling is used to obtain the average production rate of the line. The performance of the proposed approach and the power of the hybridization are investigated for various serial line configurations. Promising results demonstrate the efficacy of the proposed hybrid approach for the buffer allocation problem in open serial lines.     

Multi-objective imperfect maintenance optimization for production system with an intermediate buffer

In several production systems, buffer stocks are built between consecutive machines to ensure the continuity of supply during interruptions of service caused by breakdowns or planned maintenance actions. However, in previous research, maintenance planning is performed individually without considering buffer stocks. In order to balance the trade-offs between them, in this study, an integrated model of buffer stocks and imperfective preventive maintenance for a production system is proposed. This paper considers a repairable machine subject to random failure for a production system by considering buffer stocks. First, the random failure rate of a machine becomes larger with the increase of the number of random failures. Thus, the renewal process is used to describe the number of random failures. Then, by considering the imperfect maintenance action reduced the age of the machine partially, a mathematical model is developed in order to determine the optimal values of the two decision variables which characterize the proposed maintenance strategy and which are: the size of the buffer stock and the maintenance interval. The optimal values are those which minimize the average total cost per time unit including maintenance cost, inventory holding cost and shortage cost, and satisfy the availability constraint. Finally, a heuristic procedure is used to solve the proposed model, and one experiment is used to evaluate the performance of the proposed methods for joint optimization between buffer stocks and maintenance policy. The results show that the proposed methods have a better performance for the joint optimization problem and can be able to obtain a relatively good solution in a short computation time.     

Dynamic buffer management with extensible replacement policies

The objective of extensible DBMSs is to ease the construction of specialized DBMSs for nontraditional applications. Although much work has been done in providing various levels of extensibility (e.g., extensibility of data types and operators, query language extensibility, and query optimizer extensibility), there has been very limited research in providing extensibility at the buffer management level. Supporting extensibility at the buffer management level is important as it can contribute significantly to overall system performance. This paper addresses the problem of supporting extensibility of buffer replacement policies. The main contribution is the proposal of a framework for modeling buffer replacement policies. This work is novel in two aspects. First, by providing a uniform and generic specification of buffer replacement policies, the proposed framework unifies existing work in this area. Second, our work introduces a new level of extensibility. None of the existing extensible DBMSs, to our knowledge, provides extensibility at the buffer management level. The proposed framework provides a basis for the construction of an extensible buffer manager as part of a 100% Java-based storage manager. We conducted an extensive performance study to investigate the performance of the proposed framework. The experimental results demonstrate that the proposed framework is indeed feasible for existing DBMSs and improves system performance significantly without costing significant overhead. Edited by M. Kersten     

Buffer management based on return on consumption in a multi-query environment

In a multi-query environment, the marginal utilities of allocating additional buffer to the various queries can be vastly different. The conventional approach examines each query in isolation to determine the optimal access plan and the corresponding locality set. This can lead to performance that is far from optimal. As each query can have different access plans with dissimilar locality sets and sensitivities to memory requirement, we employ the concepts of memory consumption and return on consumption (ROC) as the basis for memory allocations. Memory consumption of a query is its space-time product, while ROC is a measure of the effectiveness of response-time reduction through additional memory consumption. A global optimization strategy using simulated annealing is developed, which minimizes the average response over all queries under the constraint that the total memory consumption rate has to be less than the buffer size. It selects the optimal join method and memory allocation for all query types simultaneously. By analyzing the way the optimal strategy makes memory allocations, a heuristic threshold strategy is then proposed. The threshold strategy is based on the concept of ROC. As the memory consumption rate by all queries is limited by the buffer size, the strategy tries to allocate the memory so as to make sure that a certain level of ROC is achieved. A simulation model is developed to demonstrate that the heuristic strategy yields performance that is very close to the optimal strategy and is far superior to the conventional allocation strategy.     

Detecting buffer overflow via automatic test input data generation

Buffer overflows cause serious problems in various categories of software systems. In critical systems, such as health-care, nuclear or aerospace software applications, a buffer overflow may cause severe threats to humans or severe economic losses. If they occur in network or security applications, they can be exploited to gain administrator privileges, perform system attacks, access unauthorized data, or misuse the system. This paper proposes a combination of genetic algorithms, linear programming, evolutionary testing, and static and dynamic information to detect buffer overflows. The newly proposed test input generation process avoids the need for human intervention to define and tune genetic algorithm weights and therefore it becomes completely automated. The process that guides the genetic search towards the detection of buffer overflow relies on a fitness function that takes into account static and dynamic information. Reported results of our case studies, consisting of two sets of open-source programs show that the new process and fitness function outperform previously published approaches.     

A real-time video watermarking system with buffer sharing for video-on-demand service

Real-time watermarking for streaming video (such as VOD service) requires significant amounts of computing resources. To address this issue, we present a scalable watermarking scheme integrated in a parallel MPEG-2 engine. A content-based block selection algorithm is proposed to efficiently embed the pseudo-random watermark signatures into DCT blocks. Our watermark scheme also provides a robust way to synchronize the watermarked video to the original source at detectors and is very resilient against cumulative and temporal attack.We optimize the parallel watermark engine to achieve real-time watermarking performance. We found that the system throughput could suffer significant degradation when processing high-level MPEG-2 video (such as HDTV) due to inefficient management of memory space. Therefore, we investigated an efficient buffer management scheme consisting of two methods: First we reduced the transmission buffer in slave nodes by frames sharing between frames in the Group-of-Picture (GOP) level. Then we further reduce the buffer space by a dynamic on-demand allocation on the slave side. By solving the memory-shortage bottleneck, the proposed system can support real-time watermarking for multiple high-resolution (up to 1404 × 960) video.     

Two approaches for solving the buffer allocation problem in unreliable production lines

This paper presents an integrated approach to solve the buffer allocation problem in unreliable production lines so as to maximize the throughput rate of the line with minimum total buffer size. The proposed integrated approach has two control loops; the inner loop and the outer loop. While the inner loop control includes an adaptive tabu search algorithm proposed by Demir et al. [8], binary search and tabu search are proposed for the outer loop. These nested loops aim at minimizing the total buffer size to achieve the desired throughput level. To improve the efficiency of the proposed tabu search, alternative neighborhood generation mechanisms are developed. The performances of the proposed algorithms are evaluated by extensive computational experimentation, and the results are reported.     

Price-based buffer sizing in assembly systems

Internal transfer pricing mechanism will be applied to the problem of buffer allocation in the context of interfacing an assembly line with multiple parallel production lines. Economic effect of buffer sizing iin assembly will be analyzed by means of internal transfer pricing. New internal transfer pricing scheme will be designed to increase the efficiency of assembly system globally not sub-optimally. This new approach will enhance the economic benefit of production channel between an assembly line and multiple production lines. This study will give the basic idea for the application of internal transfer pricing mechanism in various kinds of manufacturing system to increase economic efficiency globally.     

Buffer management for lossless service in shared buffer switches

Fair scheduling and buffer management are two typical approaches to provide differentiated service. Fair scheduling algorithms usually need to keep a separate queue and maintain associated state variables for each incoming flow, which makes them difficult to operate and scale. On the contrary, buffer management (in conjunction with FIFO scheduling) needs only a constant amount of state information and processing, and can be efficiently implemented. In this paper, we consider using buffer management to provide lossless service for guaranteed performance flows in shared buffer switches. We study the buffer size requirement and buffer allocation strategies by starting with the single output switch and then extending the analytical results to the general multiple output switch. We present a universally applicable buffer allocation method for assuring lossless service, and validate the correctness of the theoretical results through simulations.     

一种改进的iSCSI存储系统中的缓冲策略

iSCSI存储系统具有容量大、高性能、扩展性好等优点，但仍然不能克服目前的磁盘I／O速度普遍跟不上处理器速度和网络传输速度的问题。针对这种情况，提出了一种改进的iSCSI存储系统的缓冲策略，尽量避免在处理请求时直接对存储设备进行读写。实验证明，这种策略提高了网络传输速率，缩短了系统响应时间，增加了系统的并行性。     

Dynamic buffer allocation in an ATM switch

Efficient and fair use of buffer space in an Asynchronous Transfer Mode (ATM) switch is essential to gain high throughput and low cell loss performance from the network. In this paper a shared buffer architecture associated with threshold-based virtual partition among output ports is proposed. Thresholds are updated based on traffic characteristics on each outgoing link, so as to adapt to traffic loads. The system behavior under varying traffic patterns is investigated via simulation; cell loss rate is the quality of service (QoS) measure used in this study. Our study shows that the threshold based dynamic buffer allocation scheme ensures a fair share of the buffer space even under bursty loading conditions.     

关于新的弱化缓冲算子的研究及其应用

在灰色系统理论缓冲算子公理体系下,构造出一类新的弱化缓冲算子.研究其一些特性和内在联系,可有效地解决冲击扰动数据序列在建模预测过程中经常出现的定量预测结果与定性分析结论不符的问题.实例分析结果表明,该类算子是有效而实用的.     

机会网络中基于能量消耗的缓存管理策略

为了减少机会网络中节点的能量消耗,均衡各节点之间能量使用情况,延长网络寿命,提出基于能耗的缓存管理策略。在节点缓存空间有限的情况下,所提出的算法根据周围邻居节点能量的使用情况,动态调整节点用于缓存转发消息空间的大小,从而减少节点在存储-转发过程中的能量消耗。同时,为了避免传统休眠机制的能耗路由算法中由于目的节点休眠而导致消息投递失败的情况,引入了新的Inactive节点状态。实验仿真表明,与定时休眠机制的能耗算法比较,采用基于能量消耗的缓存管理策略能够使得机会网络中所有节点的整体能耗降低50%左右,并且节点之间能耗的标准差降低80%以上。     

Buffer allocation in general single-server queueing networks

The optimal buffer allocation in queueing network systems is a difficult stochastic, non-linear, integer mathematical programming problem. Moreover, the objective function, the constraints or both are usually not available in closed form, making the problem even harder. A good approximation for the performance measures is thus essential for a successful buffer allocation algorithm. A recently published two-moment approximation formula to obtain the optimal buffer allocation in general service time single queues is examined in detail, based on which a new algorithm is proposed for the buffer allocation in single-server general service time queueing networks. Computational results and simulation results are shown to evaluate the efficacy of the approach in generating optimal buffer allocation patterns.     

Near optimal buffer allocation in remanufacturing systems with N-policy

We introduce a near optimal buffer allocation plan (NOBAP) specifically developed for a cellular remanufacturing system with finite buffers where the servers follow N-policy. The term N-policy is used for the situation where the server leaves primary work to tend to an external workload assigned to him (such as processing additional tasks or performing preventive maintenance of equipments) every time the server becomes idle and does not return back to his primary work until the queue size in front of the primary work reaches a threshold value of N (?1). The remanufacturing system considered here consists of three modules, viz., the disassembly module for returned products, the testing module and the remanufacturing module. In order to analyze the system we propose an algorithm that uses an open queueing network, decomposition principle and expansion methodology. The buffer allocation algorithm distributes a given number of available buffer slots among the remanufacturing system stations to optimize the system’s performance. The algorithm has been rigorously tested using a variety of experimental conditions. From the results, it is clear that the algorithm’s performance is robust, consistent and produces excellent results.     

Optimal buffer allocation in short μ-balanced unreliable production lines

In this work, we investigate the optimal buffer allocation in short μ-balanced production lines consisting of machines that are subject to breakdown. Repair times and times to failure are assumed exponential, whereas service times are allowed to follow the Erlang-k distribution (with k=1, 2, 4 and 8). By an improved enumeration procedure and applying the evaluative algorithm of Heavey et al. (European Journal of Operational Research 1993;68:69–89) for the calculation of throughput, we have examined in a systematic way several systems with 3, 4, 5, 6 and 7 stations and with a different total number of buffer slots. We have been able to give answers to some critical questions. These include the effect of the distribution of the service and repair times, the availability of the stations and the repair rates on the optimal buffer allocation and the throughput of the lines.     

Exploiting write-only-once characteristics of file data in smartphone buffer cache management

In this article, we analyze file access characteristics of smartphone applications and find out that a large portion of file data in smartphones are written only once. This specific phenomenon appears due to the behavior of SQLite, a lightweight database library used in most smartphone applications. Based on this observation, we present a new buffer cache management scheme for smartphone systems that considers non-reusability of write-only-once data that we observe. Buffer cache improves file access performances by maintaining hot data in memory thereby servicing subsequent requests without storage accesses. The proposed scheme classifies write-only-once data and aggressively evicts them from the buffer cache to improve cache space utilization. Experimental results with various real smartphone applications show that the proposed buffer cache management scheme improves the performance of smartphone buffer cache by 5%–33%. We also show that our scheme can reduce the buffer cache size to 1/4 of the original system without performance degradation, which allows the reduction of energy consumption in a smartphone memory system by 27%–92%.     

Approximating the buffer allocation problem using epochs

The correctness of applications that perform asynchronous message passing typically relies on the underlying hardware having a sufficient amount of memory (message buffers) to hold all undelivered messages—such applications may deadlock when executed on a system with an insufficient number of message buffers. Thus, determining the minimum number of buffers that an application needs to prevent deadlock is an important task when writing portable parallel applications. Unfortunately, both this problem (called the Buffer Allocation Problem) and the simpler problem of determining whether an application may deadlock for a given number of available message buffers are intractable [A. Brodsky, J. Pedersen, A. Wagner, On the complexity of buffer allocation in message passing systems, Journal of Parallel and Distributed Computing 65 (2005) 692–713].     

非均匀业务流下的片上网络缓冲区分配算法*

针对片上网络的非均匀业务流,提出一种基于模拟退火遗传算法的缓冲区资源分配算法,对系统的有限缓冲区资源的分配问题进行了研究。该算法建立在二维Mesh结构的片上网络通信模型基础上,根据各节点间的业务流特征,估计出节点中各输入通道的负载大小,再根据其负载情况采用模拟退火遗传算法进行缓冲区资源的分配,从而使整个网络的平均延时性能最优。实验中设置了不同的热点位置和热度,结果表明,该算法可以更合理地分配缓冲区资源,有效降低数据包的传输延时。在单热点通信流量下,热度为100%和300%时,可分别降低传输延时32.58% ~ 65.29%和35.54% ~ 70.38%;在双热点通信流量下,可降低传输延时52.02% ~ 70.43%。同时,该算法具有良好的收敛性。