[go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

Two-agent single-machine scheduling with release dates to minimize the makespan

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

Abstract

We consider two-agent scheduling on a single-machine with release dates. There are two agents, namely, A and B. Each agent has his own job set. Each job has a release date and a processing time. All jobs need to be scheduled on a single machine. The objective function of each agent is the makespan with respect to his jobs, i.e., the maximum completion time. We consider two problems, namely the problem to minimize the makespans of agent A with the makespan of agent B not greater than a positive number Q given in advance, and the problem to minimize the weighted sum of both agents’ makespans. For the first problem, we drive an approximation algorithm with a worst-case ratio of \(\frac{3}{2}\). Furthermore, we show that this problem admits a fully polynomial-time approximation scheme(FPTAS). For the second problem, we propose an improved approximation algorithm with a worst-case ratio of \(1 +\frac{\theta }{(1+\theta )^2}\), where \(\theta >0\) is the weight of agent B.

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

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5

Similar content being viewed by others

References

  1. Agnetis, A., Billaut, J.C., Gawiejnowicz, S., Pacciarelli, D.: Multiagent scheduling : models and algorithms. Springer, Berlin (2014)

    Book  MATH  Google Scholar 

  2. Agnetis, A., Mirchandani, P.B., Pacifici, P.A.: Scheduling problems with two competing agents. Operat. Res. 52(2), 229–242 (2004)

    Article  MathSciNet  MATH  Google Scholar 

  3. Arbib, C., Smriglio, S., Servilio, M.: A competitive scheduling problem and its relevance to umts channel assignment. Networks 44(2), 132–141 (2004)

    Article  MathSciNet  MATH  Google Scholar 

  4. Baker, K.R., Smith, J.C.: A multiple-criterion model for machine scheduling. J. Sched. 6, 7–16 (2003)

    Article  MathSciNet  MATH  Google Scholar 

  5. Blazewicz, J., Ecker, K., Schmidt, G., Weglarz, J.: Scheduling in Computer and Manufacturing Systems. Springer, Berlin (1993)

    Book  MATH  Google Scholar 

  6. Cheng, T., Ng, C., Yuan, J.: Multi-agent scheduling on a single machine to minimize total weighted number of tardy jobs. Theor Comput. Sci. 362(1), 273–281 (2006)

    Article  MathSciNet  MATH  Google Scholar 

  7. Cheng, T., Ng, C., Yuan, J.: Multi-agent scheduling on a single machine with max-form criteria. Eur J. Operat. Res. 188(2), 603–609 (2008)

    Article  MathSciNet  MATH  Google Scholar 

  8. Ding, G., Sun, S.: Single-machine scheduling problems with two agents competing for makespan. In: Li K., Fei M., Jia L., Irwin G.W. (eds) Life System Modeling and Intelligent Computing. ICSEE 2010, LSMS 2010. Lecture Notes in Computer Science, vol 6328. Springer, Berlin. (2010)

  9. Elvikis, D., T’Kindt, V.: Two-agent scheduling on uniform parallel machines with min-max criteria. Annal. Operat. Res. 213, 79–94 (2014)

    Article  MathSciNet  MATH  Google Scholar 

  10. Fan, B., Cheng, T.: Two-agent scheduling in a flowshop. Eur. J. Operat. Res. 252(2), 376–384 (2016)

    Article  MathSciNet  MATH  Google Scholar 

  11. Feng, Q., Shang, W.P., Jiao, C.W., Li, W.J.: Two-agent scheduling on a bounded parallel-batching machine with makespan and maximum lateness objectives. J. Operat. Res. Soc. China 8(1), 189–196 (2020)

    Article  MathSciNet  MATH  Google Scholar 

  12. Gao, Y., Yuan, J., Ng, C.T., Cheng, T.: A note on competing-agent pareto-scheduling. Optim. Lett. 15, 249–262 (2021)

    Article  MathSciNet  MATH  Google Scholar 

  13. Gerstl, E., Mosheiov, G.: Scheduling problems with two competing agents to minimized weighted earliness-tardiness. Comput. Operat. Res. 40(1), 109–116 (2013)

    Article  MathSciNet  MATH  Google Scholar 

  14. Gerstl, E., Mosheiov, G.: Single machine just-in-time scheduling problems with two competing agents. Naval Res. Logist. 61(1), 1–16 (2014)

    Article  MathSciNet  MATH  Google Scholar 

  15. Ibarra, O., Kim, C.: Fast approximation algorithms for the knapsack and sum of subsets problems. J. ACM 22, 463–468 (1975)

    Article  MathSciNet  MATH  Google Scholar 

  16. Kacem, I.: Approximation algorithms for the makespan minimization with positive tails on a single machine with a fixed non-availability interval. J. Combinat. Opt. 17, 117–133 (2009)

    Article  MathSciNet  MATH  Google Scholar 

  17. Kovalyov, M., Oulamara, A., Soukhal, A.: Two-agent scheduling with agent specific batches on an unbounded serial batching machine. J. Schedul. 18, 423–434 (2015)

    Article  MathSciNet  MATH  Google Scholar 

  18. Lawler, E.L.: Optimal sequencing of a single machine subject to precedence constraints. Manage. Sci. 19, 544–546 (1973)

    Article  MATH  Google Scholar 

  19. Lee, K., Choi, B.C., Leung, J.Y.T., Pinedo, M.: Approximation algorithms for multi-agent scheduling to minimize total weighted completion time. Inform. Process. Lett. 109(16), 913–917 (2009)

    Article  MathSciNet  MATH  Google Scholar 

  20. Leung, J.Y.T., Pinedo, M., Wan, G.: Competitive two-agent scheduling and its applications. Operat. Res. 58(2), 458–469 (2010)

    Article  MathSciNet  MATH  Google Scholar 

  21. Liu, P., Gu, M., Li, G.: Two-agent scheduling on a single machine with release dates. Comput. Operat. Res. 111, 35–42 (2019)

    Article  MathSciNet  MATH  Google Scholar 

  22. Luo, W., Chen, L., Zhang, G.: Approximation schemes for two-machine flow shop scheduling with two agents. J. Combinat. Optim. 24(3), 229–239 (2012)

    Article  MathSciNet  MATH  Google Scholar 

  23. Mor, B., Mosheiov, G.: A two-agent single machine scheduling problem with due-window assignment and a common flow-allowance. J. Combinat. Optim. 33, 1454–1468 (2017)

    Article  MathSciNet  MATH  Google Scholar 

  24. Nong, Q., Cheng, T., Ng, C.: Two-agent scheduling to minimize the total cost. Eur. J. Operat. Res. 215(1), 39–44 (2011)

    Article  MathSciNet  MATH  Google Scholar 

  25. Perez-Gonzalez, P., Framinan, J.M.: A common framework and taxonomy for multicriteria scheduling problems with interfering and competing jobs: Multi-agent scheduling problems. Eur. J. Operat. Res. 235, 1–16 (2014)

    Article  MathSciNet  MATH  Google Scholar 

  26. T’kindt, V., Billaut, J.C.: Multicriteria Scheduling: theory, models and algorithms. Springer, Berlin (2006)

  27. Wan, G., Vakati, S.R., Leung, J.Y.T., Pinedo, M.: Scheduling two agents with controllable processing times. Eur. J. Operat. Res. 205, 528–539 (2010)

    Article  MathSciNet  MATH  Google Scholar 

  28. Woeginger, G.: When does a dynamic programming formulation guarantee the existence of a fully polynomial time approximation scheme (fptas)? INFORMS J. Comput. 12, 57–74 (2000)

    Article  MathSciNet  MATH  Google Scholar 

  29. Woeginger, G.: A comment on scheduling two machines with capacity constraints. Discrete Optim. 2, 269–272 (2005)

    Article  MathSciNet  MATH  Google Scholar 

  30. Zhang, X., Wang, Y.: Two-agent scheduling problems on a single-machine to minimize the total weighted late work. J. Combinat. Optim. 33(3), 945–955 (2017)

    Article  MathSciNet  MATH  Google Scholar 

Download references

Acknowledgements

This work is supported by the National Nature Science Foundation of China(11871213). The authors would like to thank anonymous referees whose comments helped a lot to improve this paper.

Author information

Authors and Affiliations

  1. School of Science, East China University of Science and Technology, Shanghai, 200237, People’s Republic of China

    Jin Yu, Peihai Liu & Xiwen Lu

Authors
  1. Jin Yu
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Peihai Liu
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Xiwen Lu
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Peihai Liu.

Additional information

Publisher's Note

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

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

Yu, J., Liu, P. & Lu, X. Two-agent single-machine scheduling with release dates to minimize the makespan. Optim Lett 17, 1915–1937 (2023). https://doi.org/10.1007/s11590-022-01967-6

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s11590-022-01967-6

Keywords

Search

Navigation