Parallel Machines On-line Scheduling Problems With Chain Precedence Constraints And Lookahead

In off-line schedule, all information of jobs is released before the beginning of schedul-ing. In this paper, we discuss on-line-over-time scheduling problems. Over-time means that the information of the jobs is not known in advance, but released one by one over time.Parallel batch scheduling is an important problem of scheduling research. There are m machines in the parallel machine online scheduling. We need to schedule the jobs that have been come, that is putting a job on which machine. In this paper, we focus on two kinds of parallel machines online scheduling problems.The scheduling problems are denoted as follows:(1) P2|online, chains, pj∈[p,(1+α)p]|Cmax;(2) Pm|online,p-batch, pj=1, b<∞,β|Cmax.A description of the first one:In this problem, we consider the scheduling of jobs on two parallel machines with grouped processing times and chain precedence constraints to minimize the makespan. The processing time of the jobs is a variable over the interval [p,(1+α)p]. In this paper, the precedence constraints between the jobs are given by independent chains. Jobs on one chain have the same arrival time. Once a chain arrives, all the information of the jobs is known.In Section2, we first present a lower bound of1+α, where α=(?)-1. Then we provide an algorithm with competitive ratio1+α, and show the algorithm is best possible.A description of the second one:In this problem, we consider online scheduling of unit length jobs on m parallel-batch machines with lookahead to minimize makespan. In this problem, we have m parallel machines. Parallel-batch scheduling is an important model of modern scheduling. In parallel batch scheduling, a machine can process at most b jobs simultaneously as a batch with capacity b. The capacity of a batch can be finite or infinite. In this paper, we deal with the problem with finite capacity. Jobs in a batch have a common starting time and a common completion time.The processing time of a batch is defined to be the maximum processing time of the jobs in the batch.Denote by β the lookahead length in the online setting.Then,at a time instant t,an online algorithm can foresee the information of all the jobs arrival in the time segment(t,t+β].For problem Pm|online,p-batch,pJ=1,b<∞,0<β≤1/6|Cmax,Li,Zhang and Yang[17]provide a best possible online algorithm.In this paper,we provide a best possible online algorithm for0<β≤1with competitive ratiowhere α1is the positive root of α2+(β+1)α+β-1=0,and α2=(?).