Duplicating in batch scheduling
Yuzhong Zhang Chunsong Bai Qingguo Bai Jianteng Xu
Journal of Industrial & Management Optimization 2007, 3(4): 685-692 doi: 10.3934/jimo.2007.3.685
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
Scheduling with step-deteriorating jobs to minimize the makespan
Cuixia Miao Yuzhong Zhang
Journal of Industrial & Management Optimization 2017, 13(5): 1-10 doi: 10.3934/jimo.2018131

In this paper, we consider the scheduling with step-deteriorating jobs. The objective is to minimize the makespan. We first propose a property of any optimal schedule after analyzing the NP-hardness for the parallel-machine scheduling with a common deteriorating date, and then present a fully polynomial time approximation scheme for the case where the number of machines $m$ is a constant and jobs have anti-agreeable parameters. Furthermore, we show that the single-machine scheduling is NP-hard in the strong sense if jobs have distinct release dates and distinct deteriorating dates.

keywords: Scheduling step-deteriorating anti-agreeable NP-hard fully polynomial time approximation scheme
Yiju Wang Xinmin Yang Yuzhong Zhang
Journal of Industrial & Management Optimization 2007, 3(4): i-iv doi: 10.3934/jimo.2007.3.4i
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
Journal of Industrial & Management Optimization 2005, 1(3): 315-321 doi: 10.3934/jimo.2005.1.315
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]