Duplicating in batch scheduling (Q2468842): Difference between revisions

In this paper, we firstly propose a technique named Duplicating, which duplicates machines in batch scheduling environment. Then we discuss several applications of Duplicating in solving batch scheduling problems. For the batch scheduling problem on unrelated parallel machines to minimize makespan, we give a \((4-\frac2B)\)-approximation algorithm and a \((2-\frac1B+\varepsilon)\) algorithm when \(m\) is fixed. We also present a \(4(2-\frac1B+\varepsilon)\)-competitive algorithm for the on-line scheduling problem on identical machines to minimize total weighted completion time by another technique-\(\rho\)-dual, which is proposed originally by \textit{L. A. Hall, A. S. Schulz, D. B. Shmoys} and \textit{J. Wein} [Math. Oper. Res. 22, 513--544 (1997; Zbl 0883.90064)].