Task Scheduling on Parallel Processors: Semi-Online Settings and Job Placement Constraints

Scheduling tasks/jobs on parallel processors/machines is a classical scheduling problem that is well studied in the literature due to its applicability in parallel computing systems and operations research. Even though it is a well studied problem, new scheduling models that consider the emerging aspects in the continuously evolving parallel computing systems are required to analyze and improve their performance. In this thesis we initially study scheduling on parallel processors under three new semi-online paradigms with motivations from computational offloading systems (e.g. mobile cloud computing, mobile edge computing, hybrid cloud, etc.), where only partial information about the tasks is available. First, we study makespan minimization on a set of local processors and a set of remote processors under the semi-online setting where the task processing times on the local processors are known a priori, but are unknown on the remote processors. Second, considering that each offloaded task incurs a cost, we study makespan-plus-weighted-offloading-cost minimization when the task processing times are not known a priori, but their offloading costs are known. Third, we consider the scenario where offloaded task incurs non-negligible communication overhead and study makespan minimization under the semi-online setting where task communication overheads are known a priori, but their processing times are not known. For each of the above problems we propose efficient algorithms, analyze their performance in the worst case, by deriving competitive ratios, and study their average performance using simulation. Finally, we identity a new job model in scheduling on parallel processors, where a job has placement constraints and multi-processor requirement. Under the job placement constraints we solve a problem of assigning identical jobs to machines. We establish novel results for this problem under generalized objective functions. We propose a new algorithm and analyze its runtime complexity. Further, using benchmark input instances we show that the proposed algorithm has orders of magnitude lower runtime than the existing algorithms.Ph.D