  We consider maximizing the long-term average reward in a single server queue,
where the reward obtained for a job is a non-increasing function of its sojourn
time. The motivation behind this work comes from multiple applications,
including quantum information processing and multimedia streaming. We introduce
a new service discipline, shortest predicted sojourn time (SPST), which, in
simulations, performs better than well-known disciplines. We also present some
limited analytical guarantees for this highly intricate problem.
