  We consider the problem of dynamically scheduling J jobs on N processors for
non-preemptive execution where the value of each job (or the reward garnered
upon completion) decays over time. All jobs are initially available in a buffer
and the distribution of their service times are known. When a processor becomes
available, one must determine which free job to schedule so as to maximize the
total expected reward accrued for the completion of all jobs. Such problems
arise in diverse application areas, e.g. scheduling of patients for medical
procedures, supply chains of perishable goods, packet scheduling for
delay-sensitive communication network traffic, etc. Computation of optimal
schedules is generally intractable, while online low-complexity schedules are
often essential in practice.
  It is shown that the simple greedy/myopic schedule provably achieves
performance within a factor 2 + E[max_j sigma_j](min_j E[sigma_j]) from
optimal. This bound can be improved to a factor of 2 when the service times are
identically distributed. Various aspects of the greedy schedule are examined
and it is demonstrated to perform quite close to optimal in some practical
situations despite the fact that it ignores reward-decay deeper in time.
