Duplicating in batch scheduling
Yuzhong Zhang Chunsong Bai Qingguo Bai Jianteng Xu
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 - \frac{2}{B})$- approximation algorithm and a $(2 - \frac{1}{B} + \epsilon)$ algorithm when $m$ is fixed. We also present a $4(2 - \frac{1}{B} + \epsilon)$-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 Hall et al.(1997).
keywords: Duplicating Parallel machines. Integer programming Batch scheduling
Yiju Wang Xinmin Yang Yuzhong Zhang
This special issue is dedicated to Professor Changyu Wang on the occasion of his 70th birthday in recognition of his contributions to Operations Research and its applications and his lasting impact as an educator.
Some new results on multi-dimension Knapsack problem
Yuzhong Zhang Fan Zhang Maocheng Cai
We claim a conclusion on Multi-Dimensional Knapsack Problem (MKP), which extends an important proposition by Dantzig firstly, then address to a special case of this problem, and constitute a polynomial algorithm, extending Zukerman et al's work.
keywords: integer programming Knapsack problem polynomial time algorithm approximation algorithm.

Year of publication

Related Authors

Related Keywords

[Back to Top]