This thesis examines service systems where there is some uncertainty over the
successful completion of jobs within the system. Such problems have not been
widely studied, with much research assuming that jobs are willing to await service
indefinitely and that completion can be immediately observed during processing.
However, there are instances where this may not be the case. These include the
allocation of firepower in the military context, where 'jobs' are enemy targets who
may move out of range during 'service'. Another example for which our models are
relevant is a situation in which some service schedule is to be produced in advance,
where the exact time of completion is not known.
In these situations, allocating a large amount of processing to one job may increase
its chances of being successfully completed but will impose a burden on other jobs
awaiting service. Thus, any schedule should include some such 'trade-off'.
We examine this trade-off in three broad types of problem. In the first type, a
discount factor is applied to future rewards and fixed-time schedules developed. For
the second type, fixed-time schedules are developed for a single class queueing system,
subject to job arrivals and losses during service. In the third type, a multiple class
queueing system is studied, allocating a group of servers between job classes.
For each problem, stochastic dynamic programming optimality equations are
formulated. However, dynamic programming suffers from the well documented 'curse
of dimensionality' with problems becoming increasingly more difficult to solve as
the number of states increases. Thus, the focus of this thesis is the development of
heuristics as alternatives. Such heuristics are developed using results from queueing
theory and their effectiveness is discussed. Characterisations of optimal schedules are