Research On The Online Scheduling Problems With Deteriorating Jobs

In the traditional scheduling problem,the processing time of the job is a definite constant.However,in real life,due to some characteristics of the job,the processing time of the job may deteriorate in the process of waiting for processing.For example,the fire will gradually become fierce in the process of waiting for extinguishing,the time required to extinguish will be longer.Such examples can be found in medical,financial management,iron and steel manufacturing,resource allocation and national defense,etc.Therefore,in both theoretical and practical applications,the scheduling problem with deterioration is of great significance and value.And the scheduling prob-lem with deterioration has gradually attracted extensive attention and in-depth study by researchers at home and abroadIn this paper,we mainly discuss the online over time scheduling problems with deteriorating jobs on a single machine,that is,jobs arrive successively with the advance of time,and before each job arrives,the scheduler knows nothing about the future information.In addition,for any job Jj,its processing time pj is a simple linear function of its starting time Sj,that is pj=bjSj,where bj is the deterioration rate of job Jj.This paper is divided into five chapters.It chiefly studied the online scheduling with rejection of simple linear deteriorating jobs on a single machine and the DSGR algorithm,respectively.In the first chapter,we first introduce the scheduling problem,then we briefly describe the development of the online scheduling problems,the scheduling problems with deteriorating jobs and the scheduling problems with rejectionThe second chapter introduces some basic definitions,such as competitive ratio,lower bound,three-parameter representation,and some conclusions about DSGR algo-rithm and SRDR algorithmIn the third chapter,we discuss an online scheduling problem of simple linear deterioration job with rejection,that is,each job has a rejection penalty ej and obeys agreeable condition,that is,for any two jobs Ji and Jj,if bi<bj,then ei?ej,and if bi=bj and ri<rj,then ei?ej.When the scheduler selects one job for processing,it can reject the job which is available and bear the corresponding penalty,or it can accept the job to process.The objective function is to minimize the total completion time of processed jobs plus the total penalty of rejection jobs.For this problem,we propose a best possible online algorithm DSGRR with competitive ratio 1+bmax,where bmax is also the maximum deterioration rate of all jobsIn the fourth chapter,we show another way to prove the optimality of DSGR algorithm,which is the best possible online algorithm given by Liu et al.for the online scheduling of simple linear deteriorating jobs on a single machine.And its competitive ratio is 1+bmax,where bmax denotes the maximum deterioration rate of all jobsThe last chapter mainly summarizes the content and innovation of the article,and looks forward to the future research directions.