Duplicating in batch scheduling (Q2468842)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Duplicating in batch scheduling |
scientific article |
Statements
Duplicating in batch scheduling (English)
0 references
11 February 2008
0 references
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)].
0 references
scheduling
0 references
algorithm
0 references
approximation
0 references