On-line Parallel Machine Scheduling With Chains Precedence Constraints

In classic problems of scheduling theory,all information of jobs is released before the beginning of scheduling.In practice,however,the information of jobs is not known in advance,but released one by one along with the flowing of time.Scheduling decisions have to be made without knowledge of future releases.In other words,the scheduler has to schedule jobs in an online over time fashion.In this paper,we investigate parallel machine on-line scheduling problem with chains precedence constraints to minimize the makespan.Here the processing times of the jobs are the same.The jobs have precedence constraints which are parallel chains.All the information of jobs on the chain is not known until the chain arrives.The jobs are processed on two identical and parallel machines in accordance with the precedence constraints.We can express this problem with three field notation as P2|p_j=p,chains_i released at r_i|Cmax.In a paper published in SIAM J.Comput.(2005),Huo and Leung gave a lower bound of 16/15,and concluded that it is impossible to get an optimal online algorithm for this problem.We first give a better bound of 1+α(α=((13)^1/2-3)/2)≈1.3028 by constructing a special instance,and present a best possible on-line algorithm whick forms the main body of this thesis.Next,we consider the integer case of this problem.We give a lower bound of max{(p+[αp])/p, (3p)/(2p+[αp])} for fixed p,and conclude that,for arbitrary integer p,1+αis a lower bound of the integer case problem too.Finally,we give a best possible algorithm of this problem by modifying the algorithm for arbitrary case.