학술논문
Online algorithms for scheduling unit length jobs on unbounded parallel-batch machines with linearly lookahead.
Document Type
Journal
Author
Jiao, Chengwen (PRC-ZUT-CSC) AMS Author Profile; Yuan, Jinjiang (PRC-ZHEN-SMS) AMS Author Profile; Feng, Qi (PRC-ZUT-CSC) AMS Author Profile
Source
Subject
68 Computer science -- 68W Algorithms
68W27Online algorithms
68W27
Language
English
ISSN
17937019
Abstract
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.