Machine Covering On Two Uniform Machines

This thesis study the non-preemptive maximization problem on two uniform machines, where one machine is q times as efficient on each task as is the other,with the goal of maximizing the makespan.We analyze the worse-case ratio of Algorithm LPT, and give instance to prove the tightness of the ratio.Secondly,we study the semi-online version:jobs arrive one by one in the order of non-increasing sizes.We design optimal algorithms in the intervals where Algorithm LPT is not the optimal one,and prove the competitive ratio of the algorithms.The worse-case ratio and the competitive ratio are given as piecewise functions of q.At last,instances which express as functions of q are given to prove the lower bounds of the problem.This paper includes three sections. Section 1 introduces basic knowledge of scheduling and our results.Section 2 proves the worse-case ratio of Algorithm LPT.Section 3 proves the competitive ratio of optimal algorithms and gives the lower bounds.