Journal
THEORETICAL COMPUTER SCIENCE
Volume 262, Issue 1-2, Pages 437-458Publisher
ELSEVIER
DOI: 10.1016/S0304-3975(00)00288-7
Keywords
analysis of algorithms; scheduling; online algorithms
Categories
Ask authors/readers for more resources
The problem of online multiprocessor scheduling with rejection was introduced by Bartal et al. (SIAM J, Discrete Math. 13(1) (2000) 64-78). They show that for this problem the competitive ratio is 1 + phi approximate to 2.61803, where phi is the golden ratio. A modified model of multiprocessor scheduling with rejection is presented where preemption is allowed. For this model, it is shown that better performance is possible. An online algorithm which is (4 + root 10/3 < 2.38743-competitive is presented. We prove that the competitive ratio of any online algorithm is at least 2.12457. We say that an algorithm schedules obliviously if the accepted jobs are scheduled without knowledge of the rejection penalties. We also show a lower bound of 2.33246 on the competitive ratio of any online algorithm which schedules obliviously. As a subroutine in our algorithm, we use a new optimal online algorithm for preemptive scheduling without rejection. This algorithm never achieves a larger makespan than that of the previously known algorithm of Chen et al. (Oper, Res. Lett. 18(3) (1995) 127-131), and achieves a smaller makespan for some inputs. <(c)> 2001 Elsevier Science B.V. All rights reserved.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available