Research Of Special Parallel Jobs Scheduling

This thesis mainly concerns design and analysis of approximation algorithms on two special parallel jobs scheduling problems. The goal is to minimize the makespan. Jobs come over list. A parallel job may require a number of machines for its processing at the same time. Upon arrival of a job, its processing time and the number of requested machines become known, and it must be scheduled immediately without any knowledge of future jobs.We first introduce basic notions of scheduling problem, approximation algorithms and competitive analysis.In Chapter 2, we deal with the case that jobs arrive in non-increasing order of sizes. First, we show the competitive ratio of algorithm greedy is at most11/4, but at least5/2. In the second part, we show an improved greedy algorithm has a competitive ratio of at most 1＋(10^1/2/2).In Chapter 3, we assume that jobs arrive in non-increasing order of processing times. We obtain an upper botmd of 2 by employing a greedy algorithm, which schedules jobs as early as possible.