Bounds and approximation for clocked interprocessor communication

We consider a clocked message transfer scheme in which message transfer is implemented as a periodic task with fixed overhead. Messages are then processed according to a priority discipline with preemption. Simple closed-form lower and upper bounds, and an approximation based on these bounds are found for the total system mean response time. Both bounds are tight for high processor occupancies, and simulation shows that the approximation is excellent for medium to high occupancies. Application to two different processors is given; the bounds and the approximation are found to be sufficiently tight, demonstrating the usefulness of this bounding and approximation technique for performance modelling of systems early in the design cycle.     

Computably Rigid Models with Enumerable Submodels

We consider recursive representations for the set of rational numbers with a distinguished dense and codense subset and for some Boolean algebras with a distinguished subalgebra. We show that the rejection of recursiveness of the distinguished submodel opens up the possibility of constructing models without nontrivial automorphisms. The proof is carried out by the priority method.     

互补判断矩阵排序的最小偏差法的性质

互补判断矩阵是决策给出的一种重要的偏好信息形式。本基于完全一致性互补判断矩阵的定义。提出互补判断矩阵排序的最小偏差法，研究了它的一些优良性质，包括强条件下保序性、置换不变性、相容性等，最后给出了一个算例，结果表明该种排序方法是有效的。     

基于OWGA算子的偏好信息集结法及其在群决策中的应用

研究了决策者的偏好信息以不同形式给出的群决策问题。首先，利用不同偏好信息之间的转换公式，将偏好次序型、效用值型、互反判断矩阵型三种偏好信息一致化为模糊互补判断矩阵型的偏好信息；其次。利用加权几何平均（OWGA）算子对一致化后的决策信息进行集结。再对方案的加权几何平均优势度进行综合集结，并以此进行方案的排序，提出了基于OWGA算子的群决策方法，该方法具有操作简便和计算量少的特点。最后。通过实例说明方法的可行性和实用性。     

Multi-Server Queueing Systems with Multiple Priority Classes

We present the first near-exact analysis of an M/PH/k queue with m > 2 preemptive-resume priority classes. Our analysis introduces a new technique, which we refer to as Recursive Dimensionality Reduction (RDR). The key idea in RDR is that the m-dimensionally infinite Markov chain, representing the m class state space, is recursively reduced to a 1-dimensionally infinite Markov chain, that is easily and quickly solved. RDR involves no truncation and results in only small inaccuracy when compared with simulation, for a wide range of loads and variability in the job size distribution. Our analytic methods are then used to derive insights on how multi-server systems with prioritization compare with their single server counterparts with respect to response time. Multi-server systems are also compared with single server systems with respect to the effect of different prioritization schemes—“smart” prioritization (giving priority to the smaller jobs) versus “stupid” prioritization (giving priority to the larger jobs). We also study the effect of approximating m class performance by collapsing the m classes into just two classes. Supported by NSF Career Grant CCR-0133077, NSF Theory CCR-0311383, NSF ITR CCR-0313148, and IBM Corporation via Pittsburgh Digital Greenhouse Grant 2003. AMS subject classification: 60K25, 68M20, 90B22, 90B36     

Re-entrant lines

Traditionally, manufacturing systems have mainly been treated as either job shops or flow shops. In job shops, parts may arrive with random routes, with each route having a low volume. In flow shops, the routes are fixed and acyclic, as in assembly lines. With the advent of semiconductor manufacturing plants, and more recently, thin film lines, this dichotomy needs to be expanded to consider another class of systems, which we call re-entrant lines. The distinguishing feature of these manufacturing systems is that parts visit some machines more than once at different stages of processing.Scheduling problems arise because several parts at different stages of processing may be in contention with each other for service at the same machine. There may be uncertainties in the form of random service or set-up times, as well as random machine failures and repairs. The goal of scheduling is to improve performance measures such as mean sojourn time in the system, which is also known as the mean cycle-time, or the variance of the cycle-time.In this paper we provide a tutorial account of some recent results in this field. We describe several scheduling policies of interest, and provide some results concerning their stability and performance. Several open problems are suggested.The research reported here has been partially supported by the National Science Foundation under Grant No. ECS-90-25007, and the Joint Services Electronics Program under Contract No. N00014-84-C-0149.     

Markov stopping games with random priority

In the paper a construction of Nash equilibria for a random priority finite horizon two-person non-zero sum game with stopping of Markov process is given. The method is used to solve the two-person non-zero-sum game version of the secretary problem. Each player can choose only one applicant. If both players would like to select the same one, then the lottery chooses the player. The aim of the players is to choose the best candidate. An analysis of the solutions for different lotteries is given. Some lotteries admit equilibria with equal Nash values for the players.The research was supported in part by Committee of Scientific Research under Grant KBN 211639101.     

三角模糊数互补判断矩阵排序的目标规划法

针对决策者以三角模糊数互补判断矩阵形式给出的多目标决策问题.给出三角模糊数加性一致性互补判断矩阵的判定定理.利用该定理基于最小偏差建立一个目标规划模型而解得三角模糊数互补判断矩阵的权重向量,从而使用三角模糊数排序公式对方案排序,提出了基于目标规划的三角模糊数互补判断矩阵排序法.最后,将模型与方法应用于项目投资决策中.     

基于样块和粒子群算法的图像修复

图像修复是近年来图像视觉研究当中的一个热点.Criminisi算法是一种比较常用的方法.为了消除原算法当中置信度和数据项相互影响的问题,并且考虑到平滑项对图像的锐化作用,对优先权的计算重新进行了调整.而将粒子群算法运用到最佳匹配块的搜索过程当中,避免了全局搜索带来的大工作量和不准确性,提高了算法的修复效率和准确性.经过仿真实验证明,改进后的算法不仅在PSNR值上有所提高,修复效果也更符合人们的视觉需求.     

An Arrival Time Approach to M/G/1-type Queues with Generalized Vacations

We propose a simple way, called the arrival time approach, of finding the queue length distributions for M/G/1-type queues with generalized server vacations. The proposed approach serves as a useful alternative to understanding complicated queueing processes such as priority queues with server vacations and MAP/G/1 queues with server vacations.