Some Special Online Scheduling Problems On Single Parallel-Batching Machine

According to jobs’different properties, scheduling problems are divided into off-line scheduling problems and on-line scheduling problems. In off-line scheduling problems, all the job’s information is known before a scheduling decision is made. However, in this paper, we will study some kinds of standard online scheduling problems, which means that jobs arrive over time and each job’s characteristics, including release date, proccessing time and so on, are unknown until it is released.In this paper, we research some special online scheduling problems on a single parallel-batching machine. The scheduling problems are denoted as follows:(1) 1|p-batch,pj=1,b<n,2-family, on-line|Cmax(2) 1|p-batch,pj ∈ [p,(1+ф)p],b<n.qj,on-line|Dmax(3) 1|p-batch,p3 ∈ [p,(1+ф)p),β=фp,b=∞,2-family, on-line|CmaxThe description of the first model:In this model, we consider on-line scheduling problem on a bounded parallell batch machine of two incompatible families of unit-length jobs. The objective is to minimize the makespan. In this problem, the processing time of all jobs is one and the jobs which belong to different families cannot be processed in the same batch.For the problem 1|on-line, p-batch, b=∞,2-family|Cmax Fu et al. [4] provided a best possible online algorithmon with competitive ratio√17+3/4 . For the problem 1|on-line, p-batch, b=∞, f-familyCmax:, the result in Fu et al.[5] imply that the best possible online algo-rithm is (1+af)-competitive, where af is a positive root of fa2+a-f=0. For the model considered in this paper, in section 2, we give a best possible online algorithm with a competitive ratio 1+a, where a is a positive root of 2a2+a-2=0.The description of the second model:In this model, we consider on-line scheduling problem on a bounded parallel batch machine with the assumption that all jobs have their processing times in [p,(1+ф)p], where ф=√5-1/2. The objective of the problem considered in section 3 is to minimize the time by which all jobs have been delivered, where Dmax= maxDj= max{Cj+qj}.Yang Fang et al. [17] offered a best possible online algorithm with competitive ratio ф=√5+1/2 for the problem 1|rjpj ∈ [p,(1+ф)p], b<+∞, on-line|Cmax and also provided a best possible online algorithm with competitive ratio ф=√5+1/2 for the problem 1|rj,pj ∈ [p,,(1+ф>)p],b=∞, qj,on-line|Lmax. For the model considered in this paper, in section 3, we established a best possible online algorithm with competitive ratio ф=√5+1/2.The description of the third model:In this model, we studies on-line scheduling on a single parallel batching machine of two incompatible families of jobs with lookahead where the batch capacity is bounded and we assume that all jobs have their processing times in [p,(1+ф)p]. The objective is to minimize the makespan. In this paper, lookahead parameter is defined as the length of time, in other word, at a time instant t, an on-line algorithm can foresee the information of some future jobs arriving in a finite time segment (t,t+β].Li et al. [21] offered a best possible online algorithm with competitive ratio 1+a’ for the problem 1|p-batch,pj=1,LKp,b=∞, two families, on-line|Cmax;, where a’ is a positive root of 2a2+(β+1)a+β-2=0. For the model considered in this paper, in section 4, we established a best possible online algorithm with competitive ratio φ=√5+1/2.