The aim of this paper is to evaluate the performance of the optimal policy (the Gittins index policy) for open tax problems of the type considered by Klimov in the undiscounted limit. In this limit, the state-dependent part of the cost is linear in the state occupation numbers for the multi-armed bandit, but is quadratic for the tax problem. The discussion of the passage to the limit for the tax problem is believed to be largely new; the principal novelty is our evaluation of the matrix of the quadratic form. These results are confirmed by a dynamic programming analysis, which also suggests how the optimal policy should be modified when resources can be freely deployed only within workstations, rather than system-wide.

The M/G/1 processor-sharing queue is studied by way of an approximating sequence of models featuring a round-robin discipline and operating in discrete time. In particular, residence-time distributions of jobs are derived.

Suppose that a number of jobs are to be carried out by a single processing unit orserver. The server can process any number of jobs at the same time but the time taken to finish all the jobs is the same no matter what scheduling policy is used, provided the server is never left idle. It is, however, possible to minimise the total delays to individual jobs by adopting a suitable policy. Optimal policies are derived here for the situation when the processing times are random variables. If the completion rates (analogous to hazard rates) for every job are increasing it is optimal to process the jobs in sequence. If they are decreasing the optimal policy involves simultaneous processing. These results are applied to a more general resource allocation problem arising in industrial chemical research.

A problem in optimal resource allocation is considered for n jobs with identically distributed service times admitting a monotone hazard function. If the hazard function is increasing, it is shown that the procedure of allocating the full resource individually to each job until its completion minimizes the expected completion time of the jth job. The procedure which at any instant of time equally allocated the resource among all of the remaining jobs is shown to minimize the expected total cumulative waiting time if the hazard is decreasing.