中文

Operations Research Transactions >

2024 , Vol. 28 >Issue 4: 18 - 28

DOI: https://doi.org/10.15960/j.cnki.issn.1007-6093.2024.04.002

Research on the NDP-constraint online scheduling of jobs have agreeable processing times and delivery times

Expand
  • 1. School of Mathematical Sciences, Luoyang Normal University, Luoyang 471934, Henan, China

Received date: 2022-03-30

  Online published: 2024-12-20

Copyright

, 2024, All rights reserved, without authorization
Fold

Abstract

This paper studies the single-machine online schedule under the NDP-constraint to minimize the maximum delivery completion time. Here "NDP-constraint" means that the idle machine must schedule the available jobs at any time, i.e., the available jobs cannot be delayed for processing. In this paper, we study the restricted version in which the jobs have agreeable processing times and delivery times (if $p_{i}\geq p_{j}$, then $p_{i}\geq p_{j}$). we first present a lower bound of 4/3 and then design an online algorithm with the competitive ratio of 1.382.

Key words： online scheduling; online algorithm; NDP-constraint; agreeable; delivery completion time

Cite this article

Wenjie LI, Zhihui DU, Menglong SU . Research on the NDP-constraint online scheduling of jobs have agreeable processing times and delivery times[J]. Operations Research Transactions, 2024 , 28(4) : 18 -28 . DOI: 10.15960/j.cnki.issn.1007-6093.2024.04.002

References

1 唐国春, 张峰, 罗守成, 等. 现代排序论[M]. 上海: 上海科学普及出版社, 2003.
2 万国华. 排序与调度的理论、模型和算法[M]. 北京: 清华大学出版社, 2019.
3 Blazewicz J , Ecker K , Pesch E , et al. Handbook on Scheduling-From Theory to Practice[M]. Switzerland: Springer Nature, 2019.
4 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.
5 Baker K R . Introduction to Sequencing and Scheduling[M]. New York: John Wiley & Sons, 1974.
6 Hoogeveen H , Potts C N , Woeginger G J . Online scheduling on a single machine: Maximizing the number of early jobs[J]. Operations Research Letters, 2000, 27, 193- 196.
7 Keskinocak P. Online algorithms with lookahead: A survey [Z]. ISYE working paper, 1999.
8 Ma R , Guo S N , Miao C X . A semi-online algorithm and its competitive analysis for parallel-machine scheduling problem with rejection[J]. Applied Mathematics and Computation, 2021, 392, 125670.
9 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.
10 Graham R L , Lawer E L , Lenstra J K . Optimization and approximation in deterministic sequencing and scheduling[J]. Annals of Discrete Mathematics, 1979, 5, 287- 326.
11 胡觉亮, 张玮虹, 蒋义伟. 生产和运输时间具有一致性的单机在线最优算法[J]. 浙江理工大学学报, 2010, 27, 830- 834.
12 Liu H L , Lu X W , Li W J . A best possible online algorithm for parallel batch scheduling with delivery times and limited restart[J]. Optimization Letters, 2021, 15, 1155- 1173.
13 Hoogeveen H , Vestjens A P A . A best possible deterministic on-line algorithm for minimizing maximum delivery time on a single machine[J]. SIAM Journal on Discrete Mathematics, 2000, 13, 56- 63.
14 Tian J , Fu R Y , Yuan J J . A best on-line algorithm for single machine scheduling with small delivery times[J]. Theoretical Computer Science, 2008, 393, 287- 293.
15 Liu M , Chu C B , Xu Y F , et al. An optimal online algorithm for single machine scheduling with bounded delivery times[J]. European Journal of Operational Research, 2010, 201, 693- 700.
Options
Outlines

/

〈 〉