부산대학교 도서관

In the batch scheduling problem considered in this paper, there are $m$ machines and each machine can process at most $b$ jobs simultaneously at any time. The jobs all have unit length and arrive online. Once scheduled, 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 the batch. At any time $t$, an online algorithm is able to look ahead to jobs arriving in the time interval $(t,\lambda t+\beta]$, where $\lambda>1$, $\beta>0$. The goal of an online algorithm is to minimize the makespan of the schedule. \par The authors partition the problem into subproblems that depend on the value of $\beta$. In the first subproblem, they assume that $\beta\geq(\lambda-1)/(\lambda^m-1)$ and in the second, they assume that $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 with competitive ratio $1+\alpha_m$, where $\alpha_m$ is the positive root of 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.