Workpiece Parallel Machine Online Scheduling Problem With Precedence Constraints

Scheduling is to assign some tasks to time resources under some constraints, such thatone- or multi-criteria attain to the optimum. Recently, on-line scheduling is a flourishingscheduling model. On-line scheduling means that all job informations are unknown beforetheir release times. Jobs cannot be scheduled before they arrived, and jobs do not have tobe scheduled immediately upon arrival. Once they are scheduled the schedule cannot bechanged.In this paper, we consider an on-line scheduling model: on-line scheduling problemwith precedence constraints on identical parallel processors. There are n jobs, J₁, J₂,..., J_n,with precedence constraints. Each job has a release time r_j; a processing time p_j. Thesejobs need to be processed on m≥1 identical parallel processors. A task, once begun,cannot be interrupeted until it completes. Our objective is to minimize the sum of squaresof the machine completion times. Using the 3-field notation of Graham et al. [3], ourproblem is denoted as (?).The main results of this paper are as follows.(1) For the scheduling model (?), the lower bound of competitiveratio of any on-line algorithm is not less than 5/4.(2) For the scheduling model P3|p_j = 1, intree_i released at (?), the lowerbound of competitive ratio of any on-line algorithm is not less than 302/281 .(3) For the scheduling model P2|p_j = p, chains_i released at (?), the lowerbound of competitive ratio of any on-line algorithm is not less than 106/81.(4) For the scheduling model P2|p_j = 1.prec_i released at(?), the lowerbound of competitive ratio of any on-line algorithm is not less than 65/49. We also givean on-line algorithm with competitive ratio not greater than 2.(5) For the scheduling model Pm|p_j = 1,outtree_i released at (?), we givean on-line algorithm with competitive ratio not greater than m.