A Study Of Online Hierarchical Scheduling And Some Related Problems

Rapid developing modern industry is giving birth to more and more new combinatorialoptimization models. One important branch is the scheduling problem withhierarchy settings, which has received many researchers' attention recently. This thesismainly studies online parallel machines scheduling with hierarchy settings. Fivechapters are made.In Chapter 1, we first introduce scheduling problem, with the basic conception,theory and results included, then we give a description for hierarchical scheduling problem,as well as related notations and definitions.Chapter 2 studies general hierarchical scheduling on m parallel identical machines.For the fractional model, we give both online algorithm and lower bound basedon solutions of mathematical programming. For any given m, the competitive ratio ofour algorithm achieves the lower bound by numerical calculation. Next we consider theintegral model, where both a general algorithm for any m and an improved algorithmwith better competitive ratios for m=3,4,5 are presented. We show that the competitiveratio of the general algorithm is at most one more than that of the algorithm for thecorresponding fractional model.In Chapter 3, we investigate online hierarchical scheduling on m parallel identicalmachines with two hierarchies. For both the fractional model and the model with unitjob size, optimal algorithms are given, which have competitive ratio of (?) and3/2 respectively. All the algorithms are proved to be optimal in the sense of any numberof machines m and any hierarchy settings k. Integral model is also studied. We designan online algorithm with competitive ratio 1+(?)＜7/3, which improves theprevious upper bound for the problem. The performance for some pairs of k and m isfurther improved by another algorithm. Besides, it is shown that any online algorithmis at least 2-competitive when k≥3 and m≥3/2(k+1) and lower bounds for someother pairs of m and k are also obtained.Chapter 4 discusses online hierarchical scheduling on two uniform machines. Wepresent optimal online algorithm with respect to the speed ratio s of the machines. For0＜s＜1, it has a competitive ratio of min{1+s,(?)}. For s≥1, the competitiveratio is (?). In Chapter 5, we consider two models of online coupon consumption problem thatarise from real life, which are closely related with scheduling and bin packing problems.The first model is the discount coupon consumption. We propose different online consumptionpolicies (algorithms) and lower bounds for different number of purchasablecoupons. These policies are shown to be optimal for any discount rate if the couponscan be arbitrarily purchased or at most one or two coupons are purchasable. Anothermodel is consuming for one free coupon. We note the online problem is unboundedand study the case with known total pay scales. Policies are designed depending uponit and shown to perform at most 0.129 worse than the optimal policies.