Skip to main content
Springer Nature Link
Log in

Mathematical Programming Models for Competitive Two-Agent Single-Machine Scheduling with Flexible Periodic Maintenance Activities

  • Research Article - Computer Engineering and Computer Science
  • Published:
Arabian Journal for Science and Engineering Aims and scope Submit manuscript

Abstract

Competitive multi-agent scheduling has attracted increasingly more and more researchers’ attention recently. Inspired by the observation that a machine may not be always available during the whole planning horizon, we study a new category of scheduling problems where competitive two-agent scheduling and flexible periodic maintenance are considered simultaneously. As a start of this new topic, we focus our attention on establishing mathematical programming models for some of these scheduling problems. Specifically, we first present a framework for the general problem, and then construct various constraint blocks, which include common constraint block, constraint block for the relationship between start times and completion times of the jobs, constraint block for the relationship between the jobs and the maintenance activities, constraint block for various regular objective functions of the two agents, constraint block for the ranges of variables, and constraint block for the other constraint factors. One can establish mathematical programming models for at least 512 scheduling scenarios of this category easily based on these constraint blocks. The work presented in this paper is extremely useful for the production managers and software developers who are seeking for optimization models to generate optimal schedules for their problems.

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. Agnetis A., Mirchandani P.B., Pacciarelli D., Pacifici A.: Scheduling problems with two competing agents. Oper. Res. 52, 229–242 (2004)

    Article  MATH  MathSciNet  Google Scholar 

  2. Ng C.T., Cheng T.C.E., Yuan J.J.: A note on the complexity of the problem of two-agent scheduling on a single machine. J. Comb. Optim. 12, 387–394 (2006)

    Article  MATH  MathSciNet  Google Scholar 

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

    Google Scholar 

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

    Google Scholar 

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

    Article  MATH  MathSciNet  Google Scholar 

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

    Article  MATH  MathSciNet  Google Scholar 

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

    Google Scholar 

  8. LiuP. Tang L.X.: Two-agent scheduling with linear deteriorating jobs on a single machine. Lect. Notes Comput. Sci. 5092, 642–650 (2008)

    Article  Google Scholar 

  9. Gawiejnowicz, S.; Lee, W.-C.; Lin, C.-L.; Wu, C.-C.: Single-machine scheduling of proportionally deteriorating jobs by two agents. J. Oper. Res. Soc. 62, 1983–1991 (2011)

    Google Scholar 

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

    Google Scholar 

  11. Liu P., Yi N., Zhou X.: Two-agent single-machine scheduling problems under increasing linear deterioration. Appl. Math. Model. 35, 2290–2296 (2011)

    Article  MATH  MathSciNet  Google Scholar 

  12. Chen J.S.: Single-machine scheduling with flexible and periodic maintenance. J. Oper. Res. Soc. 57, 703–710 (2006)

    Article  MATH  Google Scholar 

  13. Chen J.S.: Scheduling of nonresumable jobs and flexible maintenance activities on a single machine to minimize makespan. Eur. J. Oper. Res. 190, 90–102 (2008)

    Article  MATH  Google Scholar 

  14. Chen J.S.: Optimization models for the machine scheduling problem with a single flexible maintenance activity. Eng. Optim. 38, 53–71 (2006)

    Article  MathSciNet  Google Scholar 

  15. Yang, D.L.; Hung, C.L.; Hsu, C.J.; Chern, M.S.: Minimizing the makespan in a single machine scheduling problem with a flexible maintenance. J. Chin. Inst. Ind. Eng. 19, 63–66 (2002)

    Google Scholar 

  16. Xu, D.; Yin, Y.; Li, H.: A note on “scheduling of nonresumable jobs and flexible maintenance activities on a single machine to minimize makespan”. Eur. J. Oper. Res. 197, 825–827 (2009)

    Google Scholar 

  17. Chen W.J.: Scheduling of jobs and maintenance in a textile company. Int. J. Adv. Manuf. Tech. 31, 737–742 (2007)

    Article  Google Scholar 

  18. Chen W.J.: Minimizing total flow time in the single-machine scheduling problem with periodic maintenance. J. Oper. Res. Soc. 57, 410–415 (2006)

    Article  MATH  Google Scholar 

  19. Chen, W.J.: An efficient algorithm for scheduling jobs on a machine with periodic maintenance. Int. J. Adv. Manuf. Tech. 34, 1173–1182 (2007)

    Google Scholar 

  20. Chen W.J.: Minimizing number of tardy jobs on a single machine subject to periodic maintenance. Omega Int. J. Manage. S. 37, 591–599 (2009)

    Article  Google Scholar 

  21. Liao, C.J.; Chen, W.J.: Single-machine scheduling with periodic maintenance and nonresumable jobs. Comput. Oper. Res. 30, 1335–1347 (2003)

    Google Scholar 

  22. Sbihi, M.; Varnier, C.: Single-machine scheduling with periodic and flexible periodic maintenance to minimize maximum tardiness. Comput. Ind. Eng. 55, 830–840 (2008)

    Google Scholar 

  23. Xu, D.; Sun, K.; Li, H.: Parallel machine scheduling with almost periodic maintenance and non-preemptive jobs to minimize makespan. Comput. Oper. Res. 35, 1344–1349(2008)

    Google Scholar 

  24. Behnamian, J.; Zandieh, M.: Earliness and tardiness minimizing on a realistic hybrid flowshop scheduling with learning effect by advanced metaheuristic. Arab. J. Sci. Eng. 38, 1229–1242 (2013)

    Google Scholar 

  25. Molaei S., Vahdani B., Molaei S.: A molecular algorithm for an operation-based job shop scheduling problem. Arab. J. Sci. Eng. 38, 2993–3003 (2013)

    Article  MathSciNet  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. School of Science, East China Institute of Technology, Nanchang, 330013, Jiangxi, People’s Republic of China

    Dehua Xu & Aihua Liu

  2. School of Science, East China Institute of Technology, Fuzhou, 344000, Jiangxi, People’s Republic of China

    Dehua Xu & Aihua Liu

  3. Department of Information Management, National Formosa University, Yun-Lin, 632, Taiwan

    Dar-Li Yang

Authors
  1. Dehua Xu
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Aihua Liu
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Dar-Li Yang
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Dar-Li Yang.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Xu, D., Liu, A. & Yang, DL. Mathematical Programming Models for Competitive Two-Agent Single-Machine Scheduling with Flexible Periodic Maintenance Activities. Arab J Sci Eng 39, 3715–3722 (2014). https://doi.org/10.1007/s13369-014-1003-0

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s13369-014-1003-0

Keywords

Search

Navigation