Optimal algorithms for online single machine scheduling with deteriorating jobs

In many realistic scenarios of job processing, one job consumes a longer time to be satisfied with a later start time of processing. This phenomenon is known as job’s deterioration effect. Such effect is unexplored in the context of online environment. In this paper we study online single machine scheduling for deteriorating jobs, where jobs arrive over time and become known to any online algorithm on their arrivals. The processing time of each job is a linearly increasing function of its start time. We mainly investigate three online models that minimize makespan, total completion time and maximum delivery time, respectively. For each model we present an optimal online algorithm in competitiveness.