October  2007, 3(4): 685-692. doi: 10.3934/jimo.2007.3.685

Duplicating in batch scheduling


School of Operations Research and Management Sciences, Qufu Normal University, Rizhao, Shandong, 276826


Department of Mathematics, Fuyang Teachers College, Fuyang, Anhui, 236032, P.R., China


School of Operations Research and Management Sciences, Qufu Normal University, Rizhao, Shandong, 276826, P.R., China


School of Management, Harbin Institute of Technology, Harbin, Heilongjiang, 150001, P.R., China

Received  November 2006 Revised  July 2007 Published  October 2007

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).
Citation: Yuzhong Zhang, Chunsong Bai, Qingguo Bai, Jianteng Xu. Duplicating in batch scheduling. Journal of Industrial & Management Optimization, 2007, 3 (4) : 685-692. doi: 10.3934/jimo.2007.3.685

Xu Zhang, Xiang Li. Modeling and identification of dynamical system with Genetic Regulation in batch fermentation of glycerol. Numerical Algebra, Control & Optimization, 2015, 5 (4) : 393-403. doi: 10.3934/naco.2015.5.393


Ardeshir Ahmadi, Hamed Davari-Ardakani. A multistage stochastic programming framework for cardinality constrained portfolio optimization. Numerical Algebra, Control & Optimization, 2017, 7 (3) : 359-377. doi: 10.3934/naco.2017023


Luke Finlay, Vladimir Gaitsgory, Ivan Lebedev. Linear programming solutions of periodic optimization problems: approximation of the optimal control. Journal of Industrial & Management Optimization, 2007, 3 (2) : 399-413. doi: 10.3934/jimo.2007.3.399


Xiaohong Li, Mingxin Sun, Zhaohua Gong, Enmin Feng. Multistage optimal control for microbial fed-batch fermentation process. Journal of Industrial & Management Optimization, 2021  doi: 10.3934/jimo.2021040


Longxiang Fang, Narayanaswamy Balakrishnan, Wenyu Huang. Stochastic comparisons of parallel systems with scale proportional hazards components equipped with starting devices. Journal of Industrial & Management Optimization, 2020  doi: 10.3934/jimo.2021004


Xiaomao Deng, Xiao-Chuan Cai, Jun Zou. A parallel space-time domain decomposition method for unsteady source inversion problems. Inverse Problems & Imaging, 2015, 9 (4) : 1069-1091. doi: 10.3934/ipi.2015.9.1069

2019 Impact Factor: 1.366


  • PDF downloads (42)
  • HTML views (0)
  • Cited by (0)

[Back to Top]