Optimal algorithms for online scheduling with bounded rearrangement at the end

Especially, for the lower bound, (i) for s≥2 an improved lower bound s+2s+1 is obtained, which is better than (s+1)2s2+s+1 (Liu et al. (2009) [9]); (ii) for 1+52≤s<2, an improved lower bound s2s2−s+1 is obtained, which is better than (s+1)2s2+s+1 (Liu et al. (2009) [9]). For the upper bound, (i) for s≥2 and K=1, a new upper bound s+2s+1 is obtained, which is optimal and better than the one s+1s in Liu et al. (2009) [9]; (ii) for 1+52≤s<2 and K=2, an upper bound s2s2−s+1 is proposed, which is optimal and better than the previous one s+1s in Liu et al. (2009) [9]; (iii) for s<1+52 and K=2, an upper bound (s+1)2s2+s+1 is obtained, which is also optimal and better than the previous one min{s+1s,(s+1)2s+2} in Liu et al. (2009) [9].