[go: up one dir, main page]
More Web Proxy on the site http://driver.im/ Skip to main content
Springer Nature Link
Log in

Online NDP-constraint scheduling of jobs with delivery times or weights

  • Original Paper
  • Published:
Optimization Letters Aims and scope Submit manuscript

Abstract

This paper studies three online scheduling problems on the single-machine, denoted by (P1), (P2) and (P3), to minimize the maximum weighted completion time or the maximum delivery completion time with or without the NDP constraint. Here, “NDP” means that the available jobs cannot be delayed for processing when the machine is idle. Problems (P1) and (P2) aim to minimize the maximum weighted completion time, where (P1) has not the NDP constraint and (P2) has the NDP constraint. Problem (P3) aims to minimize the maximum delivery completion time under the NDP constraint. For problems (P1) and (P2), we study the restricted version in which the jobs have agreeable processing times and weights (i.e., if \(p_{i}> p_{j}\), then \(w_{i}\ge w_{j}\)). For problem (P3), we study the restricted version in which the jobs have small delivery times (i.e., \(p_{j}\ge q_{j}\)). We show that problem (P1) admits a best possible online algorithm with a competitive ratio of 1.618, problem (P2) has a lower bound 3/2 and admits a \(\sqrt{3}\)-competitive online algorithm, and problem (P3) admits a best possible online algorithm with a competitive ratio of 4/3.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
£29.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (United Kingdom)

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. Akker, M.V.D., Hoogeveen, H., Vakhania, N.: Restarts can help in the online minimization of the maximum delivery time on a single machine. J. Sched. 3, 333–341 (2003)

    Article  MATH  Google Scholar 

  2. Baker, K.R.: Introduction to Sequencing and Scheduling. John Wiley & Sons, New York (1974)

    Google Scholar 

  3. Chai, X., Lu, L.F., Li, W.H., Zhang, L.Q.: Best-possible online algorithms for single machine scheduling to minimize the maximum weighted completion time. Asia Pac. J. Oper. Res. 35, 1850048(1-10) (2018)

  4. Chen, R.B., Yuan, J.J.: Single-machine scheduling of proportional-linearly deteriorating jobs with positional due indices. 4OR Q. J. Oper. Res. 18, 177–196 (2020)

    Article  MathSciNet  MATH  Google Scholar 

  5. Fang, Y., Liu, P.H., Lu, X.W.: Optimal on-line algorithms for one batch machine with grouped processing times. J. Comb. Optim. 22, 509–516 (2011)

    Article  MathSciNet  MATH  Google Scholar 

  6. Hoogeveen, H., Vestjens, A.P.A.: A best possible deterministic on-line algorithm for minimizing maximum delivery time on a single machine. SIAM J. Discret. Math. 13, 56–63 (2000)

    Article  MathSciNet  MATH  Google Scholar 

  7. Hoogeveen, H., Potts, C.N., Woeginger, G.J.: Online scheduling on a single machine: maximizing the number of early jobs. Oper. Res. Lett. 27, 193–196 (2000)

    Article  MathSciNet  MATH  Google Scholar 

  8. Keskinocak, P.: Online algorithms with lookahead: a survey, ISYE working paper (1999)

  9. Li, W.J.: A best possible online algorithm for the parallel-machine scheduling to minimize the maximum weighted completion time. Asia Pac. J. Oper. Res. 32, 1550030(1-10) (2015)

  10. Li, W.H., Chai, X.: Online scheduling on bounded batch machines to minimize the maximum weighted completion time. Asia Pac. J. Oper. Res. 6, 455–465 (2018)

    Article  MathSciNet  MATH  Google Scholar 

  11. Li, W.J., Yuan, J.J.: Single-machine online scheduling of jobs with non-delayed processing constraint. J. Comb. Optim. 41, 830–843 (2021)

    Article  MathSciNet  MATH  Google Scholar 

  12. Liu, M., Chu, C.B., Xu, Y.F., Zheng, F.F.: An optimal online algorithm for single machine scheduling with bounded delivery times. Eur. J. Oper. Res. 201, 693–700 (2010)

    Article  MathSciNet  MATH  Google Scholar 

  13. Liu, H.L., Lu, X.W., Li, W.J.: A best possible online algorithm for parallel batch scheduling with delivery times and limited restart. Optim. Lett. 15, 1155–1173 (2021)

    Article  MathSciNet  Google Scholar 

  14. Tan, Z.Y., Yu, S.H.: Online scheduling with reassignment. Oper. Res. Lett. 36, 250–254 (2008)

    Article  MathSciNet  MATH  Google Scholar 

  15. Tian, J., Fu, R.Y., Yuan, J.J.: On-line scheduling with delivery time on a single batch machine. Theoret. Comput. Sci. 374, 49–57 (2007)

    Article  MathSciNet  MATH  Google Scholar 

  16. Tian, J., Fu, R.Y., Yuan, J.J.: A best on-line algorithm for single machine scheduling with small delivery times. Theoret. Comput. Sci. 393, 287–293 (2008)

    Article  MathSciNet  MATH  Google Scholar 

  17. Tian, J., Fu, R.Y., Yuan, J.J.: An on-line algorithm for the single machine unbounded parallel-batching scheduling with large delivery times. Inf. Process. Lett. 111, 1048–1053 (2011)

    Article  MathSciNet  MATH  Google Scholar 

  18. Tian, J., Cheng, T.C.E., Ng, C.T., Yuan, J.J.: An improved on-line algorithm for single parallel- batch machine scheduling with delivery times. Discret. Appl. Math. 160, 1191–1210 (2012)

    Article  MathSciNet  MATH  Google Scholar 

  19. Yuan, J.J., Li, S.S., Tian, J., Fu, R.Y.: A best possible on-line algorithm for the single machine parallel-batch scheduling with restricted delivery times. J. Comb. Optim. 17, 206–213 (2009)

    Article  MathSciNet  MATH  Google Scholar 

  20. Yuan, J.J., Ng, C.T., Cheng, T.C.E.: Scheduling with release dates and preemption to minimize multiple max-form objective functions. Eur. J. Oper. Res. 280, 860–875 (2020)

    Article  MathSciNet  MATH  Google Scholar 

  21. Zhao, Q.L., Yuan, J.J.: Bicriteria scheduling of equal length jobs on uniform parallel machines. J. Comb. Optim. 39, 637–661 (2020)

    Article  MathSciNet  MATH  Google Scholar 

Download references

Acknowledgements

The authors would like to thank the referees for their helpful comments and Prof. Jinjiang Yuan for his help on the representation of the paper. This work was supported by the Natural Science Foundation of Henan (No. 222300420503), the Basic Research Foundation of Henan Educational Committee (Nos. 22A110015, 20ZX004, 22ZX009) and the Young Backbone Teachers of Henan Colleges (Nos. 2019GGJS202, 2018XJGGJS-10).

Author information

Authors and Affiliations

  1. School of Mathematical Sciences, Luoyang Normal University, Luoyang, Henan, 471934, People’s Republic of China

    Wenjie Li

  2. College of Science, Henan University of Engineering, Zhengzhou, Henan, 451191, People’s Republic of China

    Hailing Liu

Authors
  1. Wenjie Li
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Hailing Liu
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Wenjie Li.

Additional information

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Li, W., Liu, H. Online NDP-constraint scheduling of jobs with delivery times or weights. Optim Lett 17, 591–612 (2023). https://doi.org/10.1007/s11590-022-01889-3

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s11590-022-01889-3

Keywords

Search

Navigation