Lower Bounds And Approximation Algorithms For Semi-online Order Scheduling Problems On Two Uniform Machines

In this paper, we consider some semi-online order scheduling problems on two uniform machines, where each order has at least one job. Only after all the jobs in the current order are scheduled irrevocably, the next job order can arrive. The objective is to minimize the maximum job completion time (makespan), and it is assumed that the first machine’s speed is1and the second is s (s>1).In chapter two we consider a semi-online order scheduling problem on two uniform machines, where there are at least two orders and all the orders have equal job length. We give the lower bounds and present a semi-online algorithm H to the problem. And the competitive ratio of the algorithm H is proved to be When1≤<s≤2, the competitive ratio of the algorithm H is better than the classical LS algorithm.In chapter three we consider a semi-online order scheduling problem on two uniform machines, where there are at least two orders and the largest job processing time of all the orders are equal. We give the lower bounds and present a semi-online algorithm L to this problem. And the competitive ratio of the algorithm L is proved to be When1≤5≤2,the competitive ratio of the algorithm L is better than the classical LS algorithm.In chapter four, we consider the similar problems considered in chapter two and three, but the assumption that there are at least two orders in each instance is deleted. We also give the lower bounds to both the problems. We give a semi-online algorithm A to Q2|SUM,OO|Cmax,and prove that the competitive ratio of the algorithm A is3/2.