成批到达排队系统的随机比较

本文研究成批到达排队系统中队长过程的随机比较问题．利用随机比较方法我们对成批到达指数服务的多服务台排队系统进行分析,得到了该排队系统中队长过程的随机比较以及队长函数关于时间的凹性和凸性．同时我们也给出了成批到达一般服务的单服务台排队系统队长过程、稳态队长的随机比较以及队长函数关于时间的凹性和凸性．     

The Forcing Convexity Number of a Graph

For two vertices u and v of a connected graph G, the set I(u,v) consists of all those vertices lying on a u-v geodesic in G. For a set S of vertices of G, the union of all sets I(u,v) for u, v S is denoted by I(S). A set S is a convex set if I(S) = S. The convexity number con(G) of G is the maximum cardinality of a proper convex set of G. A convex set S in G with |S| = con(G) is called a maximum convex set. A subset T of a maximum convex set S of a connected graph G is called a forcing subset for S if S is the unique maximum convex set containing T. The forcing convexity number f(S, con) of S is the minimum cardinality among the forcing subsets for S, and the forcing convexity number f(G, con) of G is the minimum forcing convexity number among all maximum convex sets of G. The forcing convexity numbers of several classes of graphs are presented, including complete bipartite graphs, trees, and cycles. For every graph G, f(G, con) con(G). It is shown that every pair a, b of integers with 0 a b and b is realizable as the forcing convexity number and convexity number, respectively, of some connected graph. The forcing convexity number of the Cartesian product of H × K ₂ for a nontrivial connected graph H is studied.     

A modified vacation model M[x]/G/1 system

This paper studies the operating characteristics of an M^[x]/G/1 queueing system under a modified vacation policy, where the server leaves for a vacation as soon as the system is empty. The server takes at most J vacations repeatedly until at least one customer is found waiting in the queue when the server returns from a vacation. We derive the system size distribution at different points in time, as well as the waiting time distribution in the queue. Further, we derive some important characteristics including the expected length of the busy period and idle period. This shows that the results generalize those of the multiple vacation policy and the single vacation policy M^[x]/G/1 queueing system. Finally, a cost model is developed to determine the optimum of J at a minimum cost. Copyright © 2006 John Wiley & Sons, Ltd.     

Beyond the cμ rule: Dynamic scheduling of a two-class loss queue

We consider scheduling a single server in a two-class M/M/1 queueing system with finite buffers subject to holding costs and rejection costs for rejected jobs. We use dynamic programming to investigate the structural properties of optimal policies. Provided that the delay of serving a job is always less costly than rejecting an arrival, we show that the optimal policy has a monotonic threshold type of switching curve; otherwise, numerical analysis indicates that the threshold structure may not be optimal. Received December 1996/Revised version May 1997     

Hamiltonism and Partially Square Graphs

 Given a graph G, we define its partially square graph G ^* as the graph obtained by adding edges uv whenever the vertices u and v have a common neighbor x satisfying the condition N _G[x]⊆N _G[u]∪N _G [v], where N _G[x]=N _G(x)∪{x}. In particular, this condition is satisfied if x does not center a claw (an induced K _1,3). Obviously G⊆G ^*⊆G ², where G ² is the square of G. We prove that a k-connected graph (k≥2) G is hamiltonian if the independence number α(G ^*) of G ^* does not exceed k. If we replace G ^* by G we get a well known result of Chvátal and Erdo?s. If G is claw-free and G ^* is replaced by G ² then we obtain a result of Ainouche, Broersma and Veldman. Relationships between connectivity of G and independence number of G ^* for other hamiltonian properties are also given in this paper. Received: June 17, 1996 Revised: October 30, 1998     

Cycles in Partially Square Graphs

. In this work we consider finite undirected simple graphs. If G=(V,E) is a graph we denote by α(G) the stability number of G. For any vertex x let N[x] be the union of x and the neighborhood N(x). For each pair of vertices ab of G we associate the set J(a,b) as follows. J(a,b)={u∈N[a]∩N[b]∣N(u)⊆N[a]∪N[b]}. Given a graph G, its partially squareG ^* is the graph obtained by adding an edge uv for each pair u,v of vertices of G at distance 2 whenever J(u,v) is not empty. In the case G is a claw-free graph, G ^* is equal to G ². If G is k-connected, we cover the vertices of G by at most ⌈α(G ^*)/k⌉ cycles, where α(G ^*) is the stability number of the partially square graph of G. On the other hand we consider in G ^* conditions on the sum of the degrees. Let G be any 2-connected graph and t be any integer (t≥2). If ∑ _{x ∈ S} deg _G (x)≥|G|, for every t-stable set S⊆V(G) of G ^* then the vertex set of G can be covered with t−1 cycles. Different corollaries on covering by paths are given. Received: January 22, 1997 Final version received: February 15, 2000     

Generalized convexity and concavity of the optimal value function in nonlinear programming

In this paper we consider generalized convexity and concavity properties of the optimal value functionf ^* for the general parametric optimization problemP(_ε) of the form min _x f(x, ε) s.t.x∈R(ε). Many results on convexity and concavity characterizations off ^* were presented by the authors in a previous paper. Such properties off ^* and the solution set mapS ^* form an important part of the theoretical basis for sensitivity, stability and parametric analysis in mathematical optimization. We give sufficient conditions for several types of generalized convexity and concavity off ^*, in terms of respective generalized convexity and concavity assumptions onf and convexity and concavity assumptions on the feasible region point-to-set mapR. Specializations of these results to the parametric inequality-equality constrained nonlinear programming problem are provided. Research supported by Grant ECS-8619859, National Science Foundation and Contract N00014-86-K-0052, Office of Naval Research.     

Some results on a generalized M/G/1 feedback queue with negative customers

This paper deals with a generalized M/G/1 feedback queue in which customers are either “positive" or “negative". We assume that the service time distribution of a positive customer who initiates a busy period is G _e (x) and all subsequent positive customers in the same busy period have service time drawn independently from the distribution G _b (x). The server is idle until a random number N of positive customers accumulate in the queue. Following the arrival of the N-th positive customer, the server serves exhaustively the positive customers in the queue and then a new idle period commences. This queueing system is a generalization of the conventional N-policy queue with N a constant number. Explicit expressions for the probability generating function and mean of the system size of positive customers are obtained under steady-state condition. Various vacation models are discussed as special cases. The effects of various parameters on the mean system size and the probability that the system is empty are also analysed numerically. AMS Subject Classification: Primary: 60 K 25 · Secondary: 60 K 20, 90 B 22     

Computing steady-state queueing-time distributions of single-server queues:GI X /M/1

This paper presents a computationally efficient method to find the steady-state distributions of actual queueing times of the first customer, as well as of a randomly selected customer, of an arrival group for the queueing systemGI ^X /M/1, and hence the queueing-time distribution of a customer for the systemGI/E _X /1. The distribution of virtual queueing time is also obtained. Approximate analysis based on one or more roots is also discussed. Though the exact detailed as well as approximate computations for a variety of interarrival-time distributions such as generalized Erlang, mixed generalized Erlang, hyperexponential, generalized hyperexponential, and deterministic have been carried out, only representative results in the form of tables have been appended. The results obtained should prove useful to queueing theorists, practitioners, and others.     

A simple proof of an inequality connecting the alternating number of independent sets and the decycling number

If s_k denotes the number of independent sets of cardinality k and α(G) is the size of a maximum independent set in graph G, then I(G;x)=s₀+s₁x+?+s_α(G)x^α(G) is the independence polynomial of G (Gutman and Harary, 1983) [8].In this paper we provide an elementary proof of the inequality|I(G;−1)|≤2^φ(G) (Engström, 2009) [7], where φ(G) is the decycling number of G (Beineke and Vandell, 1997) [3], namely, the minimum number of vertices that have to be deleted in order to turn G into a forest.     

Cohen–Macaulayness and Limit Behavior of Depth for Powers of Cover Ideals

Let 𝕂 be a field, and let R = 𝕂[x ₁,…, x _n ] be the polynomial ring over 𝕂 in n indeterminates x ₁,…, x _n . Let G be a graph with vertex-set {x ₁,…, x _n }, and let J be the cover ideal of G in R. For a given positive integer k, we denote the kth symbolic power and the kth bracket power of J by J ^(k) and J ^[k], respectively. In this paper, we give necessary and sufficient conditions for R/J ^k , R/J ^(k), and R/J ^[k] to be Cohen–Macaulay. We also study the limit behavior of the depths of these rings.     

Depth of Initial Ideals of Normal Edge Rings

Let G be a finite graph on the vertex set [d] = {1,…, d} with the edges e ₁,…, e _n and K[t] = K[t ₁,…, t _d ] the polynomial ring in d variables over a field K. The edge ring of G is the semigroup ring K[G] which is generated by those monomials t ^e  = t _i t _j such that e = {i, j} is an edge of G. Let K[x] = K[x ₁,…, x _n ] be the polynomial ring in n variables over K, and define the surjective homomorphism π: K[x] → K[G] by setting π(x _i ) = t ^{e _i} for i = 1,…, n. The toric ideal I _G of G is the kernel of π. It will be proved that, given integers f and d with 6 ≤ f ≤ d, there exists a finite connected nonbipartite graph G on [d] together with a reverse lexicographic order <_rev on K[x] and a lexicographic order <_lex on K[x] such that (i) K[G] is normal with Krull-dim K[G] = d, (ii) depth K[x]/in_<rev (I _G ) = f and K[x]/in_<lex (I _G ) is Cohen–Macaulay, where in_<rev (I _G ) (resp., in_<lex (I _G )) is the initial ideal of I _G with respect to <_rev (resp., <_lex) and where depth K[x]/in_<rev (I _G ) is the depth of K[x]/in_<rev (I _G ).     

On constructible graphs,locally Helly graphs,and convexity

A (finite or infinite) graph G is constructible if there exists a well‐ordering ≤ of its vertices such that for every vertex x which is not the smallest element, there is a vertex y < x which is adjacent to x and to every neighbor z of x with z < x. Particular constructible graphs are Helly graphs and connected bridged graphs. In this paper we study a new class of constructible graphs, the class of locally Helly graphs. A graph G is locally Helly if, for every pair (x,y) of vertices of G whose distance is d ≥ 2, there exists a vertex whose distance to x is d ? 1 and which is adjacent to y and to all neighbors of y whose distance to x is at most d. Helly graphs are locally Helly, and the converse holds for finite graphs. Among different properties we prove that a locally Helly graph is strongly dismantable, hence cop‐win, if and only if it contains no isometric rays. We show that a locally Helly graph G is finitely Helly, that is, every finite family of pairwise non‐disjoint balls of G has a non‐empty intersection. We give a sufficient condition by forbidden subgraphs so that the three concepts of Helly graphs, of locally Helly graphs and of finitely Helly graphs are equivalent. Finally, generalizing different results, in particular those of Bandelt and Chepoi 1 about Helly graphs and bridged graphs, we prove that the Helly number h(G) of the geodesic convexity in a constructible graph G is equal to its clique number ω(G), provided that ω(G) is finite. © 2003 Wiley Periodicals, Inc. J Graph Theory 43: 280–298, 2003     

Optimal strategy policy in batch arrival queue with server breakdowns and multiple vacations

This paper considers a like-queue production system in which server vacations and breakdowns are possible. The decision-maker can turn a single server on at any arrival epoch or off at any service completion. We model the system by an M^[x]/M/1 queueing system with N policy. The server can be turned off and takes a vacation with exponential random length whenever the system is empty. If the number of units waiting in the system at any vacation completion is less than N, the server will take another vacation. If the server returns from a vacation and finds at least N units in the system, he immediately starts to serve the waiting units. It is assumed that the server breaks down according to a Poisson process and the repair time has an exponential distribution. We derive the distribution of the system size through the probability generating function. We further study the steady-state behavior of the system size distribution at random (stationary) point of time as well as the queue size distribution at departure point of time. Other system characteristics are obtained by means of the grand process and the renewal process. Finally, the expected cost per unit time is considered to determine the optimal operating policy at a minimum cost. The sensitivity analysis is also presented through numerical experiments.     

Analysis of a Discrete-Time Finite-Capacity Single-Server Queue with Markovian-Arrival Process and Random-Bulk-Service: D-MAP/G Y /1/M

In this article, we consider a single-server, finite-capacity queue with random bulk service rule where customers arrive according to a discrete-time Markovian arrival process (D-MAP). The model is denoted by D-MAP/G ^Y /1/M where server capacity (bulk size for service) is determined by a random variable Y at the starting point of services. A simple analysis of this model is given using the embedded Markov chain technique and the concept of the mean sojourn time of the phase of underlying Markov chain of D-MAP. A complete solution to the distribution of the number of customers in the D-MAP/G ^Y /1/M queue, some computational results, and performance measures such as the average number of customers in the queue and the loss probability are presented.     

A Stochastic Directional Convexity Result and Its Application in Comparison of Queues

Second order properties of queues are important in design and analysis of service systems. In this paper we show that the blocking probability of M/M/C/N queue is increasing directionally convex in (λ,?μ), where λ is arrival rate and μ is service rate. To illustrate the usefulness of this result we consider a heterogeneous queueing system with non-stationary arrival and service processes. The arrival and service rates alternate between two levels (λ₁,μ₁) and (λ₂,μ₂), spending an exponentially distributed amount of time with rate cα _i in level i, i=1,2. When the system is in state i, the arrival rate is λ _i and the service rate is μ _i . Applying the increasing directional convexity result we show that the blocking probability is decreasing in c, extending a result of Fond and Ross [7] for the case C=N=1.

     

Circular perfect graphs

For 1 ≤ d ≤ k, let K_k/d be the graph with vertices 0, 1, …, k ? 1, in which i ～j if d ≤ |i ? j| ≤ k ? d. The circular chromatic number χ_c(G) of a graph G is the minimum of those k/d for which G admits a homomorphism to K_k/d. The circular clique number ω_c(G) of G is the maximum of those k/d for which K_k/d admits a homomorphism to G. A graph G is circular perfect if for every induced subgraph H of G, we have χ_c(H) = ω_c(H). In this paper, we prove that if G is circular perfect then for every vertex x of G, N_G[x] is a perfect graph. Conversely, we prove that if for every vertex x of G, N_G[x] is a perfect graph and G ? N[x] is a bipartite graph with no induced P₅ (the path with five vertices), then G is a circular perfect graph. In a companion paper, we apply the main result of this paper to prove an analog of Haj?os theorem for circular chromatic number for k/d ≥ 3. Namely, we shall design a few graph operations and prove that for any k/d ≥ 3, starting from the graph K_k/d, one can construct all graphs of circular chromatic number at least k/d by repeatedly applying these graph operations. © 2005 Wiley Periodicals, Inc. J Graph Theory 48: 186–209, 2005     

Convexity in oriented graphs

For vertices u and v in an oriented graph D, the closed interval I[u,v] consists of u and v together with all vertices lying in a u−v geodesic or v−u geodesic in D. For S⊆V(D), I[S] is the union of all closed intervals I[u,v] with u,v∈S. A set S is convex if I[S]=S. The convexity number con(D) is the maximum cardinality of a proper convex set of V(D). The nontrivial connected oriented graphs of order n with convexity number n−1 are characterized. It is shown that there is no connected oriented graph of order at least 4 with convexity number 2 and that every pair k, n of integers with 1⩽k⩽n−1 and k≠2 is realizable as the convexity number and order, respectively, of some connected oriented graph. For a nontrivial connected graph G, the lower orientable convexity number con⁻(G) is the minimum convexity number among all orientations of G and the upper orientable convexity number con⁺(G) is the maximum such convexity number. It is shown that con⁺(G)=n−1 for every graph G of order n⩾2. The lower orientable convexity numbers of some well-known graphs are determined, with special attention given to outerplanar graphs.     

Radicals of Skew Polynomial and Skew Laurent Polynomial Rings Over Skew Armendariz Rings

In this note we study radicals of skew polynomial ring R[x; α] and skew Laurent polynomial ring R[x, x ^?1; α], for a skew-Armendariz ring R. In particular, among the other results, we show that for an skew-Armendariz ring R, J(R[x; α]) = N ₀(R[x; α]) = Ni?_*(R)[x; α] and J(R[x, x ^?1; α]) = N ₀(R[x, x ^?1; α]) = Ni?_*(R)[x, x ^?1; α].