Single-machine online scheduling to minimize maximum weighted completion time with limited weights

Expand
  • 1. School of Management Engineering, Qingdao University of Technology, Qingdao 266525, Shandong, China
    2. Institute of Operations Research, School of Management, Qufu Normal University, Rizhao 276826, Shandong, China

Received date: 2021-06-23

  Online published: 2024-06-07

Copyright

, 2024, All rights reserved, without authorization

Abstract

The setting we consider is nonpreemptive single machine online scheduling, with the objective to minimize the maximum weighted completion time of jobs. The weight of the job is not only limited strictly within the processing time compass of this job, but also agreeable with processing time of this job, i.e., $ ap_j\leq w_j\leq bp_j(a\geq\frac{\sqrt{5}-1}{2}b, b\geq a)$ and if $ w_i>w_j$, then $ p_i\geq p_j$. Especially, if $ w_i=w_j$, then $ p_i=p_j$. Significantly, there are irrelevant jobs arriving online over time and the knowledge of each job $ J_j$, such as its processing length $ p_j$ and weight $ w_j$, is not revealed for the scheduler until it is released at time $ r_j$. By means of adversary method, it is explicitly derived that the lower bound of the considered problem is $ 1+\frac{b}{b+a}$. Then we provide a best possible online algorithm with the competitive ratio of $ 1+\frac{b}{b+a}$. Moreover, the competitive ratio of this algorithm is $ \frac{\sqrt5+1}{2}$, when $ a=\frac{\sqrt{5}-1}{2}b$.

Cite this article

Juannian XU, Ran MA, Wenwen HAN, Yuzhong ZHANG . Single-machine online scheduling to minimize maximum weighted completion time with limited weights[J]. Operations Research Transactions, 2024 , 28(2) : 71 -80 . DOI: 10.15960/j.cnki.issn.1007-6093.2024.02.005

References

1 Vestjens A P A. On-line machine scheduling[D]. Netherlands: Eindhove University of Technology, 1997.
2 Pruhs K, Sgall J, Tong E. Online scheduling[M]//Handbook of Scheduling: Algorithms, Model, and Pertormance Analysis, Boca Raton: Chapman and Hall/CRC Press, 2004: 1-41.
3 Tan Z Y, Zhang A. Online and semi-online scheduling[M]//Handbook of Combinatorial Optimization, New York: Springer, 2013.
4 Tian J , Fu R Y , Yuan J J . Online over time scheduling on parallel-batch machines: A survey[J]. Journal of the Operations Research Society of China, 2014, 2, 445- 454.
5 Tang L X , Li F , Zhen Z L . Integrated scheduling of production and two-stage delivery of make-to-order products: Offline and online algorithms[J]. Informs Journal on Computing, 2019, 31 (3): 493- 514.
6 冯琪, 原晋江. 一个具有两类工件的多目标排序的NP-困难性[J]. 运筹学学报, 2007, 11 (4): 121- 126.
7 Oron D , Shabtay D , Steiner G . Single machine scheduling with two competing agents and equal job processing times[J]. European Journal of Operational Research, 2015, 244, 86- 99.
8 Chen R B , Yuan J J . Single-machine scheduling of proportional-linearly deteriorating jobs with positional due indices[J]. 4OR, 2020, 18 (2): 177- 196.
9 Yuan J J , Ng C T , Cheng T C E . Scheduling with release dates and preemption to minimize multiple max-form objective functions[J]. European Journal of Operational Research, 2020, 280 (3): 860- 875.
10 Zhao Q L , Yuan J J . Bicriteria scheduling of equal length jobs on uniform parallel machines[J]. Journal of Combinatorial Optimization, 2020, 39, 637- 661.
11 Li W J . A best possible online algorithm for the parallel-machine scheduling to minimize the maximum weighted completion time[J]. Asia-Pacific Journal of Operational Research, 2015, 32, 1550030.
12 Chai X , Lu L F , Li W H , et al. Best-possible online algorithms for single machine scheduling to minimize the maximum weighted completion time[J]. Asia-Pacific Journal of Operational Research, 2018, 35 (6): 1850048.
13 Li W H , Chai X . Online scheduling on bounded batch machines to minimize the maximum weighted completion time[J]. Journal of the Operations Research Society of China, 2018, 6 (3): 455- 465.
14 Li W J , Yuan J J . Single-machine online scheduling of jobs with non-delayed processing constraint[J]. Journal of Combinatorial Optimization, 2021, 41, 830- 843.
Outlines

/