Studies on Online and Semi Online Scheduling

Abstract

This thesis studies computational hardness, algorithmic competitiveness, and fairness newlinefor offline, online, and semi-online variants of the Multiprocessor Scheduling Problem newline(MPSP). In offline scheduling, an algorithm knows the whole sequence of input jobs at newlinethe outset. In online scheduling, an algorithm receives input jobs one after the other and newlinemakes an irrevocable scheduling decision on each received job without knowledge of newlinesuccessive jobs. Semi-online scheduling is a variant of online scheduling where an online newlinealgorithm schedules a received job with an Extra Piece of Information (EPI) about the newlineentire input job sequence. Online scheduling in a multiuser system allows multiple users newlineto submit their jobs simultaneously. An algorithm here receives at most one job from newlineevery user at each time step and irrevocably schedules a batch of jobs before receiving the newlinenext batch. The objective is to minimize the makespan of the job schedule. newlineResearch Motivation : A systematic study to understand the hardness of the offline Multiuser newlineMultiprocessor Scheduling Problem (MUMPSP) with the exploration of the exhaustive newlinesolution space is an emerging area of investigation. Although online multiprocessor newlinescheduling has been well-studied in the literature, the design of novel models and newlineconstant-competitive online algorithms for online scheduling in multiuser multiprocessor newlinesystems have been a potential research challenge. Many authors developed fairness-based newlineperformance measures for online scheduling algorithms by considering various resource newlineallocation criteria. However, there is less attention to the design of a user s objectivebased newlinefairness measure. In semi-online scheduling, the non-trivial research challenge is newlineto explore realistic EPI that is essential and sufficient to improve the performance of bestknown newlineonline scheduling algorithms. newline