Semi-online Machine Covering Problems On Two Uniform Machines

This thesis mainly concerns design and analysis of approximation algorithms on semi-online uniform machine covering problems. We first introduce basic notions scheduling problem, approximation algorithms and competitive analysis.In Chapter 2, we investigate semi-online scheduling problem on two uniform machines, where the total size of all jobs is known in advance, the objective is to maximize the minimum load of two machines. We present two optimal algorithms FF for and SF for s respectively. FF gives preference to the faster machine, and SF gives preference to the slower machine respectively, then obtain the competitive ratio:In Chapter 3, we investigate semi-online scheduling problem on two uniform machines, where the largest size of all jobs is known in advance with objective to maximize the minimum machine completion time. We present algorithms FFLS for and SFLS for s respectively, then we show that FFLS is optimal for this problem when , and SFLS is optimal for this problem when ) and the largest gap between the competitive ratio and the lower bound is about 0.064 when s ∈ [2.1479,3.83598).