Online scheduling of simple linear deteriorating jobs to minimize the total general completion time
Traditional scheduling assumes that the processing time of a job is fixed. Yet there are numerous situations in which the processing time increases (deteriorates) as the start time increases. In particular, lots of work has been devoted to jobs with simple linear deterioration. The processing time p(j) of job J(j) is a simple linear function of its start time s(j), precisely, p(j) = b(j)s(j), where b(j) is the deteriorating rate. In this paper, we study the problem of online non-preemptive scheduling of jobs with arbitrary release times and simple linear deteriorating rates on a single machine to minimize the total general completion time. We present an algorithm DSDR (Delayed Smallest Deteriorating Rate) and prove that it achieves the best-possible competitive ratio (1 + b(max))(alpha) for all deterministic online algorithms, where a is the general index of completion time and alpha > 0. (C) 2013 Elsevier B.V. All rights reserved.
online scheduling simple linear deterioration total general completion time release time single machine competitive analysis