Online Algorithms For Two Kinds Of Online Parallel Machine Scheduling Problems

In the thesis, we mainly investigate two kinds online parallel machine scheduling prob-lems: one is the online hierarchical scheduling problem with m parallel identical machinesand the goal is minimizing the total completion time of all jobs; The other one is schedulingjobs on two parallel identical machines with a single server, which contains two situations:one is using the server loading and unloading jobs, and the other is just unloading the jobswithout loading, whose goals are both minimizing the makespan.Our thesis contains four chapters.In chapter1, we introduce some basic concepts and theories of the scheduling problem.In chapter2, we mainly consider the online hierarchical scheduling problem on m parallelidentical machines, which jobs are unit-size. Dividing the problem into two cases, the goalsof the two cases are both minimizing the total completion time of all jobs. The frst one is1machine with lower hierarchy as well as the last m1machines’ hierarchy are higher, wewill provide an online algorithm with a competitive ratio1+√2(m1)(16m+19)(m1)2+1+3m2, whichis an improvement of LS. The second is frst k machines are lower hierarchy while the lastm k machines’ hierarchy are higher, we will prove the competitive ratio of greedy algorithmfor this situation is1+√2k(m k)m(4km3k2+k). At last, we point out some thinking for researchingthe problem in the future.In chapter3, we study two parallel machines sharing a common single server in onlinesituation. We also divide this into two situations and the goals are both minimizing themakespan: one is used to load/unload the job on the machine before/after its processing, thenwe provide an online algorithm with a competitive ratio5/3; The second is just unloadingthe job without loading, we frst show the lower bound of the greedy algorithm for it is atleast8/5, then we provide an online algorithm and prove that its competitive is11/7. Atlast, we prove the lower bound of both the situations is at least3/2. Furthermore, we showthat the lower bound of the frst one is at least8/5if the online algorithm satisfes a certainconstraint.In chapter4, we summarize our results and list some remarking conclusions for the futurestudy.