Research on the single-machine online schedule in which the jobs' release times and processing times are agreeable

Expand
  • 1. School of Mathematical Sciences, Luoyang Normal University, Luoyang 471934, Henan, China
    2. College of Science, Henan University of Engineering, Zhengzhou 451191, Henan, China

Received date: 2021-02-26

  Online published: 2022-05-27

Abstract

There are $n$ jobs $J_1, J_2, \cdots, J_n$ to be scheduled on the single machine. Each job $J_{j}$ has a nonnegative arriving time $r_{j}$, a positive processing time $p_{j}$, and a nonnegative weight $w_{j}$. We consider one restricted model: the jobs have agreeable release times and processing times (i.e., if $r_{i}\geq r_{j}$, then $p_{i}\geq p_{j}$). Under this restricted model, we study the single-machine online schedule to minimize the maximum weighted completion time of jobs or the total weighted completion times of jobs. We present two best possible online algorithms with the competitive ratio of both $\frac{\sqrt{5}+1}{2}$.

Cite this article

Wenjie LI, Yujing LI, Hailing LIU . Research on the single-machine online schedule in which the jobs' release times and processing times are agreeable[J]. Operations Research Transactions, 2022 , 26(2) : 55 -63 . DOI: 10.15960/j.cnki.issn.1007-6093.2022.02.005

References

1 唐国春, 张峰, 罗守成, 刘丽丽. 现代排序论[M]. 上海: 上海科学普及出版社, 2003.
2 万国华. 排序与调度的理论、模型和算法[M]. 北京: 清华大学出版社, 2019.
3 Blazewicz J , Ecker K , Pesch E , et al. Handbook on Scheduling-From Theory to Practice[M]. Berlin: Springer, 2019.
4 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.
5 Chen R B , Yuan J J . Single-machine scheduling of proportional-linearly deteriorating jobs with positional due indices[J]. 4OR-A Quarterly Journal of Operations Research, 2020, 18, 177- 196.
6 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, 860- 875.
7 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.
8 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(1-10).
9 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: 1850048(1-10).
10 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, 455- 465.
11 Anderson E J , Potts C N . Online scheduling of a single machine to minimize total weighted completion time[J]. Mathematics of Operations Research, 2004, 29, 686- 697.
12 Ma R , Yuan J J . Online scheduling to minimize the total weighted completion time plus the rejection cost[J]. Journal of Combinatorial Optimization, 2017, 34, 483- 503.
13 Megow N , Schulz A S . On-line scheduling to minimize average completion time revisited[J]. Operations Research Letters, 2004, 32, 485- 490.
14 Correa J R , Wagner M R . LP-based online scheduling: from single to parallel machines[J]. Mathematical Programming, 2009, 119, 109- 136.
15 Tao J P . A better online algorithm for the parallel machine scheduling to minimize the weighted completion time[J]. Computer and Operations Research, 2014, 43, 215- 224.
16 Tao J P , Huang R H , Liu T D . A 2.28-competitive algorithm for online scheduling on identical machines[J]. Journal of Industrial and Management Optimization, 2015, 11, 185- 198.
17 Ma R , Tao J P . An improved 2.11-competitive algorithm for online scheduling on parallel machines to minimize total weighted completion time[J]. Journal of Industrial and Management Optimization, 2018, 14, 497- 510.
Outlines

/