Nothing Special   »   [go: up one dir, main page]

Skip to main content
Log in

Approximation schemes for two-machine flow shop scheduling with two agents

  • Published:
Journal of Combinatorial Optimization Aims and scope Submit manuscript

Abstract

In this paper we consider two-machine flow shop scheduling with two agents. Two models are investigated. One is the weighted-sum optimization model and the other is the constrained optimization model. For the former, we show that it is weakly NP-hard and propose a fully polynomial time approximation scheme. For the latter, we also show the problem is weakly NP-hard. With violating the constraint a factor of ε a fully polynomial time approximation scheme is provided.

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

Access this article

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.

Similar content being viewed by others

References

  • Agnetis A, Mirchandani PB, Pacciarelli D, Pacifici A (2004) Scheduling problems with two competing agents. Oper Res 52:229–242

    Article  MathSciNet  MATH  Google Scholar 

  • Agnetis A, Pacciarelli D, Pacifici A (2007) Multi-agent single machine scheduling. Ann Oper Res 150:3–15

    Article  MathSciNet  MATH  Google Scholar 

  • Agnetis A, Pascale GD, Pacciarelli D (2009) A Lagrangian approach to single-machine scheduling problems with two competing agents. J Sched 12:401–415

    Article  MathSciNet  MATH  Google Scholar 

  • Arbib C, Smriglio S, Servilio M (2004) A competitive scheduling problem and its relevances to UMTS channel assignment. Networks 44:132–141

    Article  MathSciNet  MATH  Google Scholar 

  • Baker KR, Smith JC (2003) A multiple-criterion model for machine scheduling. J Sched 6:7–16

    Article  MathSciNet  MATH  Google Scholar 

  • Cheng TCE, Ng CT, Yuan JJ (2006) Multi-agent scheduling on a single machine to minimize total weighted number of tardy jobs. Theor Comput Sci 362:273–281

    Article  MathSciNet  MATH  Google Scholar 

  • Cheng TCE, Ng CT, Yuan JJ (2008) Multi-agent scheduling on a single machine with max-form criteria. Eur J Oper Res 188:603–609

    Article  MathSciNet  MATH  Google Scholar 

  • Graham RL, Lawler EL, Lenstra JK, Rinnooy Kan AHG (1979) Optimization and approximation in deterministic sequencing and scheduling: a survey. Ann Discrete Math 5:287–326

    Article  MathSciNet  MATH  Google Scholar 

  • Johnson SM (1954) Optimal two-and three-stage production schedules with setup times included. Nav Res Logist 1:61–68

    Article  Google Scholar 

  • Lee K, Choi B-C, Leung JY-T, Pinedo ML (2009) Approximation algorithms for multi-agent scheduling to minimize total weighted completion time. Inf Process Lett 109:913–917

    Article  MathSciNet  MATH  Google Scholar 

  • Leung JY-T, Pinedo ML, Wan G (2010) Competitive two agent scheduling and its applications. Oper Res 58:458–469

    Article  MathSciNet  MATH  Google Scholar 

  • Kubzin MA, Strusevich VA (2006) Planning machine maintenance in two-machine shop scheduling. Oper Res 54:789–800

    Article  MATH  Google Scholar 

  • Ng CT, Cheng TCE, Yuan JJ (2006) A note on the complexity of the problem of two-agent scheduling on a single machine. J Comb Optim 12:387–394

    Article  MathSciNet  MATH  Google Scholar 

  • Yuan JJ, Shang W, Feng Q (2005) A note on the scheduling with two families of jobs. J Sched 8:537–542

    Article  MathSciNet  MATH  Google Scholar 

Download references

Author information

Authors and Affiliations

Authors

Corresponding author

Correspondence to Guochuan Zhang.

Additional information

Research supported in part by NSFC (10971192).

Rights and permissions

Reprints and permissions

About this article

Cite this article

Luo, W., Chen, L. & Zhang, G. Approximation schemes for two-machine flow shop scheduling with two agents. J Comb Optim 24, 229–239 (2012). https://doi.org/10.1007/s10878-011-9378-2

Download citation

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10878-011-9378-2

Keywords

Navigation