Some Problems In Parallel Machine Scheduling Under A Grade Of Service Provision

This thesis mainly studies parallel machine scheduling under a grade of service provision. Each job and machine are labelled with prespecified grade of service (or GoS) levels. Each job is allowed to be processed by a particular machine only when the GoS level of the job is no less than the GoS level of the machine. The goal is to minimize the maximum machine completion time, called makespan. This problem is proposed by Hwang et al. recently. For this problem, we present a new algorithm, which improved the known result 2 -1/(m-1). The thesis consists of three chapters.The first chapter gives some introduction and prelimilaries for scheduling problems. The second chapter investigates parallel machine scheduling problem with two grades of sevice provision. We present an algorithm MMF which is modified from MULTIFIT. The worstcase ratio of MMF is 4/3 + (1/2)~k, where k is the desired number of iteration. The third chapter considers the general case for the problem under consideration. The goal is to minimize the makespan under the constraint that all requests are satisfied. We present an algorithm with a worst-case ratio of 3/2+ (1/2)~k. We further present an algorihtm with a worst-case ratio of 5/4+ (1/2)~k for m = 3 and show the bound is tight.