Approximation Algorithms for Multi-processor Task Scheduling Problems on Identical Parallel Processors

Abstract

In this thesis we present approximation algorithms for some multi-processor task scheduling problems. In a scheduling problem, there is a set of processors P that can be used to process a set of tasks T and the goal is to find a feasible scheduling of the tasks on the processors, while optimizing an objective function. In a multi-processor task scheduling problem, tasks can be executed on several processors simultaneously. In scheduling problems, tasks can be preemptive or non-preemptive. Preemptive tasks can be interrupted during their execution and resumed later with no cost. In contrast, a non-preemptive task cannot be interrupted during its execution. In Chapter 2 we propose polynomial time algorithms using linear programming to solve the preemptive scheduling problems for minimizing the maximum completion time, the maximum latency, and the maximum flow time. In Chapter 3 we consider two non-preemptive scheduling problems: the problem of minimizing the maximum completion time when tasks have minimum degree of parallelism, and problem of minimizing the maximum flow time. In Chapter 4 we consider online scheduling of multi-processor tasks with minimum degree of parallelism. In online scheduling, the scheduler does not have access to the entire input instance initially and the scheduler will have access to tasks' characteristics over time. We show that it is not possible for an online scheduler to find a feasible scheduling for all input instances of the problem. We propose a bicriteria (O(log m),1)-approximation algorithm for the problem.