Online And Semi-online Scheduling Problems On Two Parallel Machines

This paper mainly investigates online and semi-online scheduling problems on two parallel machines(identical machines and uniform machines),where the jobs arrive one by one in a given list and the objective is to minimize the makespan.In online version,each job is required to be assigned irrevocably on one of machines as soon as it arrives,without any information of the following jobs.The difference between semi-online version and online version is that some partial information about the jobs is known in advance in semi-online version.In Chapter 2,we investigate one semi-online scheduling problem with partial informa-tion of job size on two identical machines.Assume that the maximum job size is tp and all jobs have their processing times between p and tp (p>0,t≥1).The lower bounds max{ are given.And we design an optimal algorithm A1 with the competitive ratio maxIn Chapter 3,we investigate the semi-online scheduling problem with known maximum job size on two uniform machines with the speed ratio s(s≥1).The maximum size of all jobs pmax is known for scheduler. For 1≤s≤(?), we present an optimal algorithm H1 with the competitive ratio max For s≥(?), we present an algorithm H2 with the competitive ratio min{(s+1)/s, max For 1.559≤s≤2.293 and s≥(3+(?))/2, we give lower bounds (s+2)/(s+1) and (s+1)/s,respectively.Then algorithm. H2 is optimal for 1.559≤s≤2 and s≥(3+(?))/2. In addition,the improvement on lower bounds is made for 2≤s≤(3+(?))/2.In Chapter 4,we consider a semi-online scheduling problem with bounded job sizes on two uniform machines.It is assumed that all jobs have their processing times between p and tp. And it is possible that no jobs with sizes p and tp come up. We prove lower bounds and give the competitive ratios of LS algorithm. The competitive ratio of LS algorithm is (1+t)/2 for (2s+(?))/(s+1)≤t≤2/s; let N∈{1,2,3,…},it is (s+1)/s for and t≥s/N;t for N≤s≤N+1 and 1≤t≤min{1/(s-N),s/N})；(1+Nt)/s for and max letα=(1+s-s2)/s2, it is (2s+1)/(s+1) for t≥(1+s)/(sα2). And LS algorithm is optimal for the above interval about s and t. Finally, we present two optimal algorithms. Algorithm Bound1 is optimal with the competitive ratio s for 1.325≤s≤(1+(?))/2 and s< t≤(s2-1)/(1+s-s2). Algorithm Bound2 is optimal with the competitive ratio (1+t)/2 for 1≤s≤(1+(?))/4 and max{2s-1,(-s+(?))/2s}≤t≤2/s, and with the competitive ratio s for s≥1.206 and s≤t≤min{2s-1,(2(s2-1))/(1+s-s2)}.In Chapter 5, we consider three online scheduling problems with reassignment on two uniform machines.In the first problem PL,one can reassign the lastκjobs of the job sequence, whereκis a finite positive integer. We point out that LS algorithm is in fact optimal for any s≥1. In the second problem Pε, the last job on each machine can be reassigned. For this problem, we prove that LS algorithm with the competitive ratio (s+1)/s is optimal for s≥(1+(?))/2. Also, we give the lower bound (?) for 1≤s<(1+(?))/2 and design an algorithm Q2RE that matches the bound. In the third problem PA, one can reassign arbitraryκjobs. For this problem, we design an algorithm Q2RA with the competitive ratio (2s+2)/(s+2).