American Institute of Mathematical Sciences

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

Duplicating in batch scheduling

Yuzhong Zhang 1, , Chunsong Bai 2, , Qingguo Bai 3, and  Jianteng Xu 4,

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., China
3. 

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

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).
Keywords: Duplicating, Parallel machines., Integer programming, Batch scheduling.
Mathematics Subject Classification: Primary: 90B35; Secondary: 68M2.
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
[1]

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
[2]

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
[3]

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
[4]

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
[5]

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
[6]

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

Tools

Metrics

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

Other articles
by authors

[Back to Top]

Copyright © 2021 American Institute of Mathematical Sciences