Mathematics – Optimization and Control
Scientific paper
2009-07-21
Mathematics
Optimization and Control
36 pages, 8 figures
Scientific paper
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.
Bambos Nick
Chan Carri W.
No associations
LandOfFree
Efficiency-Loss of Greedy Schedules in Non-Preemptive Processing of Jobs with Decaying Value does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Efficiency-Loss of Greedy Schedules in Non-Preemptive Processing of Jobs with Decaying Value, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Efficiency-Loss of Greedy Schedules in Non-Preemptive Processing of Jobs with Decaying Value will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-174735