Online P-batch Scheduling With Equal-proccessing-time Jobs And Precedence Constraints

The research of classic problems of scheduling theory has more than half a century.People have already obtained a considerable achievement about it. But it has some flawsthat all information of jobs are clear. That is, all information of jobs are released beforethe beginning of scheduling. But, in practice, the information of jobs are not known inadvance in some situation, the jobs are released one by one along with the flowing of time.The scheduler has to make scheduling decisions without knowledge of future releases. Thisis online scheduling problem.In this paper, we consider the online p-batch scheduling with equal-proccessing-timejobs and precedence constraints. The objective function is to minimize the total completiontime. When there is a single machine, we write it as 1|prec,p_j = p,p - batch, online|∑C_jand we write it as Pm|prec,p_j = p,p - batch, online|∑C_j when there are m identicalmachines. In this article, the structural arrangements are as follows. We first study thecase about a single machine, then the parallel machines. In each case, we also divide intolimited and unlimited capacity version by the batch capacity. The main results of thispaper are as follows.(1) For 1|prec,p_j = p,p - batch,b =∞,online|∑C_j, we give a best possible onlinealgorithm with the worst-case ratio 1+α=(?),(2) For 1|prec, p_j = p,p - batch, b＜∞, online|∑C_j, we give an online algorithm withthe worst-case ratio no more than 2;(3) For Pm|prec, P_j = p,p - batch, b =∞, online|∑C_j, we give a best possible onlinealgorithm with the worst-case ratio 1 +α_m, whereα_m is a solution of (1 +α_m)^m+1 - (1 +α_m) = 1 ;(4) For Pm|prec,p_j = p,p - batch, b＜∞,online|∑C_j, we give an online algorithmwith the worst-case ratio no more than 2.