Online Scheduling With Eligibility Constraints

In this paper,we study an online-list scheduling problem on a set of m multipurpose machines for which the objective is to minimize the makespan. It is assumed that there are two different job types, the machines can also be divided into three categories, s machines can only eligible to process jobs of type1, m-k machines can only eligible to process jobs of type2, k-s machines eligible to process jobs of type1and type2, where k≥s Jobs arrives to the online-list.The main results of this paper are as follows:For the case of m=3,k=2,s=1, we show that there is no on-line algorithm with competitive ratio less than For the case of m=5,k=4,s=1, we show that there is no on-line algorithm with competitive ratio less than1.7. For the case of7/12≤s/k≤4/5, we show that there is no on-line algorithm with competitive ratio less than1+(?)/2. we also show that there is no on-line algorithm with competitive ratio less than. Where x≈4.0489is the unique positive root of the equation x3-3x2-4x-1=0.