Ex 2.2.6 motivates the study of the \(M/G/1\) queue under an \(N\)-policy. We use the renewal-reward theorem to derive the time-average cost for this system by focusing on the average cost and duration of cycles that start and stop each time a job arrives at an empty system. As corollaries we obtain the EPQ formula of Section 4.3 and the PK formula of Section 5.4.

The expected cycle duration is what we first need. For this, we consider the expected time \(T(q)\) to clear the system when the server starts working on the first of \(q\) jobs present. We present three different ideas to obtain \(T(q)\).

The first heuristic idea is this. We know that jobs arrive at a rate \(\lambda\) and are served at a rate \(1/\E S = \mu>\lambda\). Clearly, the net `drain rate' of the queue is \(\mu-\lambda\); hence we guess that<sup>11</sup> By analogy: when you have a `queue' of \(q\) km to cycle, and your speed is \(v\) km/h, then it takes \(q/v\) hours to complete the trip.

Clearly, this reasoning completely ignores the stochasticity in arrival times and services: we cannot guarantee that the result is correct. For the second idea, consider a regular²² That is, not controlled by an \(N\)-policy. \(M/G/1\) queue. When a job arrives to an empty system, it takes a busy time³³ Recall the explanation that led to Eq. (4.1.3). \(\E \U\) to service this job and all the jobs that arrive during the service of this first job. In other words, it takes \(\E\U\) time on average to move from \(1\) job in the system to \(0\) jobs, i.e., one job less. But then, when there are \(q\) jobs in the system, it must take \(T(q) = q\E\U\) units of time to move from state \(q\) to state \(0\). By Ex 4.3.7, \(\E\U=\E S/(1-\rho)\), so we again obtain Eq. (5.6.1). The third idea is the most powerful. Write \(Y\) for the number of jobs that arrive during a service time. Then \(T(q)\) satisfies the relation

because first the job in service must leave, and then, when \(Y=k\), it takes \(T(q+k-1)\) to clear the system. To solve this equation, we substitute the guess \(T(q) = aq+b\) and solve for \(a\) and \(b\). It is clear⁴⁴ If the system is empty, no time is needed to clear it. that \(T(0)=0\), hence \(b=0\). Substituting \(a q\) into Eq. (5.6.2) gives \(a q =\E S + aq + a\E Y - a\). Noting⁵⁵ Poisson arrivals \(\implies\) \(\E{Y|S=s} = \lambda s\) \(\implies\) \(\E{Y|S} = \lambda S\) \(\implies\) \(\E Y = \E{\E{Y|S}} = \lambda \E S\). that \(\E Y = \lambda \E S\), and solving for \(a\) we find Eq. (5.6.1). We note that the solution of Eq. (5.6.2) is unique once \(T(0)\) is fixed.

For the expected cycle duration \(C(N)\) as a function of \(N\), observe that, right after the server switches off, we need \(N\) independent inter-arrival times to reach level \(N\). As this takes \(N/\lambda\) in expectation, and then the system needs \(T(N)\) to become empty again, \(C(N) = N/\lambda + T(N)\).

For the cycle cost, we proceed as follows. First, consider the expected cost \(U(q)\) of waiting that accrues while one job is served and \(q-1\) jobs are in queue.⁶⁶ Thus, there are \(q\) jobs in the system. When the service starts, the waiting cost for these \(q\) jobs is \(h q \E{S}\).⁷⁷ That is, \(h\) times the area of the rectangle with base \(\E{S}\) and height \(q\). Next, arrivals during the service of the job also contribute to the cost of waiting. The expected time these arrivals spend in the system equals \(\E{\int_0^{S} N(s) \d s}\), where \(N(s)\sim \Pois{\lambda s}\). Conditional on \(S=t\), \(\E{\int_0^{S} N(s) \d s |S=t} = \int_{0}^{t} \E{N(s)} \d s = \int_{0}^{t} \lambda s \d s = \lambda t^2/2\), hence \(\E{\int_0^{S} N(s) \d s|S} = \lambda S^{2}/2\), hence \(\E{\int_0^{S} N(s) \d s} = \lambda \E{S^{2}/2}\). Combining both cost terms, the total cost of waiting during the service of the job is

Let \(V(q)\) be the expected queueing costs to clear the system just after a service starts and \(q\) jobs are in the system. By analogy with Eq. (5.6.2), \(V(q)\) must be the solution of

As \(U(q)\) has a term linear in \(q\) and a constant term, we substitute a quadratic form \(V(q) = aq^2 + bq+c\) instead of a linear relation, assemble terms with the same power in \(q\), and solve for \(a, b\) and \(c\). Of course, \(c = 0\) since \(V(0)=0\). For \(a\) and \(b\) we need some work to arrive at⁸⁸ See Ex 5.6.11--Opt 5.6.12.

For the cost during the build-up of the queue, we again use a recursive procedure. Write \(W(q)\) for the accumulated queueing cost⁹⁹ Here \(W\) is not the waiting time in queue. from the moment the server becomes idle up to the arrival time of the \(q\)th job (the job that sees \(q-1\) jobs in the system upon arrival). Then,¹⁰¹⁰ See Ex 5.6.8.

By combining all the above cost factors and using the renewal reward theorem, we find for the long-run average cost¹¹¹¹ Opt 5.6.13.

It is easy to retrieve the Pollaczek-Khinchine formula from this. The LHS in Eq. (5.6.4) is the average cost per unit time. Since in the \(M/G/1\) queue, each waiting customer pays \(h=1\) per unit time, the LHS corresponds to \(\E \L\). For the RHS, in the \(M/G/1\) queue, the setup cost \(K=0\), hence it is optimal to take \(N=1\). Consequently, just the first two terms of the RHS of Eq. (5.6.4) remain. The first term is \(\E\QQ = \lambda \E \W\), where \(\E \W\) is given by the PK formula. The second is \(\rho = \E{\Ls}\). But \(\E \L = \E\QQ + \E\Ls\), i.e., the LHS and RHS are equal.

A second interesting result is the EPQ formula for a production-inventory system with Poisson arrivals and no backlogging.¹²¹² This is more general than Eq. (4.3.1) because demand can arrive as a Poisson process. Although in its present form, backlogging is now not allowed, this is simple to include. The optimal production quantity can be found by taking the derivative of Eq. (5.6.4) with respect to \(N\), just as if it is a continuous variable. Setting the derivative to zero and solving for \(N\) results in, up to rounding,