Skip to main content

Advertisement

Springer Nature Link
Log in

Semi-online Machine Covering Problem on Three Hierarchical Machines with Bounded Processing Times

  • Published:
Journal of the Operations Research Society of China Aims and scope Submit manuscript

Abstract

In this paper, we consider the problem of semi-online machine covering on three machines with two hierarchies, whose objective is to maximize the minimum machine load. Since there is no online algorithm with bounded competitive ratio for the online machine covering problem, we consider the semi-online case where the processing times of all jobs lie in \([1,\alpha ]\). When there are one machine of hierarchy 1 and two machines of hierarchy 2, we design an optimal online algorithm with a competitive ratio of \(1+\alpha \). When there are two machines of hierarchy 1 and one machine of hierarchy 2, we give an optimal online algorithm with a competitive ratio of \(1+2\alpha \).

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
$34.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 excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. Bar-Noy, A., Freund, A., Naor, J.: On-line load Balancing in a hierarchical server topology. SIAM J. Comput. 31(2), 527–549 (2001)

    Article  MathSciNet  Google Scholar 

  2. Zhang, A., Jiang, Y., Tan, Z.: Online parallel machines scheduling with two hierarchies. Theoret. Comput. Sci. 410, 3597–3605 (2009)

    Article  MathSciNet  Google Scholar 

  3. Park, J., Chang, S.Y., Lee, K.: Online and semi-online scheduling of two machines under a grade of service provision. Oper. Res. Lett. 34(6), 692–696 (2006)

    Article  MathSciNet  Google Scholar 

  4. Chen, Y., Chen, T., Liu, L., Jiang, Y., Tan, Z., Zhang, A.: Online scheduling with unit processing times and processing set restrictions. J. Oper. Res. Soc. China 7, 475–484 (2019)

    Article  MathSciNet  Google Scholar 

  5. Jia, Xu., Liu, Z.: An optimal online algorithm for scheduling on two parallel machines with GoS eligibility constraints. J. Oper. Res. Soc. China 4, 371–377 (2016)

    Article  MathSciNet  Google Scholar 

  6. Cai, S., Liu, K.: Online scheduling on two parallel identical machines under a grade of service provision. J. Oper. Res. Soc. China (2020). https://doi.org/10.1007/s40305-020-00325-6

    Article  Google Scholar 

  7. Woeginger, G.J.: A polynomial time approximation scheme for maximizing the minimum machine completion time. Oper. Res. Lett. 20, 149–154 (1997)

    Article  MathSciNet  Google Scholar 

  8. He, Y.: The optimal on-line parallel machine scheduling. Comput. Math. Appl. 39, 117–121 (2000)

    Article  MathSciNet  Google Scholar 

  9. Azar, Y., Epstein, L.: On-line machine covering. J. Sched. 1, 67–77 (1998)

    Article  MathSciNet  Google Scholar 

  10. Tan, Z., Wu, Y.: Optimal semi-online algorithms for machine covering. Theoret. Comput. Sci. 372(1), 69–80 (2007)

    Article  MathSciNet  Google Scholar 

  11. He, Y.: Semi-on-line scheduling problems for maximizing the minimum machine completion time. Acta Math. Appl. Sin. 17, 107–113 (2001)

    Article  MathSciNet  Google Scholar 

  12. Chassid, O., Epstein, L.: The hierarchical model for load balancing on two machines. J. Comb. Optim. 15(4), 305–314 (2008)

    Article  MathSciNet  Google Scholar 

  13. Wu, Y., Cheng, T.C.E., Ji, M.: Optimal algorithms for semi-online machine covering on two hierarchical machines. Theoret. Comput. Sci. 531(6), 37–46 (2014)

    Article  MathSciNet  Google Scholar 

  14. Luo, T., Xu, Y.: Semi-online hierarchical load balancing problem with bounded processing times. Theoret. Comput. Sci. 607, 75–82 (2015)

    Article  MathSciNet  Google Scholar 

  15. Wu, G., Li, W.: Semi-online Machine Covering on Two Hierarchical Machines with Discrete Processing Times. In: Li, L., Lu, P., He, K. (eds.) Theoretical computer science. NCTCS 2018. Communications in computer and information science, vol. 882, pp. 1–7. Springer, Singapore (2018)

  16. Xiao, M., Wu, G., Li, W.: Semi-online Machine Covering on Two Hierarchical Machines with Known Total Size of Low-Hierarchy Jobs. In: Sun, X., He, K., Chen, X. (eds.) Theoretical computer science. NCTCS 2019. Communications in computer and information science, vol. 1069, pp. 95–108. Springer, Singapore (2019)

Download references

Author information

Authors and Affiliations

  1. School of Mathematics and Statistics, Yunnan University, Kunming, 650504, Yunnan, China

    Man Xiao, Yu-Fei Du & Wei-Dong Li

  2. Dianchi College of Yunnan University, Kunming, 650228, Yunnan, China

    Yu-Fei Du & Jin-Hua Yang

Authors
  1. Man Xiao
    View author publications

    You can also search for this author inPubMed Google Scholar

  2. Yu-Fei Du
    View author publications

    You can also search for this author inPubMed Google Scholar

  3. Wei-Dong Li
    View author publications

    You can also search for this author inPubMed Google Scholar

  4. Jin-Hua Yang
    View author publications

    You can also search for this author inPubMed Google Scholar

Contributions

M. Xiao proposed the methods and wrote the manuscript; Y.-F. Du proposed some ideas and proved some theorems; W.-D. Li proposed the problem, reviewed and modified the manuscript; J.-H. Yang provided suggestions for the methods and reviewed the manuscript. All authors have read and agreed to the published version of the manuscript.

Corresponding author

Correspondence to Wei-Dong Li.

Ethics declarations

Conflict of interest

The authors declare that there is no conflict of interests regarding the publication of this paper.

Additional information

This work was supported by the National Natural Science Foundation of China (No. 12071417).

Rights and permissions

Springer Nature or its licensor (e.g. a society or other partner) holds exclusive rights to this article under a publishing agreement with the author(s) or other rightsholder(s); author self-archiving of the accepted manuscript version of this article is solely governed by the terms of such publishing agreement and applicable law.

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Xiao, M., Du, YF., Li, WD. et al. Semi-online Machine Covering Problem on Three Hierarchical Machines with Bounded Processing Times. J. Oper. Res. Soc. China 12, 1126–1138 (2024). https://doi.org/10.1007/s40305-023-00477-1

Download citation

  • Received:

  • Revised:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s40305-023-00477-1

Keywords

Mathematics Subject Classification

Profiles

  1. Wei-Dong Li View author profile