Control Policies of an M/G/1 Queueing System with a Removable and Non-reliable Server

This paper considers a single non-reliable server in the ordinary M/G/1 queueing system whose arrivals form a Poisson process and service times are generally distributed. We also study a single removable and non-reliable server in the controllable M/G/1 queueing systems operating under the N policy, the T policy and the Min( N , T ) policy. It is assumed that the server breaks down according to a Poisson process and the repair time has a general distribution. In three control policies, we show that the probability that the server is busy in the steady-state is equal to the traffic intensity. It is shown that the optimal N policy and the optimal Min( N , T ) policy are always superior to the optimal T policy. Sensitivity analysis is also investigated.     

Control of a Heterogeneous Two-Server Exponential Queueing System

A dynamic control policy known as "threshold queueing" is defined for scheduling customers from a Poisson source on a set of two exponential servers with dissimilar service rates. The slower server is invoked in response to instantaneous system loading as measured by the length of the queue of waiting customers. In a threshold queueing policy, a specific queue length is identified as a "threshold," beyond which the slower server is invoked. The slower server remains busy until it completes service on a customer and the queue length is less than its invocation threshold. Markov chain analysis is employed to analyze the performance of the threshold queueing policy and to develop optimality criteria. It is shown that probabilistic control is sub-optimal to minimize the mean number of customers in the system. An approximation to the optimum policy is analyzed which is computationally simple and suffices for most operational applications.     

The optimal control of an M/G/1 queueing system with server vacations, startup and breakdowns

This paper studies the control policy of the N policy M/G/1 queue with server vacations, startup and breakdowns, where arrivals form a Poisson process and service times are generally distributed. The server is turned off and takes a vacation whenever the system is empty. If the number of customers waiting in the system at the instant of a vacation completion is less than N, the server will take another vacation. If the server returns from a vacation and finds at least N customers in the system, he requires a startup time before providing service until the system is again empty. It is assumed that the server breaks down according to a Poisson process and his repair time has a general distribution. The system characteristics of such a model are analyzed and the total expected cost function per unit time is developed to determine the optimal threshold of N at a minimum cost.     

Optimal control of a queueing system with two heterogeneous servers

The problem considered is that of optimally controlling a queueing system which consists of a common buffer or queue served by two servers. The arrivals to the buffer are Poisson and the servers are both exponential, but with different mean service times. It is shown that the optimal policy which minimizes the mean sojourn time of customers in the system is of threshold type. The faster server should be fed a customer from the buffer whenever it becomes available for service, but the slower server should be utilized if and only if the queue length exceeds a readily computed threshold value.     

Sensitivity analysis of the optimal management policy for a queuing system with a removable and non-reliable server

The management policy of an M/G/1 queue with a single removable and non-reliable server is considered. The decision-maker can turn the single server on at any arrival epoch or off at any service completion. It is assumed that the server breaks down according to a Poisson process and the repair time has a general distribution. Arrivals form a Poisson process and service times are generally distributed. In this paper, we consider a practical problem applying such a model. We use the analytic results of the queueing model and apply an efficient Matlab program to calculate the optimal threshold of management policy and some system characteristics. Analytical results for sensitivity analysis are obtained. We carry out extensive numerical computations for illustration purposes. An application example is presented to display how the Matlab program could be used. The research is useful to the analyst for making reliable decisions to manage the referred queueing system.     

Optimal management for infinite capacity N-policy M/G/1 queue with a removable service station

In this article, we consider an infinite capacity N-policy M/G/1 queueing system with a single removable server. Poisson arrivals and general distribution service times are assumed. The server is controllable that may be turned on at arrival epochs or off at service completion epochs. We apply a differential technique to study system sensitivity, which examines the effect of different system input parameters on the system. A cost model for infinite capacity queueing system under steady-state condition is developed, to determine the optimal management policy at minimum cost. Analytical results for sensitivity analysis are derived. We also provide extensive numerical computations to illustrate the analytical sensitivity properties obtained. Finally, an application example is presented to demonstrate how the model could be used in real applications to obtain the optimal management policy.     

Routing and scheduling in heterogeneous systems: a sample pathapproach

Consider the problem of routing customers to a set of K parallel servers that have different rates. Each server has a buffer with infinite capacity. The arrival process is general and the service times are assumed to be i.i.d. exponential random variables. Using sample path arguments, we show that, given any Bernoulli policy π, there exists another policy ρ which outperforms π by partially using a randomized version of a round-robin policy. Moreover, ρ is easily specified and implemented. We present extensions of our results to systems with finite capacities and service times that have an increasing hazard rate. Finally, a similar result is shown to hold in the context of scheduling customers from a set of K parallel queues     

Criticality- and QoS-Based Multiresource Negotiation and Adaptation

This paper presents design, analysis, and implementation of a multiresource management system that enables criticality- and QoS-based resource negotiation and adaptation for mission-critical multimedia applications. With the goal of maximizing the number of high-criticality multimedia streams and the degree of their QoS, it introduces a dynamic scheduling approach using on-line QoS adjustment and multiresource preemption. An integrated multiresource management infrastructure and a set of scheduling algorithms for multiresource preemption and on-line QoS adjustment are presented. The optimality and execution efficiency of two preemption algorithms are analyzed. A primal-dual-algorithm-based approximation solution is shown (1) to be comparable to the linear-programming-based solution, which is near optimal; (2) to outperform a criticality-cognitive baseline algorithm; and (3) to be feasible for on-line scheduling. In addition, the dynamic QoS adjustment scheme is shown to greatly improve the quality of service for video streams. The multiresource management system is part of the Presto multimedia system environment prototyped at Honeywell for mission-critical applications.     

Impatient customers in an M/M/1 queue with single and multiple working vacations

We consider an M/M/1 queue with impatient customers and two different types of working vacations. The working vacation policy is the one in which the server serves at a lower rate during a vacation period rather than completely stop serving. The customer’s impatience is due to its arrival during a working vacation period, in which the customer service rate is lower than the normal busy period. We analyze the queue for two different working vacation termination policies, a multiple working vacation policy and a single working vacation policy. Closed-form solutions and various performance measures like, the mean queue lengths and the mean waiting times are derived. The stochastic decomposition properties are verified for both multiple and single working vacation cases. A comparison of both the models is carried out to capture their performances with the change in system parameters.     

Proof of stability conditions for token passing rings by Lyapunovfunctions

A token passing ring can be described as a system of M queues with one server that rotates around the queues sequentially. Georgiadis-Szpankowski (1992) considered rings where the token (server) performs x ∇ l_j services on queue j, where x is the size of queue j upon arrival of the token, and l_j is a fixed limit of service for queue j. The token then spends some random time switching to the next queue. For j=1, ..., M, arrivals to queue j are Poisson with rate λ_j, and service times have mean s _j and are independent of the arrival and switchover processes. The purpose of this paper is to give an alternate and simpler proof of the stability conditions given by Georgiadis-Szpankowski using Lyapunov functions. An additional assumption is made about the second moments of the service and switchover times being finite     

A note on preemptive scheduling of multiclass jobs with geometric service times and hard deadlines

We consider the scheduling of multiclass jobs with deadlines to the completion of their service. Deadlines are deterministic and job arrivals in each class occur at the times of deadline expirations in the respective class. Assuming geometric service times with class dependent means, we derive structural properties of preemptive server allocation policies that maximize the expected number of job completions. Our work extends results that have appeared in the real-time wireless scheduling literature.     

Optimal anticipative scheduling with asynchronous transmissionopportunities

Service is provided to a set of parallel queues by a single server. The service of queue i may be initiated only at certain time instances {t_nⁱ}_n=1^∞ that constitute the connectivity instances for queue i. The service of different customers cannot overlap. Scheduling is required to resolve potential contention of services initiated at closely spaced, closer than the service time, connectivity instances. At any time t, the future connectivity instances are available for scheduling. An anticipative policy is given, which at time t schedules the transmissions until a certain future time t+h. The length of the scheduling horizon h is selected based on the backlog at t. The allocation of the server in the interval [t, t+h], is done in accordance to the backlogs of the individual queues at t. The throughput region of the system is characterized, and it is shown that the policy we propose achieves maximum throughput. The policy has a low implementation complexity which is bounded for all the achievable throughput vectors. The average delay and the scheduling complexity are studied by simulation, and the trade-off between the two is demonstrated. The above scheduling problem arises in the access layer of the cross-links of a satellite network     

M/M/1-PS queue and size-aware task assignment

We consider a distributed server system in which heterogeneous servers operate under the processor sharing (PS) discipline. Exponentially distributed jobs arrive to a dispatcher, which assigns each task to one of the servers. In the so-called size-aware system, the dispatcher is assumed to know the remaining service requirements of some or all of the existing jobs in each server. The aim is to minimize the mean sojourn time, i.e., the mean response time. To this end, we first analyze an M/M/1-PS queue in the framework of Markov decision processes, and derive the so-called size-aware relative value of state, which sums up the deviation from the average rate at which sojourn times are accumulated in the infinite time horizon. This task turns out to be non-trivial. The exact analysis yields an infinite system of first order differential equations, for which an explicit solution is derived. The relative values are then utilized to develop efficient dispatching policies by means of the first policy iteration (FPI). Numerically, we show that for the exponentially distributed job sizes the myopic approach, ignoring the future arrivals, yields an efficient and robust policy when compared to other heuristics. However, in the case of highly asymmetric service rates, an FPI based policy outperforms it. Additionally, the size-aware relative value of an M/G/1-PS queue is shown to be sensitive with respect to the form of job size distribution, and indeed, the numerical experiments with constant job sizes confirm that the optimal decision depends on the job size distribution.     

Preemptive scheduling on two parallel machines with a single server

This paper addresses a preemptive scheduling problem on two parallel machines with a single server. Each job has to be loaded (setup) by the server before being processed on the machines. The preemption is allowed in this paper. The goal is to minimize the makespan. We first show that it is no of use to preempt the job during its setup time. Namely, every optimal preemptive schedule can be converted to another optimal schedule where all the setup times are non-preemptively performed on one machine. We then present an algorithm with a tight bound of 4/3 for the general case. Furthermore, we show that the algorithm can produce optimal schedules for two special cases: equal processing times and equal setup times, which are NP-hard in the non-preemptive version.     

Markov regenerative stochastic Petri nets with general execution policies: supplementary variable analysis and a prototype tool

Stochastic Petri nets (SPNs) with general firing time distributions are considered. Generally timed transitions can have general execution policies: the preemption policy may be preemptive repeat different (prd) or preemptive resume (prs) and the firing time distribution can be marking-dependent. A stationary analysis method covering all possible combinations is presented by means of supplementary variables. The method is implemented in a prototype tool SPNica which is based on Mathematica. The use of the general execution policies is illustrated by a WWW server model.     

Stability properties of constrained queueing systems and schedulingpolicies for maximum throughput in multihop radio networks

The stability of a queueing network with interdependent servers is considered. The dependency among the servers is described by the definition of their subsets that can be activated simultaneously. Multihop radio networks provide a motivation for the consideration of this system. The problem of scheduling the server activation under the constraints imposed by the dependency among servers is studied. The performance criterion of a scheduling policy is its throughput that is characterized by its stability region, that is, the set of vectors of arrival and service rates for which the system is stable. A policy is obtained which is optimal in the sense that its stability region is a superset of the stability region of every other scheduling policy, and this stability region is characterized. The behavior of the network is studied for arrival rates that lie outside the stability region. Implications of the results in certain types of concurrent database and parallel processing systems are discussed     

Analysis and control of correlated web server queues

The research literature is rich with studies that demonstrate various degrees of correlation in the arrival processes found in Web server environments. All of these previous studies either have assumed the arrival process of each Web server to be independent of the corresponding service process or have completely ignored this important issue. Using data from commercial Web servers, we demonstrate the existence of considerable dependencies between arrival times and service times, in addition to a strong dependence structure within the arrival process, and then we explore a likely causal model of this cross correlation. A mathematical approximation of Web server performance is derived, based on heavy-traffic stochastic-process limits, that captures both the correlations within the arrival process and the correlations between the arrival and service processes. We then demonstrate that the results from our approximation, which is asymptotically exact, are in very good agreement with simulation results across all traffic intensities. Our mathematical analysis is further exploited to revisit certain scheduling issues in Web server environments. In particular, we consider a scheduling approach that provides expected response times relatively close to those under the optimal shortest remaining processing time policy while also maintaining better variance properties.     

Robust berth scheduling at marine container terminals via hierarchical optimization

In this paper, we present a mathematical model and a solution approach for the discrete berth scheduling problem, where vessel arrival and handling times are not known with certainty. The proposed model provides a robust berth schedule by minimizing the average and the range of the total service times required for serving all vessels at a marine container terminal. Particularly, a bi-objective optimization problem is formulated such that each of the two objective functions contains another optimization problem in its definition. A heuristic algorithm is proposed to solve the resulting robust berth scheduling problem. Simulation is utilized to evaluate the proposed berth scheduling policy as well as to compare it to three vessel service policies usually adopted in practice for scheduling under uncertainty.     

Optimal NT policies for M/G/1 system with a startup and unreliable server

This paper studies the control policies of an M/G/1 queueing system with a startup and unreliable server, in which the length of the vacation period is controlled either by the number of arrivals during the idle period, or by a timer. After all the customers are served in the queue exhaustively, the server immediately takes a vacation and operates two different policies: (i) the server reactivates as soon as the number of arrivals in the queue reaches to a predetermined threshold N or the waiting time of the leading customer reaches T units; and (ii) the server reactivates as soon as the number of arrivals in the queue reaches to a predetermined threshold N or T time units have elapsed since the end of the completion period. If the timer expires or the number of arrivals exceeds the threshold N, then the server reactivates and requires a startup time before providing the service until the system is empty. Furthermore, it is assumed that the server breaks down according to a Poisson process and his repair time has a general distribution. We analyze the system characteristics for each scheme. The total expected cost function per unit time is developed to determine the optimal thresholds of N and T at a minimum cost.     

Customer routing to parallel servers with different rates

We consider the problem of routing customers to parallel servers having different rates. There are no buffers in the system. Each customer must be rooted to a server immediately upon its arrival and if the server to which it is routed is occupied, then the customer is aborted. The aim is to maximize throughput (the proportion of customers which are successfully routed to a free server), when the routing must be done without knowing which servers are occupied and which are free. An upper bound on the throughput is found for a general renewal arrival process and geometric service times. Furthermore, a new routing policy, the golden ratio policy, is suggested and shown to approach a limit which is within at least 98.4 percent of the upper bound. The golden ratio policy is a generalization of the round robin policy, when the service rates of the servers are different.