具有两台专用机,两台通用机的Q4／／Cmax问题的近似算法

本文讨论具有两台专用机、两台通用机的两组工件的同种类平行机的Q4／／Cmax问题，对这类特殊的排序问题，提出一种启发式算法，得到了最差情况下性能指标的严格的界．     

环Z／（m）上两种序列综合算法之间的关系

有限域Fq上单条序列的综合算法有著名的Berlkamp-Massey算法(简记B-M算法)，Reeds和Sipane(1985)将这一算法推广到整数同余类环Z／(m)上．作者曾利用推广的Gr6bner基理论，蛤出了环Z／(m)上单条及多条序列的新的综合算法，简称G-算法．本文讨论这两种序列综合算法之间的关系，并证明了G-算法和B-M算法对域上序列的综合是等价的；对环Z／(m)上的序列，通过对G-算法适当改进，可以顺序得到由推广的B-M算法求得的特征多项式．     

M／M／1／k后馈系统中的随机过程

本文对Ｍ／Ｍ／１／ｋ后馈排队系统中各随机过程的Ｐｏｉｓｓｏｎ性进行了讨论，推广了Ｂｒｅｍａｕｄ（［２］，［３］）的相应结果。所得结论表明Ｍ／Ｍ／１／ｋ后馈系统与Ｍ／Ｍ／１后馈系统情况有所不同，即在某些情况下，除总输出过程外，还有其它的过程也可能是Ｐｏｉｓｓｏｎ过程。顺便又地Ｍ／Ｍ／Ｃ／ｋ前馈后馈排队系统的动态数学模型进行了严格的讨论。     

不等式a~p／p＋b~q／q≥ab的证明

本文利用一个矩阵不等式，给出不等式ａｐ／ｐ＋ｂｑ／ｑ≥ａｂ，（ａ≥０，ｂ≥０，１＜ｐ＜∞且１／ｐ＋１／ｑ＝１）的一种新的证明方法。     

多体系统动力学微分／代数方程组的一类新的数值分析方法

本文讨论了多体系统动力学微分／代数混合方程组的数值离散问题．首先把参数t并入广义坐标讨论，简化了方程组及其隐含条件的结构，并将其化为指标1的方程组．然后利用方程组的特殊结构，引入一种局部离散技巧并构造了相应的算法．算法结构紧凑，易于编程，具有较高的计算效率和良好的数值性态，且其形式适合于各种数值积分方法的的实施．文末给出了具体算例．     

PH／PH／1／N反馈排队系统的逼留时间

具有反馈依赖于队长的ＰＨ／ＰＨ／１／Ｎ排队系统的队长和忙期的研究已在文（１）中解决，本文主要解决本系统的逗留时间的研究。     

服务台可修的PH／PH（PH／PH）／1排队系统

本文利用准生灭过程理论系统地研究了服务台可修的ＰＨ／ＰＨ（ＰＨ／ＰＨ）／１排队系统的随机结构和性态。首先证明了在平稳状态下可修排除系统ＰＨ／ＰＨ（ＰＨ／ＰＨ）／１从排除论的角度可转化为一个等价的通常排队模型ＰＨ／ＳＭ／１，然后给出了服务台的所有可靠性指标。     

服务台可修的M／SM（PH／SM）／1排队系统

本文研究服务台可修的Ｍ／ＳＭ（ＰＨ／ＳＭ）／１排队系统的随机结构和性态．先证明这个可修排队系统在平稳状态下可转化为一个等价的通常排队模型，然后给出服务台的所有稳态可靠性指标及其相关的结果．     

关于M／M／1排队系统中两个公式的证明

本文对Ｎ．Ｕ．Ｐｒａｂｈｕ在［１，Ｐ．３３］中的关于Ｍ／Ｍ／１系统中到第ｎ个顾客到达止全部闲期的极限分布予以严格证明、对［１，Ｐ．３２］中的关于Ｍ／Ｍ／１系统中的一个公式给出不利用复变函数论的初等证明．     

相型同步启动时间的M／M／c排队系统

本文研究带有同步启动时间的Ｍ／Ｍ／ｃ系统，其中启动时间是相型变量，给出了稳态和等待时间分布等结果。     

Zeros in tables of characters for the groups Sn and An

In the representation theory of symmetric groups, for each partition of a natural number n, the partition h() of n is defined so as to obtain a certain set of zeros in the table of characters for S_n. Namely, h() is the greatest (under the lexicographic ordering ) partition among P(n) such that (g) 0. Here, is an irreducible character of S_n, indexed by a partition , and g is a conjugacy class of elements in S_n, indexed by a partition . We point out an extra set of zeros in the table that we are dealing with. For every non self-associated partition P(n), the partition f() of n is defined so that f() is greatest among the partitions of n which are opposite in sign to h() and are such that (g) 0 (Thm. 1). Also, for any self-associated partition of n > 1, we construct a partition () P(n) such that () is greatest among the partitions of n which are distinct from h() and are such that (g) 0 (Thm. 2).Supported by RFBR grant No. 04-01-00463 and by RFBR-BRFBR grant No. 04-01-81001.Translated from Algebra i Logika, Vol. 44, No. 1, pp. 24–43, January–February, 2005.     

On the asymptotic behavior of xn+1=anxn/xn−1

We investigate the asymptotic behavior of solutions of a separable difference equation of the form

     

Embedding the diamond graph inLpand dimension reduction inL1

We show that any embedding of the level k diamond graph of Newman and Rabinovich [NR] into L_p, 1 < p 2, requires distortion at least . An immediate corollary is that there exist arbitrarily large n-point sets such that any D-embedding of X into requires . This gives a simple proof of a recent result of Brinkman and Charikar [BrC] which settles the long standing question of whether there is an L₁ analogue of the Johnson-Lindenstrauss dimension reduction lemma [JL].     

Some properties of the delay probability inM/M/s/s +c systems

We look at an extension of the steady state delay probability inM/M/s/s + c systems to nonintegral number of serverss and queue capacityc, which we call GED function. We show that this function is increasing and concave in the queue capacity. We find that if c 1, the reciprocal of the GED function is convex in the traffic intensity and the GED function is increasing in the traffic intensity if is below some ^* _s,c, and decreasing if is greater than ^* _s,c, Moreover, ^* _s,c is increasing in the number of servers and, fors 1, ^* _i,c=1 p^* _s,c < 2.Research supported by Grant BD/645/90-RM from Junta Nacional de Investigação Científica e Tecnológica.On leave from: Departamento de Matemätica, Instituto Superior Técnico, Av. Rovisco Pais, 1096 Lisboa Codex, Portugal.     

Second-order properties of the loss probability inM/M/s/s +c systems

The Erlang loss function, which gives the steady state loss probability in anM/M/s/s system, has been extensively studied in the literature. In this paper, we look at the similar loss probability inM/M/s/s + c systems and an extension of it to nonintegral number of servers and queue capacity. We study its monotonicity properties. We show that the loss probability is convex in the queue capacity, and that it is convex in the traffic intensity if is below some ^* and concave if is greater that ^*, for a broad range of number of servers and queue capacities. We prove that the one-server loss system is the onlyM/M/s/s +c system for which the loss probability is concave in the traffic intensity in all its range.Research supported by Grant BD/645/90-RM from Junta Nacional de Investigação Científica e Tecnológica.On leave from: Departamento de Matemática, Instituto Superior Técnico, Av. Rovisco Pais, 1096 Lisboa Codex, Portugal.     

On the average sojourn time under M/M/1/SRPT

We study an M/M/1 queueing system under the shortest remaining processing time (SRPT) policy. We show that the average sojourn time varies as , where ρ is the system load. Thus, SRPT offers a Θ(ln(e/(1−ρ))) factor improvement over policies that ignore knowledge of job sizes while scheduling.     

On the Relative Waiting Times in the GI/M/s and the GI/M/1 Queueing Systems

The expected steady-state waiting time, Wq(s), in a GI/M/s system with interarrival-time distribution H(·) is compared with the mean waiting time, Wq, in an "equivalent" system comprised of s separate GI/M/1 queues each fed by an interarrival-time distribution G(·) with mean arrival rate equal to 1/s times that of H(·). For H(·) assumed to be Exponential, Gamma or Deterministic three possible relationships between H(·) and G(·) are considered: G(·) can be of the "same type" as H(·); G(·) can be derived from H(·) by assigning new arrivals to the individual channels in a cyclic order; and G(·) may be obtained from H(·) by assigning customers probabilistically to the different queues. The limiting behaviour of the ratio R = Wq/Wq(s) is studied for the extreme values (1 and 0) of the common traffic intensity, ρ. Closed form results, which depend on the forms of H(·) and G(·) and on the relationships between them, are derived. It is shown that Wq is greater than Wq(s) by a factor of at least (s + 1)/2 when ρ approaches one, and that R is at least s(s!) when ρ tends to zero. In the latter case, however, R goes to infinity (!) in most cases treated. The results may be used to evaluate the effect on the waiting times when, for certain (non-queueing) reasons, it is needed to partition a group of s servers into several small groups.     

Representing workloads in GI/G/1 queues through the preemptive-resume LIFO queue discipline

We give in this paper a detailed sample-average analysis of GI/G/1 queues with the preemptive-resume LIFO (last-in-first-out) queue discipline: we study the long-run state behavior of the system by averaging over arrival epochs, departure epochs, as well as time, and obtain relations that express the resulting averages in terms of basic characteristics within busy cycles. These relations, together with the fact that the preemptive-resume LIFO queue discipline is work-conserving, imply new representations for both actual and virtual delays in standard GI/G/1 queues with the FIFO (first-in-first-out) queue discipline. The arguments by which our results are obtained unveil the underlying structural explanations for many classical and somewhat mysterious results relating to queue lengths and/or delays in standard GI/G/1 queues, including the well-known Bene's formula for the delay distribution in M/G/l. We also discuss how to extend our results to settings more general than GI/G/1.