线形网络上单台车辆分群调度问题

本文研究线形网络上单台车辆分群调度问题:若干客户分布在一条直线上,它们被划分成若干个连续子集,其中每个子集称为一个群;每个客户有一个释放时间和一个服务时间;一台机器服务所有客户,且要求每个群内的客户连续服务;目标为极小化时间表长。该问题分两种形式:返回型和不返回型。返回型的时间表长定义为机器服务完所有客户后返回其初始位置的时间;不返回型的时间表长则定义为所有客户的最大完工时间。我们的结果是:对每个客户服务时间为零的情形,证明了两种形式均可在O(n²) 时间内解决;对每个客户服务时间任意的情形,就返回型和不返回型,分别给出了16/9和13/7近似算法。     

Scheduling service in tandem queues attended by a single server

Consider a tandem queue model with a single server who can switch instantaneously from one queue to another. Customers arrive according to a Poisson process with rate λ . The amount of service required by each customer at the i^th queue is an exponentially distributed random variable with rate μ_i. Whenever two or more customers are in the system, the decision as to which customer should be served first depends on the optimzation criterion. In this system all server allocation policies in the finite set of work conserving deterministic policies have the same expected first passage times (makespan) to empty the system of customers from any initial state. However, a unique policy maximizes the first passage probability of empty-ing the system before the number of customers exceeds K, for any value of K, and it stochastically minimizes (he number of customers in the system at any time t > 0 . This policy always assigns the server to the non empty queue closest to the exit     

Control and recovery from rare congestion events in a large multi-server system

We develop deterministic fluid approximations to describe the recovery from rare congestion events in a large multi-server system in which customer holding times have a general distribution. There are two cases, depending on whether or not we exploit the age distribution (the distribution of elapsed holding times of customers in service). If we do not exploit the age distribution, then the rare congestion event is a large number of customers present. If we do exploit the age distribution, then the rare event is an unusual age distribution, possibly accompanied by a large number of customers present. As an approximation, we represent the large multi-server system as an M/G/∞ model. We prove that, under regularity conditions, the fluid approximations are asymptotically correct as the arrival rate increases. The fluid approximations show the impact upon the recovery time of the holding-time distribution beyond its mean. The recovery time may or not be affected by the holding-time distribution having a long tail, depending on the precise definition of recovery. The fluid approximations can be used to analyze various overload control schemes, such as reducing the arrival rate or interrupting services in progress. We also establish large deviations principles to show that the two kinds of rare events have the same exponentially small order. We give numerical examples showing the effect of the holding-time distribution and the age distribution, focusing especially on the consequences of long-tail distributions. This revised version was published online in June 2006 with corrections to the Cover Date.     

A consistent diffusion approximation for finite-capacity multiserver queues

A diffusion approximation is developed for general multiserver queues with finite waiting spaces, which are typical models of manufacturing systems as well as computer and communication systems. The model is the standard GI/G/s/s + r queue with s identical servers in parallel, r extra waiting spaces, and the first-come, first-served discipline. The main focus is on the steady-state distribution of the number of customers in the system. The process of the number of customers is approximated by a time-homogeneous diffusion process on a closed interval in the nonnegative real line. A conservation law plus some heuristics standing on solid theoretical ground generate approximation formulas for the steady-state distribution and other congestion measures. These formulas are consistent with the exact results for the M/G/s/s and M/M/s/s + r queues. The accuracy of approximations for principal congestion measures are numerically examined for some particular cases.     

考虑常数客户批运输的单机排序问题

本文考虑工件首先在单机上加工,完工的工件由一辆容量有限的车配送到指定客户的模型,目标是最小化makespan。对于工件物理大小相同的情况,我们考虑了常数个客户的情形,并且给出了一个多项式时间的动态规划算法。对于工件物理大小不同的情况,我们讨论了一类特殊的三个客户的情形,并给出了一个2-近似算法。     

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.     

Equilibrium arrival times to a queue with order penalties

Suppose customers need to choose when to arrive to a congested queue with some desired service at the end, provided by a single server that operates only during a certain time interval. We study a model where the customers incur not only congestion (waiting) costs but also penalties for their index of arrival. Arriving before other customers is desirable when the value of service decreases with every admitted customer. This may be the case for example when arriving at a concert or a bus with unmarked seats or going to lunch in a busy cafeteria. We provide game theoretic analysis of such queueing systems with a given number of customers, specifically we characterize the arrival process which constitutes a symmetric Nash equilibrium.     

Tandem queueing system with infinite and finite intermediate buffers and generalized phase-type service time distribution

A tandem queueing system with infinite and finite intermediate buffers, heterogeneous customers and generalized phase-type service time distribution at the second stage is investigated. The first stage of the tandem has a finite number of servers without buffer. The second stage consists of an infinite and a finite buffers and a finite number of servers. The arrival flow of customers is described by a Marked Markovian arrival process. Type 1 customers arrive to the first stage while type 2 customers arrive to the second stage directly. The service time at the first stage has an exponential distribution. The service times of type 1 and type 2 customers at the second stage have a phase-type distribution with different parameters. During a waiting period in the intermediate buffer, type 1 customers can be impatient and leave the system. The ergodicity condition and the steady-state distribution of the system states are analyzed. Some key performance measures are calculated. The Laplace–Stieltjes transform of the sojourn time distribution of type 2 customers is derived. Numerical examples are presented.     

Planning and scheduling of the make-and-pack dairy production under lifetime uncertainty

In the dairy processing, the rapid quality decay of milk-based intermediate mixture to make and pack restricts productivity and, forces organizations to carefully plan and schedule their production. Hereby, in this study, we consider a planning and scheduling problem encountered in the dairy industry and propose a chance-constrained programming model accounting for uncertainty in quality decay of intermediate mixture. The aim of the model is to find the optimal lot sizes and production schedule with minimum makespan (total time needed to finish the daily production). The proposed schedule allows the storage duration of intermediate mixture to be within a stochastic lifetime. A case study is presented to illustrate the typical structure of the two-stage semi-continuous make-and-pack production process. The numerical study reflects real settings from a set (Balkan type) yoghurt production process. Accordingly, a simulation of the production process is introduced to evaluate the proposed production plan and schedule in terms of product waste. The model is examined with 32 scenarios consisting of different distribution parameters, confidence levels and demand patterns. Overall in the scenarios, the proposed plan and schedule result in decreasing 2693 l of product waste with 3.24 h increase of makespan in total.     

基于道路堵塞及顾客时间要求的快件配送最优路径选择

针对道路堵塞如节假日导致的临时最短配送路径失效的问题,提出配送网络最优路径选择模型,并设计了求解快递配送网络关键边和最优路径的算法。首先,计算出整个网络的关键边,掌握配送网络特征;其次,考虑顾客时间要求,研究不完全信息(中断无法提前预知,只有到达中断边的起点处才可知)下的最优路径,根据最短路径上各边新的特点,计算出每条边中断后对应的一组备用路径,再选择运输时间小于或等于顾客可等待时间的路径为有效路径,考虑道路堵塞情况,从有效路径中选择最优路径;最后,结合配送网络的实际情况对最优路径进行了算例分析。     

Multi-server retrial queue with negative customers and disasters

We consider a multi-server retrial queue with waiting places in service area and four types of arrivals, positive customers, disasters and two types of negative customers, one for deleting customers in orbit and the other for deleting customers in service area. The four types of arrivals occur according to a Markovian arrival process with marked transitions (MMAP) which may induce the dependence among the arrival processes of the four types. We derive a necessary and sufficient condition for the system to be positive recurrent by comparing sample paths of auxiliary systems whose stability conditions can be obtained. We use a generalized truncated system that is obtained by modifying the retrial rates for an approximation of stationary queue length distribution and show the convergence of approximation to the original model. An algorithmic solution for the stationary queue length distribution and some numerical results are presented.      

高负荷下带重尾服务强占优先排队的扩散逼近

考虑的排队系统是单服务台,顾客的初始到来是依泊松过程来到服务台,顾客的服务时间是重尾分布,服务的原则是强占优先服务.在高负荷条件下对此模型进行研究,获得了系统中的负荷过程,离去过程和队长过程的扩散逼近.     

An <Emphasis Type="Italic">M</Emphasis><Superscript>[<Emphasis Type="Italic">X</Emphasis>]</Superscript>/<Emphasis Type="Italic">G</Emphasis>/1 retrial queue with server breakdowns and constant rate of repeated attempts

We consider an M ^[X]/G/1 retrial queue subject to breakdowns where the retrial time is exponential and independent of the number of customers applying for service. If a coming batch of customers finds the server idle, one of the arriving customers begins his service immediately and the rest joins a retrial group (called orbit) to repeat his request later; otherwise, if the server is busy or down, all customers of the coming batch enter the orbit. It is assumed that the server has a constant failure rate and arbitrary repair time distribution. We study the ergodicity of the embedded Markov chain, its stationary distribution and the joint distribution of the server state and the orbit size in steady-state. The orbit and system size distributions are obtained as well as some performance measures of the system. The stochastic decomposition property and the asymptotic behavior under high rate of retrials are discussed. We also analyse some reliability problems, the k-busy period and the ordinary busy period of our retrial queue. Besides, we give a recursive scheme to compute the distribution of the number of served customers during the k-busy period and the ordinary busy period. The effects of several parameters on the system are analysed numerically. I. Atencia’s and Moreno’s research is supported by the MEC through the project MTM2005-01248.     

A BMAP/SM/1 queue with service times depending on the arrival process

We study a BMAP/>SM/1 queue with batch Markov arrival process input and semi‐Markov service. Service times may depend on arrival phase states, that is, there are many types of arrivals which have different service time distributions. The service process is a heterogeneous Markov renewal process, and so our model necessarily includes known models. At first, we consider the first passage time from level {κ+1} (the set of the states that the number of customers in the system is κ+1) to level {κ} when a batch arrival occurs at time 0 and then a customer service included in that batch simultaneously starts. The service descipline is considered as a LIFO (Last‐In First‐Out) with preemption. This discipline has the fundamental role for the analysis of the first passage time. Using this first passage time distribution, the busy period length distribution can be obtained. The busy period remains unaltered in any service disciplines if they are work‐conserving. Next, we analyze the stationary workload distribution (the stationary virtual waiting time distribution). The workload as well as the busy period remain unaltered in any service disciplines if they are work‐conserving. Based on this fact, we derive the Laplace–Stieltjes transform for the stationary distribution of the actual waiting time under a FIFO discipline. In addition, we refer to the Laplace–Stieltjes transforms for the distributions of the actual waiting times of the individual types of customers. Using the relationship between the stationary waiting time distribution and the stationary distribution of the number of customers in the system at departure epochs, we derive the generating function for the stationary joint distribution of the numbers of different types of customers at departures. This revised version was published online in June 2006 with corrections to the Cover Date.     

Little-Preemptive Scheduling on Unrelated Processors

We consider the preemptive scheduling of n independent jobs on m unrelated machines to minimize the makespan. Preemptive schedules with at most 2m–3 preemptions are built, which are optimal when the maximal job processing time is no more than the optimal schedule makespan. We further restrict the maximal job processing time and obtain optimal schedules with at most m–1 preemptions. This is better than the earlier known best bound of 4m ²–5m+2 on the total number of preemptions. Without the restriction on the maximal job processing time, our (2m–3)-preemptive schedules have a makespan which is no more than either of the following two magnitudes: (a) the maximum between the longest job processing time and the optimal preemptive makespan, and (b) the optimal nonpreemptive makespan. Our (m–1)-preemptive schedules might be at most twice worse than an optimal one.     

Age Process, Workload Process, Sojourn Times, and Waiting Times in a Discrete Time SM[K]/PH[K]/1/FCFS Queue

In this paper, we study a discrete time queueing system with multiple types of customers and a first-come-first-served (FCFS) service discipline. Customers arrive according to a semi-Markov arrival process and the service times of individual customers have PH-distributions. A GI/M/1 type Markov chain for a generalized age process of batches of customers is introduced. The steady state distribution of the GI/M/1 type Markov chain is found explicitly and, consequently, the steady state distributions of the age of the batch in service, the total workload in the system, waiting times, and sojourn times of different batches and different types of customers are obtained. We show that the generalized age process and a generalized total workload process have the same steady state distribution. We prove that the waiting times and sojourn times have PH-distributions and find matrix representations of those PH-distributions. When the arrival process is a Markov arrival process with marked transitions, we construct a QBD process for the age process and the total workload process. The steady state distributions of the waiting times and the sojourn times, both at the batch level and the customer level, are obtained from the steady state distribution of the QBD process. A number of numerical examples are presented to gain insight into the waiting processes of different types of customers.AMS subject classification: 60K25, 60J10This revised version was published online in June 2005 with corrected coverdate     

专有服务机制下提供免费体验服务的服务系统优化设计研究

通过提供免费的体验服务,服务系统可以吸引潜在顾客成为忠实顾客。本文考虑专有服务机制下提供免费体验服务和付费(常规)服务的服务系统,基于顾客的延时敏感特性,利用排队论的矩阵分析方法和谱扩展方法,研究服务系统的相关性能指标以及服务系统的优化设计,进而构建服务提供商利润函数并通过数值实例来获得免费体验服务的最优服务速率以及常规服务收取的最优服务费用,并为服务提供商提供相应的管理启示。研究表明,当越来越多的体验顾客转为付费顾客时,服务提供商需要降低体验服务的服务速率,来缓解系统的拥堵情况,减少顾客的逗留时间,并且服务提供商需要降低常规服务的服务费来弥补顾客因拥堵而造成的服务延迟。新到达顾客选择体验服务的人数越多时,服务提供商需要大幅度降低常规服务的收费标准,来吸引体验顾客成为付费顾客。     

Optimal Pricing and Admission Control in a Queueing System with Periodically Varying Parameters

We consider congestion control in a nonstationary queueing system. Assuming that the arrival and service rates are bounded, periodic functions of time, a Markov decision process (MDP) formulation is developed. We show under the infinite horizon discounted and average reward optimality criteria, for each fixed time, optimal pricing and admission control strategies are nondecreasing in the number of customers in the system. This extends stationary results to the nonstationary setting. Despite this result, the problem still seems intractable. We propose an easily implementable pointwise stationary approximation (PSA) to approximate the optimal policies, suggest a heuristic to improve the implementation of the PSA and verify its usefulness via a numerical study.     

Peak congestion in multi-server service systems with slowly varying arrival rates

In this paper we consider the M _t queueing model with infinitely many servers and a nonhomogeneous Poisson arrival process. Our goal is to obtain useful insights and formulas for nonstationary finite-server systems that commonly arise in practice. Here we are primarily concerned with the peak congestion. For the infinite-server model, we focus on the maximum value of the mean number of busy servers and the time lag between when this maximum occurs and the time that the maximum arrival rate occurs. We describe the asymptotic behavior of these quantities as the arrival changes more slowly, obtaining refinements of previous simple approximations. In addition to providing improved approximations, these refinements indicate when the simple approximations should perform well. We obtain an approximate time-dependent distribution for the number of customers in service in associated finite-server models by using the modified-offered-load (MOL) approximation, which is the finite-server steady-state distribution with the infinite-server mean serving as the offered load. We compare the value and lag in peak congestion predicted by the MOL approximation with exact values for M _t/M/s delay models with sinusoidal arrival-rate functions obtained by numerically solving the Chapman–Kolmogorov forward equations. The MOL approximation is remarkably accurate when the delay probability is suitably small. To treat systems with slowly varying arrival rates, we suggest focusing on the form of the arrival-rate function near its peak, in particular, on its second and third derivatives at the peak. We suggest estimating these derivatives from data by fitting a quadratic or cubic polynomial in a suitable interval about the peak. This revised version was published online in June 2006 with corrections to the Cover Date.