Online deadline scheduling on faster machines

Abstract

Online deadline scheduling is to determine which jobs are accepted or rejected, where jobs have the deadline by which they must finish their processing and they arrive in the online fashion. The slack of a job is the gap between its arrival time and the last time when it can first be scheduled to meet its deadline. The job instance is given such that the slack of each job is at least kappa times its processing time, where kappa is called patience. In this paper, online algorithms have faster machines than the adversary. We investigate the speed of machines on which the online algorithms can achieve the optimality and parametrize them by the patience. (C) 2002 Elsevier Science B.V All rights reserved.