Parallel Machine Scheduling With Chains Precedence Constraints

In the classical problems of scheduling theory, people always assume that all information of jobs are released before the beginning of scheduling. These problems are called off-line scheduling problems. But, in practice, the information of jobs are sometimes unknown in advance, but released one by one along with the flowing of time. These problems are called on-line scheduling problems.In this paper, we consider the scheduling problem of nonpreemptive jobs, with chains precedence constraints on identical parallel machines, chains_i, i = 1,2,…, n, are released at different times r_j,j=1,2,…,n. The objective goal is to minimize the square sum of the makespans or the maximum lateness. The main results of this paper are as follows.(1) We study the off-line scheduling problem on two parallel processors with the every chain length of 1. The objective is to minimize the square sum of the machine makespans. The problem is denoted as P2||chain_i|=1|(?). We provide an algorithm, called modifmed LPT, and prove that the performance ratio is not greater than 1 + (?).(2) We study the on-line scheduling problem of unit-length jobs released at integer times on two parallel processors. The objective is to minimize the square sum of the machine makespans. The problem is denoted as P2|p_j=1, chainsi released at r_i|(?). We prove that the competitive ratio in an arbitrary algorithm is not less than 5/4, and asymptotically tends to 2 in dense algorithms. Then we give a best possible dense algorithm.(3) We discuss the on-line scheduling problem of equal-length jobs. The processing time p_j and due time q_j satisfy the condition CD: if job J_j⁽ⁱ⁾ is the predecessor of job J_k⁽ⁱ⁾ in chainsi, then p_j⁽ⁱ⁾=p_k⁽ⁱ⁾=p≥q_j≥q_k. The problem is denoted as 1|p_j = p, chainsi released at r_i, CD|L_max. We give a best possible algorithm of competitive ratio (?).