Duplicating in batch scheduling

Yuzhong Zhang; Chunsong Bai; Qingguo Bai; Jianteng Xu

doi:10.3934/jimo.2007.3.685

Article Contents

2007, Volume 3, Issue 4: 685-692. Doi: 10.3934/jimo.2007.3.685

This issue Previous Article Levitin-Polyak well-posedness in generalized variational inequality problems with functional constraints Next Article On saddle points of a class of augmented lagrangian functions

Duplicating in batch scheduling

1.
School of Operations Research and Management Sciences, Qufu Normal University, Rizhao, Shandong, 276826
2.
Department of Mathematics, Fuyang Teachers College, Fuyang, Anhui, 236032, P.R.
3.
School of Operations Research and Management Sciences, Qufu Normal University, Rizhao, Shandong, 276826, P.R.
4.
School of Management, Harbin Institute of Technology, Harbin, Heilongjiang, 150001, P.R.

Received: October 31, 2006

Revised: June 30, 2007

Published: September 2007

Abstract Related Papers Cited by

Abstract

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:

Mathematics Subject Classification: Primary: 90B35; Secondary: 68M20.

Citation:

Article Metrics

HTML views() PDF downloads(83) Cited by(0)

Duplicating in batch scheduling

Abstract

Access History

Article Metrics

Access History

Other Articles By Authors

Catalog

Duplicating in batch scheduling

Abstract

Access History

SHARE

Article Metrics

Access History

Other Articles By Authors

Catalog

Export File

Citation

Format

Content