Parallel machine scheduling with multiple unloading servers

We study a parallel machine scheduling problem with multiple unloading servers. After a machine completes processing one job, an unloading server is needed to remove the job from the machine. Only after unloading, the machine is available for processing the next job. The model is motivated by the milk run operations of a logistics company that faces limited unloading docks at the warehouse. Our interest is to minimize the total completion time of the jobs. We show that the shortest-processing-time-first (SPT) algorithm has a worst-case bound of 2. We also develop other improved heuristic algorithms as well as a branch-and-bound algorithm to solve the problem. Computational experiments show that our algorithms are efficient and effective.     

多服务员时两种等待队列性能的比较

利用排队论的相关知识,对计算机系统中常见的多服务员情况下的排队现象进行分析,通过理论推导、并用实际数据表明了在多服务员模式下,单一共享的排队等待队列的性能要优于多个独自的排队等待队列。     

Scheduling soft real-time jobs over dual non-real-time servers

In this paper, we consider soft real-time systems with redundant off-the-shelf processing components (e.g., CPU, disk, network), and show how applications can exploit the redundancy to improve the system's ability of meeting response time goals (soft deadlines). We consider two scheduling policies, one that evenly distributes load (Balance), and one that partitions load according to job slackness (Chop). We evaluate the effectiveness of these policies through analysis and simulation. Our results show that by intelligently distributing jobs by their slackness amount the servers, Chop can significantly improve real-time performance     

Approximate analysis of multiqueue systems with multiple cyclic servers

In this paper we consider an approximate model of a system of multiple queues served cyclically by a number of identical servers, which is an extension of the Kuehn model for the single server multiqueueing system. The arrival process of customers is Poissonian, walking and service times are general, servers work in the repeated mode, and they serve at most one customer per visit at a queue (node) in a cycle. Applications in the performance evaluation of the existent network of processors of the Brazilian switching system TRÓPICO are considered. The approximation is validated by means of computer simulations.     

Proxy-assisted periodic broadcast for video streaming with multiple servers

Large scale video streaming over the Internet requires a large amount of resources such as server I/O bandwidth and network bandwidth. A number of video delivery techniques can be used to lower these requirements. Periodic broadcast by a central server combined with proxy caching offers a significant reduction of the aggregate network and server I/O bandwidth usage. However, the resources available to a single server are still limited. In this paper we propose a system with multiple geographically distributed servers. The problem of multiple servers for periodic broadcast is quite different from the problem of object location for multiple web servers. Multiple servers offer increased amount of resources and service availability and may potentially allow a further reduction of network bandwidth usage. On the other hand, the benefit of periodic broadcast mostly comes from high demand videos. With multiple servers holding a video, the demand of the video at each server is reduced. Therefore, it is a challenge to use multiple servers efficiently. We first analyze the dependence of the resource requirements on the number and locations of the servers. Based on the character of the function describing such a dependence, we formulate and solve the problem of video location and delivery, in a way that minimizes resource usage. We explore a trade-off between network and I/O bandwidth requirements. We evaluate our proposed solutions through a number of tests.

Maximum entropy two-station cyclic queues with multiple general servers

Summary The efficient implementation and extension of various approximate methods for general queueing networks require the study of two-station cyclic queues. In this paper maximum entropy formalism is used to analyse two-station cyclic queues with multiple general servers and a fixed number of jobs. New robust one step recursions for the queue length distribution are derived and asymptotic connections to infinite capacity queues are established. Links with Birth-Death and global balance solutions are determined and extensions to load dependent servers with Bernoulli feedback are presented. Numerical examples provide useful information on how critically system behaviour is affected by the distributional form of service times and simple bounds for typical performance measures such as throughout and mean queue length are defined. Moreover, the utility of the work as a building block for the approximate analysis of a general central server model is demonstrated.Some of the material included in this paper has been orally presented to the International Workshop on Computer Performance Evaluation, 28–30 April 1986, Sophia-Antipolis (INRIA), France [1]This work is jointly supported by Science and Engineering Research Council (SERC), UK and Metron Technology Ltd., UK, under grants GR/D/12422 and GR/AA/772, respectively     

Optimal buffer allocation in finite closed networks with multiple servers

In this study, we present an optimal buffer allocation procedure for closed queueing networks with finite buffers. The performance measures are evaluated using the expanded mean value analysis, and the solution procedure is incorporated into a nonlinear optimization scheme to arrive at the sub-optimal buffer space vector. The effectiveness of the method is demonstrated through several numerical experiments. Discussions on convergence and computational complexity are also included.     

Assigning multiple job types to parallel specialized servers

In this paper methods of mixing decision rules are investigated and applied to the so-called multiple job type assignment problem with specialized servers. This problem is modeled as continuous time Markov decision process. For this assignment problem performance optimization is in general considered to be difficult. Moreover, for optimal dynamic Markov decision policies the corresponding decision rules have in general a complicated structure not facilitating a smooth implementation. On the other hand optimization over the subclass of so-called static policies is known to be tractable. In the current paper a suitable static decision rule is mixed with dynamic decision rules which are selected such that these rules are relatively easy to describe and implement. Some mixing methods are discussed and optimization is performed over corresponding classes of so-called mixing policies. These mixing policies maintain the property that they are easy to describe and implement compared to overall optimal dynamic Markov decision policies. Besides for all investigated instances the optimized mixing policies perform substantially better than optimal static policies.     

A GA-based movie-on-demand platform using multiple distributed servers

In this paper we present the design and explore the performance of a unicast-based distributed system for Movie-on-Demand applications. The operation of multiple servers is coordinated with the assistance of an analytical framework that provides closed-form solutions to the content partitioning and scheduling problem, even under the presence of packet losses. The problem of mapping clients to servers is solved with a genetic algorithm, that manages to provide adequate, near-optimum solutions with a minimum of overhead. While previous studies focused on the static behavior of such a system, i.e. fixed a-priori known number of N servers and K clients commencing operation at the same time instance, this paper focuses on the dynamic behavior of such a system over a period of time with clients coming and going at random intervals. The paper includes a rigorous simulation study that shows how the system behaves in terms of a variety of metrics, including the average access time over all the requested media, in response to differences in the client arrival rate or the consumed server bandwidth. As it is shown, the proposed platform exhibits excellent performance characteristics that surpass traditional approaches that treat clients individually. This has been verified to be true up to extreme system loads, proving the scalability of the proposed content delivery scheme. The significance of our findings also stems from the assumption of unreliable communications, a first for the study of complete systems in this domain.

针对Linux与Oracle的多服务器图形对比监控系统

为了监控并调优基于Linux的Oracle数据库群集,Linux和Oracle的性能数据都需要包含在内,除此以外,多台服务器性能的对比,以及Oracle集群相同事件的对比,都是必要的,但已有系统都无法方便地完成此任务。提出一系列与性能、流量、历史事件等相关的数据采集方法;利用脚本语言周期性地处理采集的数据并把结果数据集载入数据库系统;设计网页交互系统获取用户查询指令,后台利用RRDTool工具生成数据对比的图形化走势图。通过该系统与Oracle企业管理器得到系统运行性能对比分析报告。     

Improved version of parallel programming interface for distributed data with multiple helper servers

We present an improved version of the Parallel Programming Interface for Distributed Data with Multiple Helper Servers (PPIDDv2) library, which provides a common application programming interface that is based on the most frequently used functionality of both MPI-2 and GA. Compared with the previous version, the PPIDDv2 library introduces multiple helper servers to facilitate global data structures, and allows programmers to make heavy use of large global data structures efficiently.

Program summary

Program title: PPIDDv2Catalogue identifier: AEEF_v2_0Program summary URL:http://cpc.cs.qub.ac.uk/summaries/AEEF_v2_0.htmlProgram obtainable from: CPC Program Library, Queen?s University, Belfast, N. IrelandLicensing provisions: Standard CPC licence, http://cpc.cs.qub.ac.uk/licence/licence.htmlNo. of lines in distributed program, including test data, etc.: 22 997No. of bytes in distributed program, including test data, etc.: 184 477Distribution format: tar.gzProgramming language: Fortran, CComputer: Many parallel systemsOperating system: VariousHas the code been vectorised or parallelised?: Yes. 2–1024 processors usedRAM: 50 MbytesClassification: 6.5External routines: Global Arrays or MPI-2Catalogue identifier of previous version: AEEF_v1_0Journal reference of previous version: Comput. Phys. Comm. 180 (2009) 2673Does the new version supersede the previous version?: YesNature of problem: Many scientific applications require management and communication of data that is global, and the standard MPI-2 protocol provides only low-level methods for the required one-sided remote memory access.Solution method: The Parallel Programming Interface for Distributed Data (PPIDD) library provides an interface, suitable for use in parallel scientific applications, that delivers communications and global data management. The library can be built either using the Global Arrays (GA) toolkit, or a standard MPI-2 library. This abstraction allows the programmer to write portable parallel codes that can utilise the best, or only, communications library that is available on a particular computing platform.Reasons for new version: In the previous version, functionality in global data structure was mainly implemented by MPI-2 passive one-sided operations. In real applications which make heavy use of global data structures, very poor performance was observed.Summary of revisions: Multiple helper servers are introduced to facilitate the manipulation and management of global data structure. Mutual exclusion is also implemented by the help of a data server, and becomes much more robust and efficient. In addition, flexible options are provided to choose different settings for helper servers. Significant improvement has been seen in performance tests.Running time: Problem-dependent. The test provided with the distribution takes only a few seconds to run.     

An approximate MVA algorithm for exponential, class-dependent multiple servers

Mean value analysis (MVA) is an efficient algorithm for determining the mean sojourn time, the mean queue length, and the throughput in a closed multiclass queueing network. It provides exact results for the class of product-form networks. Often different classes have different service requirements in FCFS queues, but such networks are not of product form. There are several possibilities to compute performance measure for such nodes and networks. In this paper we present an approximation formula for multiple-server FCFS queues with class-dependent service times as a Norton flow equivalent product node, where the departure rate of any class depends on the number of customers of all classes in the queue. We will use this approximation in the sojourn time formula of some exact and approximate MVA algorithms.     

Scheduling web banner advertisements with multiple display frequencies

Online advertising continues to be a significant source of income for many Internet-based organizations. Recent indications of improved economic growth are having an impact on advertisement revenue, with the estimated online advertising revenue in the United States for the fourth quarter of 2003 totaling a record of $2.2 billion. A substantial portion of this income comes from banner advertisements, and efficient scheduling of these advertisements could result in a considerable increase in profits. The problem of scheduling banner advertisements has been observed to be intractable via traditional optimization techniques and has received only limited attention in the literature. In addition, all past attempts to address this problem have been based on an "all-or-nothing" framework, where a customer specifies the exact number of copies of the ad to be displayed over the planning horizon, if it is selected for display by the provider of the advertisement space. This paper extends it to a more realistic setting, where the customer is allowed to specify a set of acceptable display frequencies. The Lagrangian decomposition-based solution approaches presented in this paper are observed to provide good schedules in a reasonable period of time.     

Optimal provisioning of servers for hosting services of multiple types

Services of different types are provided to paying customers by instantiating Virtual Machines on servers hired from a cloud. Different VMs can share a server, subject to one or more resource constraints. Incoming jobs whose resource requirements cannot be satisfied are lost. The objective is to maximize the long-term average profit per unit time. A single-server model is analyzed exactly and the results provide approximations for the system with n servers. The latter is also solved exactly when the servers are dedicated and when the VMs can migrate instantaneously. Numerical examples and comparisons with simulations are presented.     

A secure mutual authenticated key agreement of user with multiple servers for critical systems

Recent technological advances in almost all critical systems’ domains have led to an explosive growth of multimedia big data. Those advances encompass the ever increasing innovative digital and remote mobile devices being operated on the users’ end. Due to the openness of critical system, the service providers in such networks are facing security challenges to authenticate those mobile devices on the field, and delivering services. In this scenario, the Multi-server authentication (MSA) framework seems to be a promising solution that enables its subscribers to avail services from different servers without getting registered to each server individually. In last few years many MSA protocols depending on RC-Offline authentication during mutual authentication, have been presented. However, to date, there is no efficient MSA scheme to our knowledge that is free of all three weaknesses, simultaneously. That is, 1) free from storage of server-based parameters (public keys or other values) in smart card by registration authority, 2) free from the assumption of publishing of server-based public keys publicly and 3) free from a single secret sharing with all servers so that it could avoid server masquerading (insider) attack. Considering these limitations, we present a multi-server authentication protocol that withstands above drawbacks using lightweight cryptographic operations. The rationale of the proposed work was to present an efficient RC-Offline MSA scheme. Our scheme is also backed by formal security analysis based on GNY logic and automated security verification using ProVerif tool.

     

Scheduling with job-dependent learning effects and multiple rate-modifying activities

We consider a scheduling problem with job-dependent learning effects and multiple rate-modifying activities. The learning effects manifest such that the processing time of a job is a decreasing function of its position in a sequence. By job-dependent learning effects, we mean that the learning of the jobs is different. A rate-modifying activity is an activity that changes the production rate of a machine. So the actual processing time of a job in our problem is a variable, which depends not only on its position in a sequence but also on whether it is scheduled before or after a rate-modifying activity. We assume that each machine may have multiple rate-modifying activities. The objective is to minimize the total completion time. We show that all the cases of the problem are polynomially solvable.     

Optimization analysis for an infinite capacity queueing system with multiple queue-dependent servers: genetic algorithm

This paper considers an M/M/r queueing system with infinite capacity, in which the number of working servers changes depending on the queue length. The steady-state probability distributions and the expected number of customers in the system are derived, which are used to construct a cost function. In order to minimize the expected cost of the system, we use the genetic algorithm to find the best thresholds of queue length in activating servers and their corresponding service rate. Some illustrative examples are provided to demonstrate how the process of this algorithm works for the optimal management policy of the multi-server queueing system.     

Scheduling with asynchronous service opportunities withapplications to multiple satellite systems

A single server is assigned to M parallel queues with independent Poisson arrivals. Service times are constant, but the server has the opportunity to initiate service at a given queue only at times forming a Poisson process. Four related scheduling policies are investigated: a simple first-come, first-serve policy for which the stability region is determined: a policy with maximum throughput, but requiring the server to have advance knowledge of service opportunities; a policy of threshold type, which is shown to be optimal among nonlookahead policies with preemption; and an adaptive policy, which when M=2 is shown to provide stability for all arrival rate vectors for which stability is possible under any nonlookahead policy with preemption. The work is motivated by the problem of transmission scheduling for a packet-switched, low-altitude, multiple-satellite system     

Product location,allocation and server home base location for an order picking line with multiple servers

In this paper, we are interested in several interrelated control issues for a ‘pick to order’ (or, ‘strict’ order picking) picking line which stores N=nk types of products in n bins, each with k shelves. To fill each order, a container is transported past the various locations containing products, and the appropriate quantity of each product is removed from its respective storage location and put into the order container using an ‘out and back’ picking strategy. Each of several pickers is assigned a set or ‘zone’ of products. We are interested in the concurrent problems of: (1) product location, (2) picker home base location, and (3) allocating products to each picker so that the expected order cycle time is minimized. We provide easily implemented algorithms to solve these problems and are able to show that the results apply for several alternate picking strategies. For fixed product locations, we develop an efficient dynamic programming algorithm which determines the optimal product allocation and server locations.