Randomized approximation scheme for resource allocation in hybrid-cloud environment

Using the virtually unlimited resource capacity of public cloud, dynamic scaling out of large-scale applications is facilitated. A critical question arises practically here is how to run such applications effectively in terms of both cost and performance. In this paper, we explore how resources in the hybrid-cloud environment should be used to run Bag-of-Tasks applications. Having introduced a simple yet effective objective function, our algorithm helps the user to make a better decision for realization of his/her goal. Then, we cope with the problem in two different cases of “known” and “unknown” running time of available tasks. A solution to approximate the optimal value of user’s objective function will be provided for each case. Specifically, a fully polynomial-time randomized approximation scheme based on a Monte Carlo sampling method will be presented in case of unknown running time. The experimental results confirm that our algorithm approximates the optimal solution with a little scheduling overhead.     

Optimal location query based on k nearest neighbours

Optimal location query in road networks is a basic operation in the location intelligence applications. Given a set of clients and servers on a road network, the purpose of optimal location query is to obtain a location for a new server, so that a certain objective function calculated based on the locations of clients and servers is optimal. Existing works assume no labels for servers and that a client only visits the nearest server. These assumptions are not realistic and it renders the existing work not useful in many cases. In this paper, we relax these assumptions and consider the k nearest neighbours (KNN) of clients. We introduce the problem of KNN-based optimal location query (KOLQ) which considers the k nearest servers of clients and labeled servers. We also introduce a variant problem called relocation KOLQ (RKOLQ) which aims at relocating an existing server to an optimal location. Two main analysis algorithms are proposed for these problems. Extensive experiments on the real road networks illustrate the efficiency of our proposed solutions.     

Uniform tree approximation by global optimization techniques

In this paper we present adaptive algorithms for solving the uniform continuous piecewise affine approximation problem (UCPA) in the case of Lipschitz or convex functions. The algorithms are based on the tree approximation (adaptive splitting) procedure. The uniform convergence is achieved by means of global optimization techniques for obtaining tight upper bounds of the local error estimate (splitting criterion). We give numerical results in the case of the function distance to 2D and 3D geometric bodies. The resulting trees can retrieve the values of the target function in a fast way.     

Interprocessor communication with limited memory

Many parallel applications require periodic redistribution of workloads and associated data. In a distributed memory computer, this redistribution can be difficult if limited memory is available for receiving messages. We propose a model for optimizing the exchange of messages under such circumstances which we call the minimum phase remapping problem. We first show that the problem is NP-complete, and then analyze several methodologies for addressing it. First, we show how the problem can be phrased as an instance of multicommodity flow. Next, we study a continuous approximation to the problem. We show that this continuous approximation has a solution which requires at most two more phases than the optimal discrete solution, but the question of how to consistently obtain a good discrete solution from the continuous problem remains open. We also devise a simple and practical approximation algorithm for the problem with a bound of 1.5 times the optimal number of phases. We also present an empirical study of variations of our algorithms which indicate that our approaches are quite practical.     

Splitting Methods for Three-Dimensional Transport Models with Interaction Terms

We investigate the use of splitting methods for the numerical integration of three-dimensional transport-chemistry models. In particular, we investigate various possibilities for the time discretization that can take advantage of the parallelization and vectorization facilities offered by multi-processor vector computers. To suppress wiggles in the numerical solution, we use third-order, upwind-biased discretization of the advection terms, resulting in a five-point coupling in each direction. As an alternative to the usual splitting functions, such as co-ordinate splitting or operator splitting, we consider a splitting function that is based on a three-coloured hopscotch-type splitting in the horizontal direction, whereas full coupling is retained in the vertical direction. Advantages of this splitting function are the easy application of domain decomposition techniques and unconditional stability in the vertical, which is an important property for transport in shallow water. The splitting method is obtained by combining the hopscotch-type splitting function with various second-order splitting formulae from the literature. Although some of the resulting methods are highly accurate, their stability behaviour (due to horizontal advection) is quite poor. Therefore we also discuss several new splitting formulae with the aim to improve the stability characteristics. It turns out that this is possible indeed, but the price to pay is a reduction of the accuracy. Therefore, such methods are to be preferred if accuracy is less crucial than stability; such a situation is frequently encountered in solving transport problems. As part of the project TRUST (Transport and Reactions Unified by Splitting Techniques), preliminary versions of the schemes are implemented on the Cray C98 4256 computer and are available for benchmarking.     

互联网信息组织和规划中的带拒绝装箱问题

讨论如下定义的带拒绝装箱问题：设有许多等长的一维箱子，给定一个物品集，每个物品有两个参数：长度和罚值．物品可以放入箱子也可被拒绝放入箱子．如果将物品放入箱子，则使该箱剩余长度减少．一旦需将某一物品放入某一箱中，而该箱的剩余长度不够时，则需启用新箱子．如果物品被拒绝放入任何箱中，则产生惩罚．问怎样安排物品使所用箱子数与未装箱的物品总罚值之和最小．该问题是一个新的组合优化问题，来源于内部互联网的信息组织和规划．该文首先给出一个最优解值的下界估计，它可用于分枝定界法求最优解．由于该问题是强NP-难的，该文进一步研究它的离线和在线近似算法的设计与分析．文中给出一个离线算法，其绝对性能比为2；同时给出一个在线算法，其绝对性能比不超过3，渐近性能比为2，还对算法性能比的下界进行了讨论．     

Truss topology optimization with discrete design variables—Guaranteed global optimality and benchmark examples

This paper considers the problem of optimal truss topology design subject to multiple loading conditions. We minimize a weighted average of the compliances subject to a volume constraint. Based on the ground structure approach, the cross-sectional areas are chosen as the design variables. While this problem is well-studied for continuous bar areas, we consider in this study the case of discrete areas. This problem is of major practical relevance if the truss must be built from pre-produced bars with given areas. As a special case, we consider the design problem for a single available bar area, i.e., a 0/1 problem. In contrast to the heuristic methods considered in many other approaches, our goal is to compute guaranteed globally optimal structures. This is done by a branch-and-bound method for which convergence can be proven. In this branch-and-bound framework, lower bounds of the optimal objective function values are calculated by treating a sequence of continuous but non-convex relaxations of the original mixed-integer problem. The main effect of using this approach lies in the fact that these relaxed problems can be equivalently reformulated as convex problems and, thus, can be solved to global optimality. In addition, these convex problems can be further relaxed to quadratic programs for which very efficient numerical solution procedures exist. By exploiting this special problem structure, much larger problem instances can be solved to global optimality compared to similar mixed-integer problems. The main intention of this paper is to provide optimal solutions for single and multiple load benchmark examples, which can be used for testing and validating other methods or heuristics for the treatment of this discrete topology design problem.     

A new order splitting model with stochastic lead times for deterioration items

In unreliable supply environments, the strategy of pooling lead time risks by splitting replenishment orders among multiple suppliers simultaneously is an attractive sourcing policy that has captured the attention of academic researchers and corporate managers alike. While various assumptions are considered in the models developed, researchers tend to overlook an important inventory category in order splitting models: deteriorating items. In this paper, we study an order splitting policy for a retailer that sells a deteriorating product. The inventory system is modelled as a continuous review system (s, Q) under stochastic lead time. Demand rate per unit time is assumed to be constant over an infinite planning horizon and shortages are backordered completely. We develop two inventory models. In the first model, it is assumed that all the requirements are supplied by only one source, whereas in the second, two suppliers are available. We use sensitivity analysis to determine the situations in which each sourcing policy is the most economic. We then study a real case from the European pharmaceutical industry to demonstrate the applicability and effectiveness of the proposed models. Finally, more promising directions are suggested for future research.     

Routing in sparse splitting optical networks with multicast traffic

In this paper, we investigate the problem of Multicast Routing in Sparse Splitting Networks (MR-SSN). Given a network topology with the multicast capable nodes distributed uniformly throughout the network, and a multicast session, the MR-SSN problem is to find a route from the source node of the multicast session to all destinations of the multicast session such that the total number of fibers used in establishing the session is minimized. In this paper, we develop a rerouting algorithm for a given Steiner tree, which makes it feasible to route a multicast session using a tree-based solution in sparse light splitting optical networks. In addition, we present a heuristic based on Tabu Search (TS) that requires only one transmitter for the source node and one wavelength for each multicast session. To evaluate the performance of heuristics, we formulate the MR-SSP problem as an integer linear program (ILP), and optimally solve small instances using the commercially available linear solver, CPLEX. We test our heuristic on a wide range of network topologies. Our experimental results show that: (1) The difference between our solution and ILP optimal solution, in terms of the number of fibers used for establishing a multicast session, is within 10% in almost all the instances and within 5% in about half of the instances. (2) The average delay, taken over all destination nodes, falls within three times the optimal value. (3) A sparse light splitting all-optical network with 30% of multicast capable cross-connects has an acceptable low cost and relatively good performance. (4) The improvement achieved by TS heuristic increases considerably when the session size is large, the number of Splitter-and-Delivery cross-connects is small, and the network connectivity is dense.     

互联网通信中的信息选取与分布问题的建模与求解

讨论了互联网通信中的一个信息选取与规划问题。由于内部网的单个Web服务器容量不够大,不能容纳与日剧增的信息内容,如何将众多的信息分布到多个Web服务器上,使得每个服务器上存放的信息总量不超过各个服务器容量且避免访问瓶颈的发生;这是陈卫东等1999年提出的一个新问题,该文建立了该问题的一个优化新模型,在讨论了它的强NP－完全性,难近似性后,给出了一个伪多项式时间最优算法的一个多项式时间近似算法。     

VoD on steroids : Optimized content delivery using distributed video servers over best-effort Internet

This paper addresses the problem of delivering a long-duration continuous media document, typically a movie, over unreliable communication links like the ones that make up the Internet. Packet loss/drop is one of the main problems that plague Internet's use for offering multimedia services. The framework presented here addresses analytically this problem by offering closed-form solutions for partitioning and scheduling the delivery of a document by multiple spatially distributed servers. The goal is to offer uninterrupted playback to clients while minimizing their access-time.The solid mathematical foundation presented, enables the study of multi-server document delivery using unreliable communications for both CBR and VBR media. It is also shown how slow connections that would otherwise prevent the deployment of Movie-on-Demand class services, could be used to offer such services in an optimal manner. The paper also addresses the problem of optimally arranging the available servers.A rigorous simulation study that explores the potential of the proposed approach concludes the paper. Our simulations show a super-linear speedup in access-times and also the robustness of the proposed scheme, capable of handling unknown network conditions by shifting server “load”.     

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.     

虚拟机资源分配的非合作博弈标价模型

基于非合作博弈理论,提出虚拟机资源分配的标价模型,该模型设计了各虚拟机的效益函数,同时利用该函数的最优反应函数,优化各博弈参与者对资源的标价。在效益函数零点无定义下,给出虚拟机标价最优解的唯一性和最优性证明。在满足服务质量条件下,利用优化后的标价按比例分配资源,使资源在各虚拟机之间公平分配,以提高虚拟资源利用率,保证用户的响应时间。仿真实验表明,提出的模型是有效合理的。     

Bounded parallel-batch scheduling on single and multi machines for deteriorating jobs

We consider the bounded parallel-batch scheduling problem in which the processing time of a job is a simple linear function of its starting time. The objective is to minimize the makespan. When the jobs have identical release dates, we present an optimal algorithm for the single-machine problem and an fully polynomial-time approximation scheme for the parallel-machine problem. When the jobs have distinct release dates, we show that the single-machine problem is NP-hard and present an optimal algorithm for one special case.     

A class of multi-server queueing system with server failures

A multi-server queueing system with identical unreliable servers with phase type distributed service times is considered. The servers are subject to random breakdowns and repairs when a repair person is available. We consider both the cases of infinite and finite buffers. Job arrivals are Poisson and server inter-failure and repair times follow exponential distributions. The infinitesimal generator matrix has a block tri-diagonal structure. The stability condition for the infinite case and the loss probability for the finite buffer case are obtained. We use a matrix-geometric approach to analyze the infinite buffer problem. Numerical examples are presented for both cases.     

Wavelet Neural Network employment for continuous GNSS orbit function construction: Application for the Assisted-GNSS principle

This paper presents a Wavelet Neural Network (WNN) employment for discrete precise ephemerides tabular data of Global Navigation Satellite System (GNSS) orbit approximation to obtain continuous orbit function. Orbit function is essential in positioning and navigation tasks, the advantage of continuity, however, is that it can also be used during GNSS signal interruptions. The essence of WNN continuous orbit construction is single function determination for the entire interval, while the interpolation methods follow several discrete function establishment. Specifically, we investigate the performance of the WNN continuous orbit approximation by comparison with well known polynomial and trigonometric interpolations. The experimental results show that our proposed method is superior to the traditional methods especially near the end of intervals, because they are not subject to large scale function oscillations as in the case of polynomials constructions. We propose a WNN construction using different mother functions of the WNN namely Mexican hat, Morlet function, Gaussian and Daubechies (D4) wavelet. Furthermore best algorithm for regression estimation is described; selection of neurons in the hidden layer of WNN is based on orthogonal least squares algorithm. The main objective of this article is to show that the presented method of orbit function construction could be used for GNSS ephemerides distribution and short-time prediction in the Assisted GNSS-networks.     

模型辅助的计算费时进化高维多目标优化

代理模型能够辅助进化算法在计算资源有限的情况下加快找到问题的最优解集,因此建立高效的代理模型辅助多目标进化搜索逐渐受到了重视.然而随着目标数量的增加,对每个目标分别建立高斯过程模型时个体整体估值的不确定度会随之增加.因此通过对模型最优解集的搜索探索原问题潜在的非支配解集,并基于个体的收敛性,种群的多样性和估值的不确定度...     

A Truthful Mechanism for Value-Based Scheduling in Cloud Computing

We introduce a novel pricing and resource allocation approach for batch jobs on cloud systems. In our economic model, users submit jobs with a value function that specifies willingness to pay as a function of job due dates. The cloud provider in response allocates a subset of these jobs, taking into advantage the flexibility of allocating resources to jobs in the cloud environment. Focusing on social-welfare as the system objective (especially relevant for private or in-house clouds), we construct a resource allocation algorithm which provides a small approximation factor that approaches 2 as the number of servers increases. An appealing property of our scheme is that jobs are allocated non-preemptively, i.e., jobs run in one shot without interruption. This property has practical significance, as it avoids significant network and storage resources for checkpointing. Based on this algorithm, we then design an efficient truthful-in-expectation mechanism, which significantly improves the running complexity of black-box reduction mechanisms that can be applied to the problem, thereby facilitating its implementation in real systems.     

Infinite-horizon models for inventory control under yield uncertainty and disruptions

We consider a firm facing supply chain risk in two forms: disruptions and yield uncertainty. We demonstrate the importance of analyzing a sufficiently long time horizon when modeling inventory systems subject to supply disruptions. Several previous papers have used single-period newsboy-style models to study supply disruptions, and we show that such models underestimate the risk of supply disruptions and generate sub-optimal solutions. We consider one case where a firm's only sourcing option is an unreliable supplier subject to disruptions and yield uncertainty, and a second case where a second, reliable (but more expensive) supplier is available. We develop models for both cases to determine the optimal order and reserve quantities. We then compare these results to those found when a single-period approximation is used. We demonstrate that a single-period approximation causes increases in cost, under-utilizes the unreliable supplier, and distorts the order quantities that should be placed with the reliable supplier in the two-supplier case. Moreover, using a single-period model can lead to selecting the wrong strategy for mitigating supply risk.     

Optimal buffer allocation of serial production lines with quality inspection machines

Using Taylor series expansion and probability generating function technique, we present an approximation method for the analysis of the average steady state throughput of serial production lines with unreliable machines, finite buffers and quality inspection machines. Employing the approximation method, we propose an analytic method for the optimal buffer allocation to achieve a desired throughput. The proposed methods are validated by computer simulations.