Online scheduling on a single machine with linear deteriorating processing times and delivery times

摘要

Abstract This paper considers a class of problems with linear deteriorating jobs. Jobs are released over time and become known to the online scheduler until their release times. Jobs are with deteriorating processing times or deteriorating delivery times. The objective is to minimize the time by which all jobs are delivered. We consider five different models on a single machine, and present an optimal online algorithm in competitiveness for each model, respectively.