Server Allocation Algorithms for Tiered Systems

Many web-based systems have a tiered application architecture, in which a request needs to transverse all the tiers before finishing its processing. One of the most important QoS metrics for these applications is the expected response time for the user. Since the expected response time in any tier depends upon the number of servers allocated to this tier, and a request's total response time is the sum of the response times over all the tiers, many different configurations (number of servers allocated to each tier) can satisfy the expected response-time requirement. Naturally, one would like to find the configuration that minimizes the total system cost while satisfying the total response-time requirement. This is modeled as a non-linear optimization problem using an open-queuing network model of response time, which we call the server allocation problem for tiered systems (SAPTS). In this paper we study the computational complexity of SAPTS and design efficient algorithms to solve it. For a variable number of tiers, we show that the decision version of SAPTS is NP-complete. Then we design a simple two-approximation algorithm and a fully polynomial-time approximation scheme (FPTAS). If the number of tiers is a constant, we show that SAPTS is polynomial-time solvable. Furthermore, we design a fast polynomial-time exact algorithm to solve the important two-tier case. Most of our results extend to the general case in which each tier has an arbitrary response-time function.     

A grouped storage method for minimizing relocations in block stacking systems

When storage and retrieval times of inventories are uncertain and the storage space for the inventories is limited, it is an important problem to assign the inventories to storage spaces so that the total expected number of relocations is minimized. This paper addresses a dynamic location problem as well as a static location problem. Mathematical models are proposed for obtaining the optimal solution. To overcome the excessive computational time of optimizing methods, a genetic algorithm is suggested. Also, simple heuristic rules are suggested to solve the dynamic location problem. Performance of various solution methods are compared with each other. Received: June 2005 / Accepted: December 2005     

A generalized sequential preventive maintenance policy for repairable systems with general random minimal repair costs

A generalized sequential preventive maintenance (PM) policy for repairable systems with general random minimal repair costs is proposed and analysed. After each (planned or unplanned) preventive maintenance, the system has a different failure distribution and the failure rate function increases with the number of preventive maintenances carried out. The criterion for the optimal policy is to minimize the expected cost per unit time for an infinite time span. It is shown that under certain reasonable assumptions, sequential preventive maintenance policy has unique solutions. Various special cases are considered.     

Wartime logistics model for multi‐support unit location–allocation problem with frontline changes

To reflect a realistic, changing front line, wartime logistics are illustrated by a dynamic location–allocation model. In this paper, a mixed integer programming (MIP) model is developed for use in deciding the timing of unit relocation for continuous resupply, safe locations for support units, and delivery amounts that minimize total risk to the logistics service. Total risk in wartime logistics is represented by unsatisfied demand, hazard at the support site, and the number of relocations. The proposed MIP model reflects realistic factors in battle situations, such as maximum distance, vehicle capacity, basic load carried by combat units, and limited supplies during unit relocation. Furthermore, special operators for crossover and mutation are developed to maintain feasibility of possible solutions, and an efficient hybrid genetic algorithm is proposed to find optimal and near‐optimal solutions.     

A heuristic rule for relocating blocks

One of the most important objectives of the storage and pickup operations in block stacking systems is to minimize the number of relocations during the pickup operation. This study suggests two methods for determining the locations of relocated blocks. First, a branch-and-bound (B&B) algorithm is suggested. Next, a decision rule is proposed by using an estimator for an expected number of additional relocations for a stack. The performance of the decision rule was compared with that of the B&B algorithm.     

Inventory of damageable items with variable replenishment and unit production cost via simulated annealing method

Items made of glass, ceramic, etc. are normally stored in stacks and get damaged during the storage due to the accumulated stress of heaped stock. The researchers have overlooked the inventory problems for this type of items. Again the classical iterative optimization techniques very often stuck to the local optimum present in the search space. This is one of the hindrances in optimizing the non-linear problems.Annealing is the physical process of heating up a solid until it melts followed by cooling it down until it crystallizes into a state with perfect lattice. Following this physical phenomenon, recently a soft computing method, Simulated Annealing (SA), has been developed to find the global optimum for a complex cost surface through stochastic search process.In this paper, a deterministic inventory model of a damageable item is developed with variable replenishment rate and unit production cost. Here replenishment rate and unit production cost are dependent on demand. Demand and damageability are stock dependent. This dependency may be linear or non-linear. The optimum inventory level is evaluated by the profit maximization principle through SA algorithm. The model is illustrated numerically with different forms of demand and damage functions.     

Optimal maintenance policies for several imperfect repair models

Three new maintenance models, two imperfect preventive maintenance models and a cost limit (imperfect) repair model are proposed. In these models the imperfect maintenance is treated in such a way that after maintenance the lifetime of a unit will be decreased to a fraction of the one immediately preceding it, and the imperfect repair time as well as cost increases as the number of imperfect repairs increases. The long-run expected maintenance cost rates and corresponding asymptotic average availabilities for these three models are derived. The optimum maintenance policies subject to maintenance time are discussed. Some constraint optimization problems related to maintenance cost rate and availability are presented. Finally, numerical examples are given.     

Some replacement policies with minimal repairs and repair cost limit

Some extended replacement policies based on the number of failures, incorporating the concept of repair cost limit are discussed. Three models are considered as follows: (a) a unit is replaced at the nth failure, or when the estimated minimal repair cost exceeds a particular limit c; (b) a unit has two types of failures and is replaced at the nth type 1 failure, or type 2 failure, or when the estimated repair cost of type 1 failures exceeds a predetermined limit c—type 1 failures are minimal; failures, type 2 failures are catastrophic failures and both occur with constant probability; (c) a unit has two types of failures and the type 1 and type 2 failures are age dependent—the unit is replaced at the nth type 1 failure, type 2 failure, or when the estimated repair cost due to type 1 failures exceeds a predetermined limit c. Introducing costs due to replacements, inspections, and minimal repairs, an optimal number of minimal repairs before replacement is obtained, which minimizes the expected cost rate. Some particular cases are also derived. Finally, the application of these models to computer science is discussed.     

Determining the Proper Number and Price of Software Licenses

Software houses sell their products by transferring usage licenses of various software components to the customers. Depending on the kind of software, there are several different license types that allow controlled access of services. The two most popular types are the fixed license, which gives access rights for an identified workstation, and the floating license, which restricts the number of simultaneous users to a certain bound. The latter of these types is advantageous when the users do not demand full-time services and occasional lack of access is bearable. The problem of deciding the number of floating licenses is studied in the present paper. Based on the expected usage profile of the software, we calculate the minimal number of licenses that guarantees that the customers get service better than a given lower bound. The problem is studied by using certain queuing models, known as the Erlang toss system, the Erlang delay system, and the Engset model. None of these analytic models consider, however, the transient period that we analyze by means of simulation and by the so-called modified offered load approximation. We also give simple formulas presenting how the number of software licenses needed to keep the probability of nonaccess below a given blocking level grows as a function of the offered load, which is the proportion of the time used in the case that all requests were successful. Results of the study may be used for setting license prices and for determining the proper number of licenses.     

Performance bounds on the splitting algorithm for binary testing

Summary In machine fault-location, medical diagnosis, species identification, and computer decisionmaking, one is often required to identify some unknown object or condition, belonging to a known set of M possibilities, by applying a sequence of binary-valued tests, which are selected from a given set of available tests. One would usually prefer such a testing procedure which minimizes or nearly minimizes the expected testing cost for identification. Existing methods for determining a minimal expected cost testing procedure, however, require a number of operations which increases exponentially with M and become infeasible for solving problems of even moderate size. Thus, in practice, one instead uses fast, heuristic methods which hopefully obtain low cost testing procedures, but which do not guarantee a minimal cost solution. Examining the important case in which all M possibilities are equally likely, we derive a number of cost-bounding results for the most common heuristic procedure, which always applies next that test yielding maximum information gain per unit cost. In particular, we show that solutions obtained using this method can have expected cost greater than an arbitrary multiple of the optimal expected cost.The authors are indebted to R. L. Rivest for simplying the original proof of Theorem 1 and to P. J. Burke for his many valuable comments.     

通用公式运算脚本引擎设计与实现

很多大型应用系统都需要处理各种公式,目前的主流做法是提供公式库,供用户从中选择。这种处理方式增加了系统维护成本。为了解决这个问题,开发了一种通用的公式运算脚本语言,终端用户可以输入任意符合语法规范的公式,从而取消了公式库。     

Topological design of a distributed computer communication network in a noisy environment

The effect of noisy links is considered in the design of a computer communication network topology. Because of noisy links, and the consequent probability of bit error, additional network traffic in the form of acknowledgement packets and retransmission packets are generated which load the network. A topological design procedure for obtaining a minimum cost network is proposed which satisfies given constraints of overall network delay, maximum delay on a link, throughput and reliability. Traffic priority for different classes of traffic is also taken into consideration in the design. As expected, the network cost increases as the bit error probability of the links increases.     

三层客户/服务计算技术研究及其应用

对三层客户/服务计算技术及其相关技术进行了深入的研究,提出了几种新的负载均衡模型与算法,研究了三层数据库所需数据库服务器和中间应用服务器数目的确定方法,提出了一些WebQoS服务性能优化的策略,并将所取得的研究成果应用于商品身份数码识别系统等软件的工程开发中,应用效果良好。     

Optimal number of minimal repairs with cumulative repair cost limit for a two-unit system with failure rate interactions

A discrete replacement model is presented that includes a cumulative repair cost limit for a two-unit system with failure rate interactions between the units. We assume a failure in unit 1 causes the failure rate in unit 2 to increase, whereas a failure in unit 2 causes a failure in unit 1, resulting in a total system failure. If unit 1 fails and the cumulative repair cost till to this failure is less than a limit L, then unit 1 is repaired. If there is a failure in unit 1 and the cumulative repair cost exceeds L or the number of failures equals n, the entire system is preventively replaced. The system is also replaced at a total failure, and such replacement cost is higher than the preventive replacement cost. The long-term expected cost per unit time is derived using the expected costs as the optimality criterion. The minimum-cost policy is derived, and existence and uniqueness are proved.     

Computer aided design of unit loads

The unit load design problem includes the selection of the best pallet or container size, the best pallet or container layout, and the best number of parta per pallet or container. Three different approaches to solve the unit load design problem are identified in this paper and a new procedure is proposed: Computer Aided Design of Unit Loads (CADUL I). Using CADUL I, unit loads are designed considering system constraints (i.e., rack opening dimensions, aisle width, trailer-truck container dimensions, product crushability constraints, material handling equipment stacking capability and weight capacity) and a cost function that includes handling, storage, transportation, and pallet or container costs. An example is used to illustrate how CADUL I works and how these approaches to unit load design perform sensitivity analysis to validate the results obtained.     

A stochastic fleet composition problem

In this paper, we consider the problem of forming a new vehicle fleet, consisting of multiple vehicle types, to cater for uncertain future requirements. The problem is to choose the number of vehicles of each type to purchase so that the total expected cost of operating the fleet is minimized. The total expected cost includes fixed and variable costs associated with the fleet, as well as hiring costs that are incurred whenever vehicle requirements exceed fleet capacity. We develop a novel algorithm, which combines dynamic programming and the golden section method, for determining the optimal fleet composition. Numerical results show that this algorithm is highly effective, and takes just seconds to solve large-scale problems involving hundreds of different vehicle types.     

Explicit formulas for the ellipsoids approximating attainability domains

A series of explicit formulas for ellipsoids that estimate from above the attainability domains of linear dynamic systems with geometric constraints on control is obtained. Locally and globally-optimal ellipsoidal estimates in terms of different cost functions are studied. In particular, some essentially nonlinear boundary-value problems connected with seeking ellipsoids that are globally-optimal in volume are solved explicitly. It is shown that the formulas can be used to efficiently implement different passages to the limit, including those of a new type—passage to a limit when the dimension of the phase space of the dynamic system tends to infinity.     

Optimum ordering policies with age-dependent minimal repair and two types of lead times

Two ordering policies for a complex system with age-dependent minimal repair and two types of lead times are considered. Introducing costs due to ordering, repairs, shortage and holding, the expected cost per unit time is derived in the long run as a criterion of optimality and the optimum ordering policies found by minimizing that cost. We show that, under certain conditions, there exists a finite and unique optimum policy. Various special cases are discussed.     

Optimal number of repairs before replacement for a two-unit system subject to non-homogeneous pure birth process

We consider a discrete replacement model for a two-unit system subject to failure rate interaction and shocks. Two types of shocks occur according to a non-homogeneous pure birth process and can affect the two-unit system. Type I shock causes unit A to fail and can be rectified by a general repair, while type II shock results in a non-repairable failure and must be fixed by a replacement. Two-unit systems also exhibit failure rate interactions between the units: each failure of unit A causes some damage to unit B, while each failure of unit B causes unit A into an instantaneous failure. The occurrence of a particular type of shock is dependent on the number of shocks occurred since the last replacement. The objective of this paper is to determine the optimal number of minor failures before replacement that minimizes the expected cost rate. A numerical example is presented to illustrate application of the model.