Some Kinds Of On-line Scheduling On Parallel Batch Machines With Lookahead

In off-line scheduling, all information of jobs is released before the beginning of scheduling. 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. In this paper jobs arrive over time. In the lookahead model, at a time instant t, an on-line algorithm can foresee the information of all jobs arriving in the time segment (t, t+β]. Incompatible job families means that jobs which belong to different families cannot be assigned to the same batch.Parallel batch scheduling is an important kind of modern scheduling research. There are m machines in the parallel machine online scheduling. In this paper, we focus on three kinds of parallel machines online scheduling problems.The scheduling problems are denoted as follows:(1) P2｜online, p-batch,pj=1,b=∞,β,3-family｜Cmax;(2) Pm｜online, p-batch,pj=1,b=∞,β,f-family｜Cmax.(其中f为偶数)(3) Pm｜online, p-batch,Pj＝1,b=∞,β|Fmax.A description of the first one:In this problem, we consider the online scheduling of incompatible unit-length job families on two identical parallel-batch machines with lookahead. In this paper, the pro-cessing time of the jobs is one. The objective is to minimize the makes-pan. The capacity of the machine is unbounded. Its characteristic is that all the information of workpiece is gradually released in stages to policy makers. Decision makers can only make ordering decisions on the basis of the existing information. The fine degree of online algorithm usually use its competitive ratio.For problem l\online, p-batch. pj=1,b=∞,β, two-family|Cmax Fu et al.[1] provided a best possible online algorithm with a competitive ratio of (?)+3/4In Section2, we first present a lower bound of1+α. where α is a positive root of2a2+(1+β)α+β-2=0Then 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 the online scheduling of incompatible unit-length job families on m identical parallel-batch machines with lookahead.The objective is to minimize the makes-pan. In this problem, we have m parallel machines. Parallel-batch scheduling is an important model of modern scheduling. In unbounded parallel batch scheduling, an infinite capacity machine can process many jobs simultaneously as a batch. But jobs which belong to different families cannot be assigned to the same batch. The capacity of a batch can be finite or infinite. In this paper, we deal with the problem with infinite 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+β].In Section3, we first provide a best possible online algorithm of competitive ratio of1+αf for0≤β<1, where αf is a positive root of the equation f·α2f+2(β+1) αf+2β-f=0. f is an even number.A description of the third one:In this problem, we consider the on-line scheduling of unit-length jobs on m identical parallel-batch machines. Jobs arrive over time. The objective is to minimize maximum flow-time. 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+β].In Section4, we provide a best possible online algorithm of a competitive ratio of1+αf for0<β≤1where a is the positive root of α2+(β+1+m)α+(m+1)β-1=0.