Performance impacts of autocorrelated flows in multi-tiered systems

This paper presents an analysis of the performance effects of burstiness in multi-tiered systems. We introduce a compact characterization of burstiness based on autocorrelation that can be used in capacity planning, performance prediction, and admission control. We show that if autocorrelation exists either in the arrival or the service process of any of the tiers in a multi-tiered system, then autocorrelation propagates to all tiers of the system. We also observe the surprising result that in spite of the fact that the bottleneck resource in the system is far from saturation and that the measured throughput and utilizations of other resources are also modest, user response times are very high. When autocorrelation is not considered, this underutilization of resources falsely indicates that the system can sustain higher capacities.

We examine the behavior of a small queuing system that helps us understand this counter-intuitive behavior and quantify the performance degradation that originates from autocorrelated flows. We present a case study in an experimental multi-tiered Internet server and devise a model to capture the observed behavior. Our evaluation indicates that the model is in excellent agreement with experimental results and captures the propagation of autocorrelation in the multi-tiered system and resulting performance trends. Finally, we analyze an admission control algorithm that takes autocorrelation into account and improves performance by reducing the long tail of the response time distribution.     

Pricing and capacity decisions for non-profit internet service providers

Many universities and other non-profit organizations started Internet dial-up access as a value-added service to their respective communities. The implementation and maintenance of these services becomes a nontrivial task, requiring large annual budgets to keep these systems up and running. The mandate for these non-profit entities is to recover the costs of providing their value added services in the long run while maintaining a guaranteed quality of service (QoS) level. The pricing and capacity planning problem of the non-profit Internet Service Providers (ISPs) has three difficult aspects. First, pricing based on cost recovery has inherent challenges. Second, the non-profit ISPs have to tackle the growth of unpredictable demand that calls for continuous capacity expansion. Third, capacity expansion in terms of Internet dial-up lines comes only in bulk units which typically exhibit economy of scale characteristics. Another critical issue of capacity expansion is the timing of the expansion since the installation of production-mode capacity requires lead-time. This paper proposes a Busiest-Minute Planning Model (BMPM) for the non-profit ISPs to effectively solve the aforementioned issues. The BMPM model provides non-profit ISPs a mechanism to determine the optimum capacity for a given QoS level. The mechanism can predict when existing capacity becomes saturated by taking into account the desired QoS and future demand change. The BMPM model proposed in this paper was tested using data from a non-profit ISP—The Northeast Regional Data Center (NERDC) of the State of Florida. The results suggest that our BMPM model is very effective in solving the pricing and capacity expansion decisions of NERDC and can be applied to other non-profit ISPs.     

Developing a maturity model for service systems in heavy equipment manufacturing enterprises

Heavy equipment manufacturing firms are increasingly challenged by the integration of service planning and execution in their established product-centred information systems (IS) environment. Despite a few standardisation efforts, there is no common understanding of service systems in industry goods companies and the corresponding requirements for the appropriation of information systems. We address this need by developing a maturity model. The design of the model is grounded in extant literature, focus group and case study research involving eleven organisations over 1.5 years. The evaluation confirms that the maturity model makes a novel and useful contribution to the design of service systems.     

On the impact of analyzing customer information and prioritizing in a service system

This paper examines prioritization in a service system and analyzes whether, in the presence of heterogeneous customers who have different needs and a costly sorting process, it pays to prioritize. In particular, in our model, sorting is costly because the task of gathering information to prioritize jobs consumes resources. We investigate a stylized model in which there are two classes of jobs — one whose waiting cost is high, called urgent, and the other whose waiting cost is low, called non-urgent. There are two types of employees, sorters, who collect information on a job and then decide whether it is urgent or non-urgent, and processors, who execute the job or provide the service. We begin by assuming that sorters categorize customers perfectly, and we relax this assumption later in the paper. We optimize two performance metrics, waiting costs (under a given budget) and total costs, and find the conditions under which prioritization is beneficial for these two metrics.     

The activity-based aggregate production planning with capacity expansion in manufacturing systems

This paper builds a mixed integer linear programming (MILP) model to mathematically characterize the problem of aggregate production planning (APP) with capacity expansion in a manufacturing system including multiple activity centers. We use the heuristic based on capacity shifting with linear relaxation to solve the model. Two linear relaxations, i.e., a complete linear relaxation (CLR) on all the integer variables and a partial linear relaxation (PLR) on part of the integer variables are investigated and compared in computational experiments. The computational results show that the heuristic based on the capacity shifting with CLR is very fast but yields low-quality solution whereas the capacity shifting with PLR provides high-quality solutions but at the cost of considerable computational time. As a result, we develop a hybrid heuristic combining beam search with capacity shifting, which is capable of producing a high-quality solution within reasonable computational time. The computational experiment on large-scale problems suggests that when solving a practical activity-based APP model with capacity expansion at the industrial level, the capacity shifting with CLR is preferable, and the beam search heuristic could be subsequently utilized as an alternative if the relaxation gap is larger than the acceptable deviation.     

Waiting time distribution in a class of discrete-time cyclic service multi-queue systems

A new approximate method is developed for finding the waiting and sojourn time distributions in a class of multi-queue systems served in cyclic order at discrete intervals. An immediate application for such a model is in communication networks where a number of different traffic sources compete to access a group of transmission channels operating under a time-slotted sharing policy. This system maps naturally onto a model in which the inter-visit time has a probability mass function of phase-type. We derive a set of matrix equations with easily tractable iterative procedures for their solution and controllable accuracy in their numerical evaluation. We then validate the analytical model against simulation and discuss the validity of the assumptions. This methodology can be extended to several other polling strategies.     

Bounding approaches for operation assignment and capacity allocation problem in flexible manufacturing systems

This study considers an operation assignment and capacity allocation problem that arises in flexible manufacturing systems. Automated machines are assumed to have scarce time and tool magazine capacities and the tools are available in limited quantities. The aim is to select a subset of operations with maximum total weight. The weight of an operation may represent its profit, processing load, relative priority. Several upper bounding procedures have been taken into account. The results of computational tests have revealed that the proposed upper bounding procedures produce satisfactory solutions in reasonable CPU times. We suggest using some of the bounds when the quality of the solutions is more important than the speed of achieving them and some others when the speed is more important than the quality.     

Beam search algorithm for capacity allocation problem in flexible manufacturing systems

This study considers the operation assignment and tool allocation problem in flexible manufacturing systems. A set of operations together with their required tools are selected so as to maximize the total weight. The machines have limited time and tool magazine capacities and the tools are available in limited quantities. We develop a beam search algorithm and obtain near optimal solutions for large size problems very quickly.     

Dual time-scale distributed capacity allocation and load redirect algorithms for cloud systems

Resource management remains one of the main issues of cloud computing providers because system resources have to be continuously allocated to handle workload fluctuations while guaranteeing Service Level Agreements (SLA) to the end users. In this paper, we propose novel capacity allocation algorithms able to coordinate multiple distributed resource controllers operating in geographically distributed cloud sites. Capacity allocation solutions are integrated with a load redirection mechanism which, when necessary, distributes incoming requests among different sites. The overall goal is to minimize the costs of allocated resources in terms of virtual machines, while guaranteeing SLA constraints expressed as a threshold on the average response time. We propose a distributed solution which integrates workload prediction and distributed non-linear optimization techniques. Experiments show how the proposed solutions improve other heuristics proposed in literature without penalizing SLAs, and our results are close to the global optimum which can be obtained by an oracle with a perfect knowledge about the future offered load.     

Determining the prices of remanufactured products,capacity of internal workstations and the contracting strategy within queuing framework

This paper studies a remanufacturing facility with several types of incoming nonconforming products and different independent remanufacturing workstations. The workstations have limited capacities so that an outsourcing strategy can be practiced. Each workstation is modeled with an M/M/1/k queuing system considering k as a decision variable. Additionally, a binary decision variable is taken into account to determine the contracting strategy along with some decision variables for the prices of remanufactured products. Thus, a bi-objective mixed-integer nonlinear programming is built to obtain optimal values of the decision variables. The first objective attempts to maximize the total profit and the second minimizes the average length of queuing at workstations. To solve the complex bi-objective mixed-integer nonlinear programming problem, the best out of six multi-objective decision-making (MODM) methods is selected in order to make the bi-objective optimization problem a single-objective one. Afterward, a genetic algorithm (GA) is developed to find a near-optimum solution of the single-objective problem. Besides, all of the important parameters of the algorithm are calibrated using regression analysis. To validate the results obtained, the solutions of some test problems are compared to the ones obtained by the GAMS software. The applicability of the proposed model and the solution procedure are shown with an illustrative example.     

An architecture for rapid, on-demand service composition

Legacy application design models, which are still widely used for developing context-aware applications, incur important limitations. Firstly, embedding contextual dependencies in the form of if–then rules specifying how applications should react to context changes is impractical to accommodate the large variety of possibly even unanticipated context types and their values. Additionally, application development is complicated and challenging, as programmers have to manually determine and encode the associations of all possible combinations of context parameters with application behaviour. In this paper we propose a framework for building context aware applications on-demand, as dynamically composed sequences of calls to services. We present the design and implementation of our system, which employs goal-oriented inferencing for assembling composite services, dynamically monitors their execution, and adapts applications to deal with contex- tual changes. We describe the failure recovery mechanisms we have implemented, allowing the deployment of the system in a non-perfect environment, and avoiding the delays inherent in re-discovering a suitable service instance. By means of experimental evaluation in a realistic infotainment application, we demonstrate the potential of the proposed solution an effective, efficient, and scalable approach. This work was supported by IBM Zurich Research Laboratory.     

Integrated pricing and capacity decision for a telecommunication service provider

This paper studies a price and capacity decision for a telecommunications service provider that differentiates its products based on price and quality of service to maximize revenue. We assume the market is segmented into two customer classes. Time sensitive customers are willing to pay a price premium for a shorter service time, while price sensitive customers are willing to accept a longer service time in return for a lower price. The service provider offers products and services that differ only in their guaranteed service times and prices. We first develop a mathematical model to determine the optimal product price and optimal capacity necessary for maximizing total profit. We then consider a case where a service provider can marginally increase or decrease the capacity, and compute the optimal price and optimal capacity.     

Observers design for linear time-delay systems

In this contribution we propose a simple and useful approach to design observers for discrete-time systems with delays in the state and output variables. The main feature is that the necessary and sufficient conditions for the existence of such observer are derived. The stability analysis is performed by the Lyapunov approach, where the obtained conditions are expressed in terms of a modified Riccati equation. Numerical examples are provided to show efficiency of the proposed observer.     

Minimum-energy control for time-varying systems with multiple state and input delays

This paper considers the minimum-energy control problem for a class of time-varying systems with multiple state and input delays. First, a state transform matrix is presented. By using the transform matrix, a system with multiple state and input delays is converted to a formal equivalent one without delay. Then, the optimal problem of the novel system is solved by using the maximum principle. Analytical expressions of the optimal control law and optimal performance are given by two formulas with respect to the state transform matrix. At last, an algorithm is given to solve the analytical expression of the state transform matrix. Simulation results show that the design algorithm is efficient and easy to implement.     

Distributed output regulation for linear multi-agent systems with communication delays

In this paper, a distributed output regulation approach is presented for the cooperative control of linear multi-agent systems in the presence of communication delays. Both dynamic state and output feedback control laws are designed for achieving the property of output regulation. Sufficient conditions for the existence of these control laws are provided in terms of linear matrix inequalities. Simulation results are given to support the efficiency of the proposed distributed output regulation approach.     

Optimizing the size and locations of facilities in competitive multi-site service systems

We propose a multi-site location-allocation model for selecting locations in competitive service systems. Examples are typical franchise systems or retailers with multiple outlets. The proposed objective function maximizes a measure of spatial utility of users subject to constraints on waiting time of users and budget of the multi-site facility owners. The intent is to provide model support in assisting with decisions by one multi-facility owner about locating new sites or closing current sites in the presence of one or more competitors, each of which control several sites. Algorithms and spatial data necessary for solving the problem are described. The model is described in the context of locating bank branches though it is applicable in many other contexts.     

Stability and robust stability for systems with a time-varying delay

To concern the stability and robust stability criteria for systems with time-varying delays, this note uses not only the time-varying-delayed state x(t-h(t)) but also the delay-upper-bounded state to exploit all possible information for the relationship among a current state x(t), an exactly delayed state x(t-h(t)), a marginally delayed state , and the derivative of the state , when constructing Lyapunov-Krasovskii functionals and some appropriate integral inequalities, originally suggested by Park (1999. A delay-dependent stability criterion for systems with uncertain time-invariant delays. IEEE Transactions on Automatic Control, 44(4), 876-877). Two fundamental criteria are provided for the cases where no bound of delay derivative is assumed and where an upper bound of delay derivative is assumed. Examples show the resulting criteria outperform all existing ones in the literature.     

A bargaining-specific architecture for supporting automated service agreement negotiation systems

The provision of services is often regulated by means of agreements that must be negotiated beforehand. Automating such negotiations is appealing insofar as it overcomes one of the most often cited shortcomings of human negotiation: slowness. Our analysis of the requirements of automated negotiation systems in open environments suggests that some of them cannot be tackled in a protocol-independent manner, which motivates the need for a protocol-specific architecture. However, current state-of-the-art bargaining architectures fail to address all of these requirements together. Our key contribution is a bargaining architecture that addresses all of the requirements we have identified. The definition of the architecture includes a logical view that identifies the key architectural elements and their interactions, a process view that identifies how the architectural elements can be grouped together into processes, a development view that includes a software framework that provides a reference implementation developers can use to build their own negotiation systems, and a scenarios view by means of which the architecture is illustrated and validated.     

多输入多输出非线性多时滞系统的直接自适应模糊跟踪控制

针对多输入多输出非线性多时滞系统,提出了一种直接自适应模糊跟踪控制方案．该方案有机综合了自适应控制和H∞ 控制,构建了一种自适应时滞模糊逻辑系统用来逼近有多重时滞的未知函数;设计了H∞ 补偿器来抵消模糊逼近误差和外部扰动．根据跟踪误差给出了参数调节规律,构造了包含时滞的李亚普诺夫函数,从而证明了误差闭环系统满足期望的H∞ 跟踪性能．仿真结果表明了该方案的可行性．