Scheduling in Multiclass Networks with Deterministic Service Times

We consider general feed-forward networks of queues with deterministic service times and arbitrary arrival processes. There are holding costs at each queue, idling may or may not be permitted, and servers may fail. We partially characterize the optimal policy and give conditions under which lower priority should be given to jobs that would be delayed later in the network if they were processed now.     

Fixed-time schedules for the processing of jobs when service completions are not observable

We argue the importance of studying service systems in which the successful completion of job/customer service cannot be observed contemporaneously. Military and other applications are cited. The allocation of a large amount of processing to a job may make its (unobservable) successful completion more likely but will impose a burden on other jobs awaiting service. A fixed-time schedule specifies both the order in which jobs should be processed and how much processing each should receive. The goal is to find schedules which maximise the total expected reward earned from all jobs served. While this problem is intractable in general, a range of characterisations of optimal fixed-time schedules is achieved for given scenarios. The development of effective heuristics is also discussed.Received: November 2004 / Revised: January 2005In honour of the 60th birthday of Professor Ulrich Rieder     

M/G/1一般减量服务单重休假排队系统的随机分解

本文讨论了M/G/1型一般减量服务单重休假排队模型,运用结构分析法得到稳态队长和服务时间的随机分解的母函数和拉式变换,并给出稳态分布成立的条件及其概率含义．     

An M/G/1 Retrial Queueing System with Two-Phase Service and Preemptive Resume

An M/G/1 retrial queueing system with additional phase of service and possible preemptive resume service discipline is considered. For an arbitrarily distributed retrial time distribution, the necessary and sufficient condition for the system stability is obtained, assuming that only the customer at the head of the orbit has priority access to the server. The steady-state distributions of the server state and the number of customers in the orbit are obtained along with other performance measures. The effects of various parameters on the system performance are analysed numerically. A general decomposition law for this retrial queueing system is established.     

Optimal Operating Policy for an M/G/1 Exhaustive Server-Vacation Model

We consider an M/G/1 queueing system controlled by an exhaustive server–vacation policy, i.e, the server is turned off whenever the system becomes empty and it is turned on after a random time with at least a customer present in the system. In this paper, it is proved that there exists an exhaustive optimal policy which is of the form X + a(T - X)⁺, where, starting with the server off, X represents the time for the first arrival and T and a are non-negative real numbers. Using a classical average cost structure, the optimization problem is treated under the asymptotic average criterion. A structured definition of exhaustive policy is also derived.     

非零服务期M/G/1闸门服务休假排队系统的随机分解

讨论了非零服务期M/G/1闸门服务排队系统的随机分解.得到稳态队长和等待时间母函数(PGF)及拉氏变换(LST).并且可根据其随机分解的结构特征,为非空竭服务休假排队系统的排队指标的控制提供直接依据.     

有Bernoulli休假和可选服务的Geo/G/1重试排队

讨论了有Bernoulli休假策略和可选服务的离散时间Geo/G/1重试排队系统.假定一旦顾客发现服务台忙或在休假就进入重试区域,重试时间服从几何分布.顾客在进行第一阶段服务结束后可以离开系统或进一步要求可选服务.服务台在每次服务完毕后,可以进行休假,或者等待服务下一个顾客.还研究了在此模型下的马尔可夫链,并计算了在稳态条件下的系统的各种性能指标以及给出一些特例和系统的随机分解.     

有启动失败和可选服务的M/G/1重试排队系统

考虑具有可选服务的M/G/1重试排队模型,其中服务台有可能启动失败.系统外新到达的顾客服从参数为λ的泊松过程.重试区域只允许队首顾客重试,重试时间服务一般分布.所有的顾客都必须接受必选服务,然而只有其中部分接受可选服务.通过嵌入马尔可夫链法证明了系统稳态的充要条件.利用补充变量的方法得到了稳态时系统和重试区域中队长分布.我们还得到重试期间服务台处于空闲的概率,重试区域为空的概率以及其他各种指标.并证出在把系统中服务台空闲和修理的时间定义为广义休假情况下也具有随机分解特征.     

Min(N,V)--策略休假的M/G/1排队系统分析

在一个M／G／1休假排队系统中，同时考虑N-策略和多重休假策略，休假终止准则为任一个条件满足，我们称其为Min（N，V）-策略。本文给出了在此策略下的排队系统的稳态队长、忙期分布等基本指标。首次使用条件等待时间方法得到稳态等待时间的LST（Laplace-Stieltjes transform），同时还列举了一个应用的实例。最后指出本文模型是几个已研究模型的推广。     

Suboptimal Regulators for Discrete-Time Jump Linear Systems with Time-Multiplied Performance Index

This paper addresses the suboptimal regulator design problem of a discrete-time jump linear system by using a time-multiplied performance index. For a given state feedback control with constant gain matrices, the time-multiplied performance index is derived and a necessary condition for such a control to minimize the time-multiplied cost is provided. A gradient-based algorithm to find a suboptimal control law is developed and some numerical results are given to show the usefulness of the theoretical results.     

具有反馈、不可靠服务台和二次多选择服务M/G/1重试排队系统

An M/G/1 retrial queue with two-phase service and feedback is studied in this paper, where the server is subject to starting failures and breakdowns during service. Primary customers get in the system according to a Poisson process, and they will receive service immediately if the server is available upon arrival. Otherwise, they will enter a retrial orbit and are queued in the orbit in accordance with a first-come-first-served (FCFS) discipline. Customers are allowed to balk and renege at particular times. All customers demand the first "essential"service, whereas only some of them demand the second "multi-optional" service. It is assumed that the retrial time, service time and repair time of the server are all arbitrarily distributed.The necessary and sufficient condition for the system stability is derived. Using a supplementary variable method, the steady-state solutions for some queueing and reliability measures of the system are obtained.     

第二种服务可选的M/G/1排队模型的适定性

运用Hille-Yosida定理,Phillips定理与Fattorini定理证明第二种服务可选的M/G/1排队模型存在唯一的概率瞬态解.     

具有不同到达率的带有启动时间及不耐烦策略的多级适应性休假M/G/1排队

研究了具有不同到达率的带有启动时间及不耐烦策略的多级适应性休假M/G/1排队模型,给出了稳态队长的母函数,等待时间的LST及其随机分解结果,并推导出忙期、全忙期及在线期均值.     

有Bernoulli休假和可选服务的M/G/1重试反馈排队模型

考虑具有可选服务的M/G/1重试反馈排队模型,其中服务台有Bernoulli休假策略.系统外新到达的顾客服从参数为λ的泊松过程.重试区域只允许队首顾客重试,重试时间服从一般分布.所有的顾客都必须接受必选服务,然而只有其中部分接受可选服务.每个顾客每次被服务完成后可以离开系统或者返回到重试区域.服务台完成一次服务以后,可以休假也可以继续为顾客服务.通过嵌入马尔可夫链法证明了系统稳态的充要条件.利用补充变量的方法得到了稳态时系统和重试区域中队长分布.我们还得到了重试期间服务台处于空闲的概率,重试区域为空的概率以及其他各种指标.并证出在系统中服务员休假和服务台空闲的时间定义为广义休假情况下也具有随机分解特征.     

Optimal Hysteretic Control for the BMAP/G/ 1 System with Single and Group Service Modes

In this paper, we consider a single server queuing model with an infinite buffer in which customers arrive according to a batch Markovian arrival process (BMAP). The services are offered in two modes. In mode 1, the customers are served one at a time and in mode 2 customers are served in groups of varying sizes. Various costs for holding, service and switching are imposed. For a given hysteretic strategy, we derive an expression for the cost function from which an optimal hysteretic control can be obtained. Illustrative numerical examples are presented.     

An M/G/1 queue with second optional service

We study an M/G/1 queue with second optional service. Poisson arrivals with mean arrival rate (>0) all demand the first essential service, whereas only some of them demand the second optional service. The service times of the first essential service are assumed to follow a general (arbitrary) distribution with distribution function B(v) and that of the second optional service are exponential with mean service time 1/₂ (₂>0). The time-dependent probability generating functions have been obtained in terms of their Laplace transforms and the corresponding steady state results have been derived explicitly. Also the mean queue length and the mean waiting time have been found explicitly. The well-known Pollaczec–Khinchine formula and some other known results including M/D/1, M/E_k/1 and M/M/1 have been derived as particular cases.     

An M/G/1 queue with cyclic service times

In this paper we consider a single server queue with Poisson arrivals and general service distributions in which the service distributions are changed cyclically according to customer sequence number. This model extends a previous study that used cyclic exponential service times to the treatment of general service distributions. First, the stationary probability generating function and the average number of customers in the system are found. Then, a single vacation queueing system with aN-limited service policy, in which the server goes on vacation after servingN consecutive customers is analyzed as a particular case of our model. Also, to increase the flexibility of using theM/G/1 model with cyclic service times in optimization problems, an approximation approach is introduced in order to obtain the average number of customers in the system. Finally, using this approximation, the optimalN-limited service policy for a single vacation queueing system is obtained.On leave from the Department of Industrial Engineering, Iran University of Science and Technology, Narmak, Tehran 16844, Iran.     

The M/G/1 queue with disasters and working breakdowns

In this paper, we analyze the M/G/1 queueing system with disasters and working breakdown services. The system consists of a main server and a substitute server, and disasters only occur while the main server is in operation. The occurrence of disasters forces all customers to leave the system and causes the main server to fail. At a failure instant, the main server is sent to the repair shop and the repair period immediately begins. During the repair period, the system is equipped with the substitute server which provides the working breakdown services to arriving customers. After introducing the concept of working breakdown services, we derive the system size distribution and the sojourn time distribution. We also obtain the results of the cycle analysis. In addition, numerical works are given to examine the relation between the sojourn time and the some system parameters.     

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.