Partial servicing of on-line jobs

We consider the problem of scheduling jobs online, where jobs may be served partially in order to optimize the overall use of the machines. Service re quests arrive online to be executed immediately. The scheduler must decide how long and if it will run a job (that is, it must fix the quality of serv ice level of the job) at the time of arrival of the job. We assume that pre emption is not allowed. We give lower bounds on the competitive ratio and present algorithms for jo bs with varying sizes and for jobs with uniform size, and for jobs that can be run for an arbitrary time or only for some fixed fraction of their full execution time. Copyright (C) 2001 John Wiley & Sons, Ltd.