부산대학교 도서관

In the batch scheduling problem considered in this paper, there are $m$machines and each machine can process at most $b$ jobs simultaneouslyat any time. The jobs all have unit length and arrive online. Oncescheduled, all jobs in a batch have the same starting and ending time.The ending time is defined by the length of the longest job in thebatch. At any time $t$, an online algorithm is able to look ahead tojobs arriving in the time interval $(t,\lambda t+\beta]$, where$\lambda>1$, $\beta>0$. The goal of an online algorithm is to minimizethe makespan of the schedule.\par The authors partition the problem into subproblems that depend on thevalue of $\beta$. In the first subproblem, they assume that$\beta\geq(\lambda-1)/(\lambda^m-1)$ and in the second, they assumethat $0<\beta<(\lambda-1)/(\lambda^m-1)$. For the first subproblem,they prove that an online algorithm can achieve competitive ratio 1.For the second subproblem, they present an online algorithm withcompetitive ratio $1+\alpha_m$, where $\alpha_m$ is the positive rootof the equation$$(1+\alpha_m)^{m+1}\lambda^m+(1+\beta-\lambda)\sum_{i=1}^m(1+\alpha_m)^i\lambda^{i-1}=2+\alpha_m,$$and prove that no better online algorithm exists.