Chapter 6 SCHEDULES AND RETRIALS
This chapter deals with models where customers choose their time of arrival. Such models contain some non-stationary element like known times that a service facility is open, a scheduled (possibly periodic) service, or information about the state of the queue in past instants.
1 Waiting time auctions
Holt and Sherman [81] considered a model for the allocation of a fixed known number, say n, of identical prizes at a specified time on a FCFS basis to N individuals who independently choose their arrival times.
To avoid trivialities assume N gt; n. Individuals are then motivated to arrive early and increase their chances of obtaining a prize. Early arrival is associated with a cost, and its benefits depend on the strategies of the other claimants. Individuals differ by their time value C and by their value R of the prize. However, only the time value of the prize matters. It is assumed that is continuously distributed in the population according to a distribution function G. Individuals learn whether they get a prize only at the time of allocation of prizes: “losers' also wait.
Holt and Sherman described an equilibrium in which individuals with higher time values of a prize arrive earlier. Thus, the time of arrival before prizes are allocated is a function t (a). Given G(a) it is possible to compute another function F(a), which gives the probability that an individual with time value of prize a obtains a prize. Specifically, F（a）is the probability that the number of applicants with values greater than a, out of the other N - 1 applicants, does not exceed n - 1:
The equilibrium arrival times t (a) satisfy：
t#39; (a) = a F#39;(a) (6.1)
for all a gt; 0. This relation equates the marginal values of the cost of arriving earlier and the expected value from the associated increase in the probability of getting a prize.
Assuming that there is some cost (time or monetary) associated with arriving, a threshold value a* exists such that only those with a gt; a* choose to arrive. A person with a = a* is indifferent between arriving and not, and if he decides to arrive then he does so at time 0: t (a*) = 0.
With this initial condition, the solution to (6.1) is
Holt and Sherman further verified that this is an equilibrium.
Holt and Sherman also considered variations of the model. One result is that if losers do not wait (they can observe that the length of the queue upon their arrival exceeds the number of prizes) then the equilibrium involves longer waiting times for the winners, so that the expected waiting time is unchanged.
2 ?/M/1
Glazer and Hassin[59] considered the customer#39;s decision of when to visit a service facility that opens daily during a prespecified time interval. They referred to the model (with a single server and exponential service) as? / M /1. This approach differs from most of the queueing literature which assumes that the arrival process is given exogenously. Though some papers considered the optimal setting of appointments, the abovementioned paper was the first to consider the way customers choose their arrival time in a decentralized queueing system where each customer maximizes his own welfare2.
The model#39;s assumptions are:
1 The facility opens al time 0 and closes at time T.
2 The service discipline is FCFS.
3 All customers arriving prior to time T are served.
4 A customer may obtain a favorable position in the queue by arriving before time o, but no service is provided until this time.
5 Customers cannot observe the queue before making their irrevocable decision of when to arrive.
6 Individuals from a very large population decide whether or not to arrive during the day .The total number of arrivals during the day has a Poisson distribution with an expected value A.
7 The service requirement of each customer is exponential with the same rate p.
8 A customer has no preferences with regard to his time of arrival except that he wants to choose one that minimizes his expected waiting time.
The arrival process can be described by a distribution function F (t),which gives the probability that a random customer among those who arrive during the day, arrives prior to time t. One can see (similar to 4.5) that in equilibrium the function F(t) is continuous (so that no point has mass probability of arrival) and the range in which it is strictly increasing is an interval of the type( -omega;, T) for some omega; gt; 0. We denote by f(t) the density function corresponding to F(t). Thus, the arrival process is nonhomogeneous Poisson, with rate tau; f (t) at time t.
Since each customer minimizes his expected waiting time, in equilibrium each instant in which a customer may arrive has the same expected waiting time. Equivalently, since all customers have the same service distribution, customers minimize their expected queueing time. The expected queueing time of a customer who arrive sat -omega; is omega;, since he is guaranteed to encounter an empty queue. Therefore, in equilibrium, the expected queueing time is exactly w for an arrival at any time in the interval (-omega;, T).
The expected queueing time for an arrival at a given instant depends on the pattern of customer arrivals prior to this instant. We will now determine necessary conditions on the function F(t) that are satisfied in equilibrium.
Consider first the situation faced by a customer who arrives at time t lt; 0. The expected number of customers ahead of him in the queue is .Because service commences only at time zero, his expected queueing time is (recall that t amp;
第6章 计划和重审
本章介绍客户选择其到达时间的模型。这类模型包含一些不稳定因素，例如服务设施开放的已知时间，调度（可能是周期性的）服务，或者关于过去时刻的队列状态的信息。
1. 等待时间拍卖
Holt和Sherman [81]提出了一个模型，用于在FCFS(First Come First Served )先来先服务的基础上指定时间分配相同奖品的固定已知数字（例如n），以及独立选择到达时间的N个人。
为了避免繁琐，假设Ngt; n。然后激励个人提前到来并增加获得奖品的机会。提前到达与成本相关，其好处取决于其他索赔人的策略。个人的时间价值C和奖品的价值R不同。然而，只有奖品的时间价值重要。假设根据分布函数G在群体中连续分布。个人学习者们是否得到奖品仅在于奖品的时间价值分配：“失败者”也等待。
Holt和Sherman描述了一种均衡，其中个人更早到达的奖励具有更高的时间价值。因此，分配奖品之前的到达时间是函数t（a）。给定G（a），可以计算另一个函数F（a），它给出了a的概率。具有奖励时间价值的个人获得奖品。具体来说，F（a）是在其他N-1个申请人中，数值大于a的申请人数不超过n-1的概率：
均衡到达时间t（a）满足：
t#39; (a) = a F#39;(a) (6.1)
对于所有agt; 0，这种关系等于早期到达成本的边际值和获得奖励概率的相关增加的预期值。
假设存在与到达相关联的一些成本（时间或金钱），存在阈值a*，使得仅具有agt; a *的那些选择到达。a=a*的人在到达与否之间无动于衷，如果他决定到达那么他在时间0：t（a *）= 0时这样做。
在这个初始条件下，（6.1）的解决方案是
霍尔特和谢尔曼进一步证实这是一种均衡。
霍尔特和谢尔曼也考虑了模型的变化。一个结果是，如果失败者不等待（他们可以观察到他们到达队列的长度超过奖品数量）那么均衡涉及获胜者的等待时间更长，因此预期的等待时间不变。
2 ? / M/1
Glazer和Hassin[59]考虑了客户决定何时访问在预定时间间隔内每天打开的服务设施。他们将模型（使用单个服务器和指数服务）称为? / M / 1。这种方法与大多数排队文献不同，后者假定到达过程是外生的。虽然有些论文考虑了会见的最佳设置，但上述论文是第一个考虑客户在分散排队系统中选择到达时间的方式，每个客户最大化自己的福利2。
该模型的假设是：
1设施打开时间0并在时间T关闭。
2服务规则是FCFS。
3所有在时间T之前到达的客户都将获得服务。
4客户可以在时间o之前到达队列中获得有利位置，但在此之前不提供服务。
5在做出不可撤销的决定何时到达之前，客户无法观察队列。
6来自非常大的人口的个人决定是否在白天到达。白天到达的总人数具有泊松分布，具有预期值A。
7每个客户的服务要求是指数级的，具有相同的费率p。
8客户对其到达时间没有偏好，除非他想选择最小化其预期等待时间的偏好。
到达过程可以通过分布函数来描述，该函数给出了在白天到达的那些中的随机客户在时间t之前到达的概率。可以看出（类似于4.5）在平衡状态下，函数是连续的（因此没有点具有质量到达概率），并且其严格增加的范围是类型的间隔（-omega;, T）对于某些omega;gt; 0，我们用表示对应于的密度函数。因此，到达过程是非均匀泊松，在时间t具有速率
由于每个客户最小化他的预期等待时间，因此在客户可能到达的每个时刻达到平衡时具有相同的预期等待时间。同样，由于所有客户都拥有相同的服务分布，因此客户可以最大限度地缩短预期的排队时间。到达设置-omega;的客户的预期排队时间是omega;，因为他保证会遇到空队列。因此，在平衡状态下，预期的排队时间恰好是在区间（-omega;，T）的任何时间到达的时间。
到达给定时刻的预期排队时间取决于此时刻之前客户到达的模式。我们现在将确定在均衡中满足的函数的必要条件。
首先考虑在时间t lt;0时到达的客户所面临的情况。队列中预期的客户数量是。因为服务仅在零时开始，他预期的排队时间是（回想t lt;0，这解释了减法）。因此，我们得出结论:
- 在时间-w和0之间，密度函数是均匀的，即
(6.2)
接下来考虑在时间0之后的到达过程。假设在时间t恰好k个客户在系统中的概率为。让系统中预期的客户数量为。加入t的客户的预期排队时间与之成正比。在均衡中，是恒定的, for 0le;tle;T。因此，
(6.3)
注意在0中是不连续的。到达时间t的速率是，并且它与时间t之前的到达过程的实现无关。因此，状态概率满足关系
(6.4)
此处，k= 1,2,⋯
(6.5)
为了定义边界条件，我们从（6.2）中观察到客户在时间0之前到达的概率是，因此在时间0之前到达的数量是泊松均值，并且对于k = 0,1,2,⋯
(6.6)
客户在时间0之后到达的概率是.因此 (6.7)
平衡的到达模式可以从(6.2)-(6.7)确定。特别是，通过用 (6.3) 中给出的表达式替换来解决 (6.4)-(6.5)。
Glazer和Hassin表明了这一点：
- 开放时间后的到达率不是恒定的，而是随着时间的推移而下降。
其他排队模型一样，个人主义行为不是社会最优的。关于客户在时间0之前的行为，最清楚地看到这个问题。在均衡状态下，客户在设施开放之前尽早到达时间单位。实际上，当相对于T较大时，大多数客户在设施开放服务之前加入队列。 对个人主义行为的非最优性问题的解决方案是预约系统的制度，但是在许多情况下这样的解决方案可能太昂贵。[59]中提出的另一种解决方案是按随机顺序提供服务，至少在时间0的队列中的那些客户中。该规则消除了在设施开放时间之前到达的激励。注意，在这种情况下，恰好在零时刻到达的正概率。
3 到达预定批量服务
Glazer和Hassin [61]考虑了一种不同的模型，客户决定何时到达，以尽量减少他们的预期等待时间。在这个模型中，服务以均匀间隔的时间安排，比如⋯-2,-1,0,1,2，⋯连续服务之间的间隔表示为一个周期，讨论将是，不失一般性，关于循环[0,1]。队列规则是FCFS，并且最多N个客户批量提供服务。如果在服务时代表超过N个客户，那么仅仅服务N，其余的服务等待未来服务3。到达过程使得各个周期中的到达是独立同分布的。具体来说，让一个周期内的到达总数为泊松类型的随机变量，均值lt;N.客户必须决定何时到达他的周期。
由于服务直到周期结束才开始，因此严格意义上的周期内到达是社会效率低下的。因此，希望客户仅在周期结束时到达。但是，如果等待客户的数量超过N的可能性很大，则这种解决方案不是均衡的。原因在于，通过较早地无限地到达，顾客可以在队列中确保更好的位置并且将他的预期等待时间减少非无限小的量。本节的其余部分描述了均衡解。
与前一节一样，到达模式的完全特征在于概率分布函数，它给出了在t，tisin;(0, 1]之前加入队列的客户（选择进入给定周期的客户）的预期比例。换句话说，是一个随机客户在一个周期开始后达到最多t个时间单位的概率。再者，在均衡中很容易验证F是连续的，以及F是严格的区间(t0, 1]。对于某些t0ge;0，单调增加的形式为（t0,1]。在t0（t0,1]期间的到达过程遵循非均匀泊松过程和速率
设为到达tisin;（0,1）的客户的预期等待时间。均衡条件意味着对于某些omega;，=omega;表示tisin;（0,1）;ge;omega;表示tisin;(0，t0)。我们现在转向计算omega;和F。
对于j = 0,1,2，...，令qj是j个新客户到达周期的概率，并且令rj是j个客户在预定服务之前就在队列中的概率。注意，值qj是外生给出的，而rj的值是从平衡解得出的
然后,
(6.8)
以及对于 jgt; 0,
(6.9)
考虑一个客户选择在服务时间0之前到达。在均衡状态下，他对这个选择和到达t0无动于衷。根据定义，(0，t0)是没有到达。因此，他不会通过将他的到来推迟到t0来冒着他在队列中位置的风险。如果0之前的队列长度是N或更大，那么通过将他的到达推迟到t0，他将节省等待t0。但是，如果时间0之前的队列长度最多为N-1，那么如果他在0之前到达，他将立即得到服务，如果他将他的到达推迟到t0，那么他将等待l- t0在时间1服务 因此
or (6.10)
为了完成均衡解的描述，我们现在通过Pj ( t )计算F表示在时间t恰好j个客户在队列中的概率。然后, (6.11)
而且
(6.12)
到达时间的顾客的预期等待时间可以表达为
得
(6.13)
由于到达过程是非均匀泊松，
(6.14)
对于jgt;0,
(6.15)
用（6.15）代替（6.13）并等于0得到
=
=
或者 (6.16)
等式(6.8)-(6.16)确定平衡到达模式。对于N = 1 (6.16)简化为
因此，
- 当N = 1时，到达速率在区间(t0, 1)中是恒定的，并且t0 =1-。
Glazer和Hassin在数值上对其他N值的方程进行了调整，在这些情况下，到达率在时间间隔(t0, 1)中随时间缩短。
4 重审
客户选择到达时间以使其福利最大化的另一种情况涉及重审或需求重复。在这些模型中，观察繁忙系统的客户在抵达后暂时离开并稍后返回。在试验之间，据说客户在轨道上。这样的客户拥有的信息通常仅限于服务器在上次试用时忙碌的知识。特别是，他无法观察到轨道上的客户数量。Falin [49]的调查报告对该模型及其变体进行了广泛的讨论。
在本节中，我们考虑Kulkarni [96]，Elcan [48]和Hassin和Haviv [71]的单服务器模型。客户到达根据泊松过程的速率，服务需求与速率mu;呈指数关系；观察繁忙服务器的客户暂时离开并稍后再次尝试。每次重审费用r，轨道运行时的费用是每单位时间的C。此模型中不允许犹豫。
假设重试之间的时间长度相互独立，并且随参数呈指数分布。特别地，的任何值对应一个策略。其他策略，例如当重试之间的时段遵循非指数分布时，在此模型中
以上是毕业论文外文翻译，课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。
