A Note on Optimal Service Selection in a Single Server Queue

In an M/G/1 environment with finite waiting room, the server, for each new customer to be served, may choose any of k different service modes. Under a certain cost structure and certain assumptions about the different “speeds” of service it is shown that the search for an optimal policy can be restricted to a relatively small class of possible policies. Using this information simple and feasible algorithms may be designed to explicitly obtain an optimal policy.