简介：Thispaperstudiesonlineschedulingofjobswithkindreleasetimesonasinglemachine.Here“kindreleasetime”meansthatinonlinesetting,nojobscanbereleasedwhenthemachineisbusy.EachjobJhasakindreleasetimer(J)≥0,aprocessingtimep(J)>0andadeadlined(J)>0.Thegoalistodetermineaschedulewhichmaximizestotalprocessingtime(∑p(J)E(J))ortotalnumber(∑E(J))oftheacceptedjobs.Forthefirstobjectivefunction∑p(J)E(J),wefirstpresentalowerbound√2,andthenprovideanonlinealgorithmLEJwithacompetitiveratioof3.Thisisthefirstdeterministicalgorithmfortheproblemwithaconstantcompetitiveratio.Whenp(J)∈{1,k},k>1isarealnumber,wefirstpresentalowerboundminf(1+k)/k,2k/(1+k)g,andthenweshowthatLEJhasacompetitiveratioof1+┌k┐=k.Inparticular,whenalltheklengthjobshavetightdeadlines,wefirstpresentalowerboundmax{4=(2+k),1}(for∑p(J)E(J))and4/3(for∑E(J)).ThenweprovethatLEJis┌k┐/k-competitivefor∑p(J)E(J)andweprovideanonlinealgorithmHwithacompetitiveratioof2┌k┐/(┌k┐+1)forthesecondobjectivefunction∑E(J).