Optimal Entering Rules for a Customer with Wait Option at an M/G/1 Queue

A "smart" customer arrives at an M/G/1 queue. While every other arrival joins the system unconditionally, our customer is allowed to choose among three alternatives: (i) he may Enter the queue and stay there until his service is completed, (ii) he may Leave the system right away, or (iii) he may Wait outside the queue. If he Enters or Leaves the system, his decision is final and no further actions are taken. If he chooses to Wait, he makes a new decision at the next service completion where he may, again, select one of the three options: Enter, Leave, or Wait. For a linear cost structure we show that for any n-period horizon (0 < n < \infty ) the individual customer's optimal strategy is a 3-region (possibly degenerate) policy by which he Enters a small queue, Leaves a large one and Waits when the queue is of an intermediate size. We also give a necessary and sufficient condition for the Wait option to exist. The special M/M/1 queue is further analyzed by allowing the Waiting customer to make decisions at instants of customers' arrivals as well as at instants of service completion. In this case, too, the optimality of the 3-region policy is derived and the "smart" customer dichotomy is recognized as the Gambler's Ruin problem. Computational procedures are developed and numerical results are presented for commonly used service time distributions.