Design And Analysis Of Algorithms For Two Kinds Of Parallel Machine Scheduling Problems

This thesis investigates two kinds of non-preemptive parallel machine schedulingproblems：one is the online hierarchical scheduling problem on m parallel identical machineswith minimizing the total completion time of all jobs；the other is a scheduling on two parallelidentical machines sharing a single server in charge of loading and unloading jobs withminimizing the makespan（makespan）. The thesis is organized as follows. In chapter1, webriefly introduce the basic theory of the scheduling.In chapter2, we study online hierarchical scheduling problem on m parallel identicalmachines. For the problem with unit-size jobs, the lower bound and algorithm are considered.The job with lower hierarchy can only be processed on the first one machine and the job withhigher hierarchy can be processed on any one of m machines. We first show that the lowerbound of this problem is at least m=2, the lower bound is16/131.2308, which is an improvement of the previous result of1.1573. We then present a greedy algorithm and show its tight competitive ratio isbased on analyzing the structure of the instance in the worst case, which isdifferent from the most common method of competitive analysis. Finally, we propose anoptimal algorithm with competitive ratio of16/13for the special case where m=2.In chapter3, we study parallel identical machines sharing a single server, which is used toload/unload the job on the machine before/after its processing. The machine cannot process jobwhen then server is loading/unloading a job onto/from a machine.We mainly consider classicalalgorithms LS and LPT for the problem where the loading and unloading times both are equalto one time unit. We first analyze the structure of list scheduling for the problem. Finally, by thethought of blocking we show that the tight worst case ratios of LS and LPT are12/7and4/3,respectively. In chapter4, we mainly give some remarking conclusions about the future study.