• Previous Article
    Optimal control of a parabolic distributed parameter system using a fully exponentially convergent barycentric shifted gegenbauer integral pseudospectral method
  • JIMO Home
  • This Issue
  • Next Article
    Integrated recycling-integrated production - distribution planning for decentralized closed-loop supply chain
April 2018, 14(2): 497-510. doi: 10.3934/jimo.2017057

An improved 2.11-competitive algorithm for online scheduling on parallel machines to minimize total weighted completion time

1. 

School of Mathematics and Information Science, Henan Polytechnic University, Jiaozuo, 454000, China

2. 

Department of Automation, Xiamen University, Xiamen, 361005, China

* Corresponding author: jipingtao@gmail.com

# These authors contributed equally to the work

Received  February 2016 Revised  September 2016 Published  June 2017

Fund Project: This work is supported by the National Natural Science Foundation of China (11501171,11571321,11201391), the Doctoral Foundation of Henan Polytechnic University (B2016-60), and the Fundamental Research Funds for the Central Universities of China (Grant No. 20720160085)

We revisit the classical online scheduling problem on parallel machines for minimizing total weighted completion time. In the problem, a set of independent jobs arriving online over time has to be scheduled on identical machines, where the information of each job including its processing time and weight is not known in advance. The goal is to minimize the total weighted completion time of the jobs. For this problem, we propose an improved 2.11-competitive online algorithm based on a kind of waiting strategy.

Citation: Ran Ma, Jiping Tao. An improved 2.11-competitive algorithm for online scheduling on parallel machines to minimize total weighted completion time. Journal of Industrial & Management Optimization, 2018, 14 (2) : 497-510. doi: 10.3934/jimo.2017057
References:
[1]

E. J. Anderson and C. N. Potts, Online scheduling of a single machine to minimize total weighted completion time, Mathematics of Operations Research, 29 (2004), 686-697. doi: 10.1287/moor.1040.0092.

[2]

M. C. ChouM. Queyranne and D. Simchi-Levi, The asymptotic performance ratio of an on-line algorithm for uniform parallel machine scheduling with release dates, Mathematical Programming, 106 (2006), 137-157. doi: 10.1007/s10107-005-0588-1.

[3]

J. R. Correa and M. R. Wagner, LP-based online scheduling: from single to parallel machines, Mathematical Programming, 119 (2009), 109-136. doi: 10.1007/s10107-007-0204-7.

[4]

M. X. GoemansM. QueyranneA. S. SchulzM. Skutella and Y. Wang, Single machine scheduling with release dates, SIAM Journal on Discrete Mathematics, 15 (2002), 165-192. doi: 10.1137/S089548019936223X.

[5]

R. L. GrahamE. L. LawlerJ. K. Lenstra and A. H. G. R. Kan, Optimization and approximation in deterministic sequencing and scheduling: A survey, Annals of Discrete Mathematics, 5 (1979), 287-326. doi: 10.1016/S0167-5060(08)70356-X.

[6]

L. A. HallA. S. SchulzD. B. Shmoys and J. Wein, Scheduling to minimize average completion time: Off-line and on-line approximation algorithms, Mathematics of Operations Research, 22 (1997), 513-544. doi: 10.1287/moor.22.3.513.

[7]

T. Kawaguchi and S. Kyan, Worst case bound of an LRF schedule for the mean weighted flow-time problem, SIAM Journal on Computing, 15 (1986), 1119-1129. doi: 10.1137/0215081.

[8]

P. H. Liu and X. W. Lu, On-line scheduling of parallel machines to minimize total completion times, Computers & Operations Research, 36 (2009), 2647-2652. doi: 10.1016/j.cor.2008.11.008.

[9]

R. MaJ. P. Tao and J. J. Yuan, Online scheduling with linear deteriorating jobs to minimize the total weighted completion time, Applied Mathematics And Computation, 273 (2016), 570-583. doi: 10.1016/j.amc.2015.10.058.

[10]

R. Ma and J. J. Yuan, Online tradeoff scheduling on a single machine to minimize makespan and total weighted completion time, International Journal of Production Economics, 158 (2014), 114-119. doi: 10.1016/j.ijpe.2014.07.027.

[11]

N. Megow and A. S. Schulz, On-line scheduling to minimize average completion time revisited, Operations Research Letters, 32 (2004), 485-490. doi: 10.1016/j.orl.2003.11.008.

[12]

C. PhillipsC. Stein and J. Wein, Minimizing average completion time in the presence of release dates, Mathematical Programming, 82 (1998), 199-223. doi: 10.1007/BF01585872.

[13]

R. Sitters, Efficient algorithms for average completion time scheduling, in Integer Programming and Combinatorial Optimization (eds. F. Eisenbrand and F. Shepherd), vol. 6080 of Lecture Notes in Computer Science, Springer, (2010), 411-423. doi: 10.1007/978-3-642-13036-6_31.

[14]

W. Smith, Various optimizers for single-stage production problem, Naval Research Logistics Quarterly, 3 (1956), 59-66. doi: 10.1002/nav.3800030106.

[15]

J. P. Tao, A better online algorithm for the parallel machine scheduling to minimize the total weighted completion time, Computers & Operations Research, 43 (2014), 215-224. doi: 10.1016/j.cor.2013.09.016.

[16]

J. P. TaoR. H. Huang and T. D. Liu, A 2.28-competitive algorithm for online scheduling on identical machines, Journal of Industrial and Management Optimization, 11 (2015), 185-198. doi: 10.3934/jimo.2015.11.185.

[17]

A. P. A. Vestjens, On-line Machine Scheduling PhD thesis, Technische Universiteit Eindhoven, Eindhoven, Netherlands, 1997.

show all references

References:
[1]

E. J. Anderson and C. N. Potts, Online scheduling of a single machine to minimize total weighted completion time, Mathematics of Operations Research, 29 (2004), 686-697. doi: 10.1287/moor.1040.0092.

[2]

M. C. ChouM. Queyranne and D. Simchi-Levi, The asymptotic performance ratio of an on-line algorithm for uniform parallel machine scheduling with release dates, Mathematical Programming, 106 (2006), 137-157. doi: 10.1007/s10107-005-0588-1.

[3]

J. R. Correa and M. R. Wagner, LP-based online scheduling: from single to parallel machines, Mathematical Programming, 119 (2009), 109-136. doi: 10.1007/s10107-007-0204-7.

[4]

M. X. GoemansM. QueyranneA. S. SchulzM. Skutella and Y. Wang, Single machine scheduling with release dates, SIAM Journal on Discrete Mathematics, 15 (2002), 165-192. doi: 10.1137/S089548019936223X.

[5]

R. L. GrahamE. L. LawlerJ. K. Lenstra and A. H. G. R. Kan, Optimization and approximation in deterministic sequencing and scheduling: A survey, Annals of Discrete Mathematics, 5 (1979), 287-326. doi: 10.1016/S0167-5060(08)70356-X.

[6]

L. A. HallA. S. SchulzD. B. Shmoys and J. Wein, Scheduling to minimize average completion time: Off-line and on-line approximation algorithms, Mathematics of Operations Research, 22 (1997), 513-544. doi: 10.1287/moor.22.3.513.

[7]

T. Kawaguchi and S. Kyan, Worst case bound of an LRF schedule for the mean weighted flow-time problem, SIAM Journal on Computing, 15 (1986), 1119-1129. doi: 10.1137/0215081.

[8]

P. H. Liu and X. W. Lu, On-line scheduling of parallel machines to minimize total completion times, Computers & Operations Research, 36 (2009), 2647-2652. doi: 10.1016/j.cor.2008.11.008.

[9]

R. MaJ. P. Tao and J. J. Yuan, Online scheduling with linear deteriorating jobs to minimize the total weighted completion time, Applied Mathematics And Computation, 273 (2016), 570-583. doi: 10.1016/j.amc.2015.10.058.

[10]

R. Ma and J. J. Yuan, Online tradeoff scheduling on a single machine to minimize makespan and total weighted completion time, International Journal of Production Economics, 158 (2014), 114-119. doi: 10.1016/j.ijpe.2014.07.027.

[11]

N. Megow and A. S. Schulz, On-line scheduling to minimize average completion time revisited, Operations Research Letters, 32 (2004), 485-490. doi: 10.1016/j.orl.2003.11.008.

[12]

C. PhillipsC. Stein and J. Wein, Minimizing average completion time in the presence of release dates, Mathematical Programming, 82 (1998), 199-223. doi: 10.1007/BF01585872.

[13]

R. Sitters, Efficient algorithms for average completion time scheduling, in Integer Programming and Combinatorial Optimization (eds. F. Eisenbrand and F. Shepherd), vol. 6080 of Lecture Notes in Computer Science, Springer, (2010), 411-423. doi: 10.1007/978-3-642-13036-6_31.

[14]

W. Smith, Various optimizers for single-stage production problem, Naval Research Logistics Quarterly, 3 (1956), 59-66. doi: 10.1002/nav.3800030106.

[15]

J. P. Tao, A better online algorithm for the parallel machine scheduling to minimize the total weighted completion time, Computers & Operations Research, 43 (2014), 215-224. doi: 10.1016/j.cor.2013.09.016.

[16]

J. P. TaoR. H. Huang and T. D. Liu, A 2.28-competitive algorithm for online scheduling on identical machines, Journal of Industrial and Management Optimization, 11 (2015), 185-198. doi: 10.3934/jimo.2015.11.185.

[17]

A. P. A. Vestjens, On-line Machine Scheduling PhD thesis, Technische Universiteit Eindhoven, Eindhoven, Netherlands, 1997.

[1]

P. Liu, Xiwen Lu. Online scheduling of two uniform machines to minimize total completion times. Journal of Industrial & Management Optimization, 2009, 5 (1) : 95-102. doi: 10.3934/jimo.2009.5.95

[2]

Hongtruong Pham, Xiwen Lu. The inverse parallel machine scheduling problem with minimum total completion time. Journal of Industrial & Management Optimization, 2014, 10 (2) : 613-620. doi: 10.3934/jimo.2014.10.613

[3]

Jiping Tao, Ronghuan Huang, Tundong Liu. A $2.28$-competitive algorithm for online scheduling on identical machines. Journal of Industrial & Management Optimization, 2015, 11 (1) : 185-198. doi: 10.3934/jimo.2015.11.185

[4]

Jinjiang Yuan, Weiping Shang. A PTAS for the p-batch scheduling with pj = p to minimize total weighted completion time. Journal of Industrial & Management Optimization, 2005, 1 (3) : 353-358. doi: 10.3934/jimo.2005.1.353

[5]

Jiping Tao, Zhijun Chao, Yugeng Xi. A semi-online algorithm and its competitive analysis for a single machine scheduling problem with bounded processing times. Journal of Industrial & Management Optimization, 2010, 6 (2) : 269-282. doi: 10.3934/jimo.2010.6.269

[6]

Wen-Hung Wu, Yunqiang Yin, Wen-Hsiang Wu, Chin-Chia Wu, Peng-Hsiang Hsu. A time-dependent scheduling problem to minimize the sum of the total weighted tardiness among two agents. Journal of Industrial & Management Optimization, 2014, 10 (2) : 591-611. doi: 10.3934/jimo.2014.10.591

[7]

Y. K. Lin, C. S. Chong. A tabu search algorithm to minimize total weighted tardiness for the job shop scheduling problem. Journal of Industrial & Management Optimization, 2016, 12 (2) : 703-717. doi: 10.3934/jimo.2016.12.703

[8]

Le Thi Hoai An, Tran Duc Quynh, Kondo Hloindo Adjallah. A difference of convex functions algorithm for optimal scheduling and real-time assignment of preventive maintenance jobs on parallel processors. Journal of Industrial & Management Optimization, 2014, 10 (1) : 243-258. doi: 10.3934/jimo.2014.10.243

[9]

Zhichao Geng, Jinjiang Yuan. Scheduling family jobs on an unbounded parallel-batch machine to minimize makespan and maximum flow time. Journal of Industrial & Management Optimization, 2018, 13 (5) : 1-22. doi: 10.3934/jimo.2018017

[10]

Lili Ding, Xinmin Liu, Yinfeng Xu. Competitive risk management for online Bahncard problem. Journal of Industrial & Management Optimization, 2010, 6 (1) : 1-14. doi: 10.3934/jimo.2010.6.1

[11]

Kyosuke Hashimoto, Hiroyuki Masuyama, Shoji Kasahara, Yutaka Takahashi. Performance analysis of backup-task scheduling with deadline time in cloud computing. Journal of Industrial & Management Optimization, 2015, 11 (3) : 867-886. doi: 10.3934/jimo.2015.11.867

[12]

Yangyang Xu, Ruru Hao, Wotao Yin, Zhixun Su. Parallel matrix factorization for low-rank tensor completion. Inverse Problems & Imaging, 2015, 9 (2) : 601-624. doi: 10.3934/ipi.2015.9.601

[13]

Leiyang Wang, Zhaohui Liu. Heuristics for parallel machine scheduling with batch delivery consideration. Journal of Industrial & Management Optimization, 2014, 10 (1) : 259-273. doi: 10.3934/jimo.2014.10.259

[14]

Xianzhao Zhang, Dachuan Xu, Donglei Du, Cuixia Miao. Approximate algorithms for unrelated machine scheduling to minimize makespan. Journal of Industrial & Management Optimization, 2016, 12 (2) : 771-779. doi: 10.3934/jimo.2016.12.771

[15]

Roberto C. Alamino, Nestor Caticha. Bayesian online algorithms for learning in discrete hidden Markov models. Discrete & Continuous Dynamical Systems - B, 2008, 9 (1) : 1-10. doi: 10.3934/dcdsb.2008.9.1

[16]

Muminu O. Adamu, Aderemi O. Adewumi. Minimizing the weighted number of tardy jobs on multiple machines: A review. Journal of Industrial & Management Optimization, 2016, 12 (4) : 1465-1493. doi: 10.3934/jimo.2016.12.1465

[17]

Donglei Du, Xiaoyue Jiang, Guochuan Zhang. Optimal preemptive online scheduling to minimize lp norm on two processors. Journal of Industrial & Management Optimization, 2005, 1 (3) : 345-351. doi: 10.3934/jimo.2005.1.345

[18]

Annalisa Pascarella, Alberto Sorrentino, Cristina Campi, Michele Piana. Particle filtering, beamforming and multiple signal classification for the analysis of magnetoencephalography time series: a comparison of algorithms. Inverse Problems & Imaging, 2010, 4 (1) : 169-190. doi: 10.3934/ipi.2010.4.169

[19]

Zhao-Hong Jia, Ting-Ting Wen, Joseph Y.-T. Leung, Kai Li. Effective heuristics for makespan minimization in parallel batch machines with non-identical capacities and job release times. Journal of Industrial & Management Optimization, 2017, 13 (2) : 977-993. doi: 10.3934/jimo.2016057

[20]

Yunhai Xiao, Junfeng Yang, Xiaoming Yuan. Alternating algorithms for total variation image reconstruction from random projections. Inverse Problems & Imaging, 2012, 6 (3) : 547-563. doi: 10.3934/ipi.2012.6.547

2017 Impact Factor: 0.994

Article outline

[Back to Top]