Online schedulingofweightedequal-lengthjobswithharddeadlines on parallelmachines

We considertheproblemofschedulingamaximumprofitselectionofequallengthjobson m identical machines.Jobsarriveonlineovertimeandthegoalistodetermineanon-preemptiveschedulewhich maximizesthetotalprofitofthescheduledjobs.Letthecommonprocessingrequirementofthejobsbe p40. Foreachjob ji, i¼1,y,n we aregivenareleasetime ri (at whichthejobbecomesknown)anda deadline riþpþdi . Ifthejobisscheduledandcompletedbeforethedeadline,aprofitof wi is earned. Upon arrivalofanewjob,anonlinealgorithmmustdecidewhethertoacceptthejobornot.Incaseof acceptance,theonlinealgorithmsmustprovideafeasiblestartingdateforthejob. Competitiveanalysishasbecomeastandardwayofmeasuringthequalityofonlinealgorithms.Fora maximizationproblem,anonlinealgorithmiscalled c-competitive,ifoneveryinputinstanceitachieves at leasta1/c-fractionoftheoptimal(‘‘offline’’)profit. Wegivelowerboundsforthecompetitivityofonlinealgorithmsandproposealgorithmswhichmatch this lowerbounduptoaconstantfactor.