On-Line And Efficient Algorithms For Scheduling Problems In Communication Networks

In this thesis, we deal with a number of scheduling problems which arise in communication networks. This thesis consists of two parts. In the first part, we focus on parallel jobs scheduling, where a job may require more than one machine simultaneously. The network topologies between machines are considered how to influence the schedule. The concrete network topologies could be PRAM, Line, Mesh, Hyper-cube and so on. A subset of machines can work together only if they are connected. Parallel jobs require some part of the machines (e.g. a mesh of a smaller size), and can be processed simultaneously on any subset of machines with that specific network topology. Different variants on on-line scheduling are explored, such as the model where jobs arrive on dependencies and the model where jobs arrive over list. Our goal is to schedule a given set of jobs so that all the constraints are satisfied and a certain objective is optimized, such as makespan minimization or throughput maximization.We present on-line algorithms for these scheduling problems and adopt the standard performance measure - competitive ratio to analyze them. We also provide lower bounds with some specific instances. It is showed that the complexity of the network topologies and various variants of on-line models impose a big influence on the schedule. On the other hand, we show that it is quite helpful if we know some partial information of the jobs in advance in order to improve the quality of the schedule. We also design efficient algorithms for some off-line problems, where we know the full information on jobs beforehand, such as the malleable parallel jobs...