New utilization criteria for online scheduling [Elektronische Ressource] / von Mohamed Hussein

NewUtilizationCriteriaforOnlineSchedulingDissertationzurErlangungdesGradeseinesD o k t o r s d e r N a t u r w i s s e n s c h a f t e nderUniversitat¨ DortmundamFachbereichInformatikvonMohamedHusseinDortmund2005iiTagdermundlichen¨ Prufung:¨ 18.07.2005Dekan: Prof. Dr. BernhardSteffenGutachter: Prof. Dr. Ing. UweSchwiegelshohnProf. Dr. IngoWegeneriiiAbstractIntheclassicalschedulingproblems,ithasbeenassumedthatcompleteknowledgeofthe problem was available when it was to be solved. However, scheduling problemsin the real world face the possibility of the lack of the knowledge. Uncertainties fre quently encountered in scheduling environments include the appearance of new jobsand unknown processing times. In this work, we take into account these realistic is sues.Thisthesisdealswiththeproblemofnon preemptiveschedulingindependentjobsonmidenticalparallelmachines. Inouronlinemodel,thejobsaresubmittedovertimenon clairvoyantly. Therefore, the processing times of the jobs are unknown until theycomplete. Further, we assume that the ratio of weight to processing time is equal foralljobs,thatis,alljobshavethesamepriorities. Thejobsareassignedtothemachinesinanondelayfashion. Ourmainschedulingobjectiveistomaximizetheutilizationofthesystem.We show that the commonly used makespan criterion usually cannot reflect thetrue utilization of this kind of online scheduling problems.