Skip to main content
SpringerLink
Log in

Single-machine scheduling with preemptive jobs and workload-dependent maintenance durations

  • Original Paper
  • Published:
Operational Research Aims and scope Submit manuscript

Abstract

A single-machine scheduling problem with preemptive jobs and workload-dependent maintenance durations is considered. The length of a maintenance duration is modeled as an non-negative increasing function of the total processing time of the jobs scheduled between the current maintenance and the latest previous one. The objective is to minimize the makespan. Two optimal algorithms are proposed for the case where the maintenance duration function is convex and the case where the maintenance duration function is concave, respectively.

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

Access this article

Log in via an institution

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

Similar content being viewed by others

References

  • Akturk MS, Ghosh JB, Gunes ED (2003) Scheduling with tool changes to minimize total completion time: a study of heuristics and their performance. Nav Res Logist 50:15–30

    Article  MATH  MathSciNet  Google Scholar 

  • Akturk MS, Ghosh JB, Gunes ED (2004) Scheduling with tool changes to minimize total completion time: basic results and SPT performance. Eur J Oper Res 157:784–790

    Article  MATH  MathSciNet  Google Scholar 

  • Akturk MS, Ghosh JB, Kayan PK (2007) Scheduling with tool changes to minimize total completion time under controllable machining conditions. Comput Oper Res 34:2130–2146

    Article  MATH  MathSciNet  Google Scholar 

  • Boyd S, Vandenberghe L (2004) Convex optimization. Cambridge University Press, Cambridge

    Book  MATH  Google Scholar 

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

    Article  MATH  Google Scholar 

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

    Article  MATH  Google Scholar 

  • Chen J-S (2008b) Optimization models for the tool change scheduling problem. Omega Int J Manag Sci 36:888–894

    Article  Google Scholar 

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

    Article  MATH  Google Scholar 

  • Chen WJ (2007a) Scheduling of jobs and maintenance in a textile company. Int J Adv Manuf Technol 31:737–742

    Article  Google Scholar 

  • Chen WJ (2007b) An efficient algorithm for scheduling jobs on a machine with periodic maintenance. Int J Adv Manuf Technol 34:1173–1182

    Article  Google Scholar 

  • Chen WJ (2009) Minimizing number of tardy jobs on a single machine subject to periodic maintenance. Omega Int J Manag Sci 37:591–599

    Article  Google Scholar 

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

    Article  MATH  MathSciNet  Google Scholar 

  • Ji M, He Y, Cheng TCE (2007) Single-machine scheduling with periodic maintenance to minimize makespan. Comput Oper Res 34:1764–1770

    Article  MATH  MathSciNet  Google Scholar 

  • Liao CJ, Chen WJ (2003) Single-machine scheduling with periodic maintenance and nonresumable jobs. Comput Oper Res 30:1335–1347

    Article  MATH  MathSciNet  Google Scholar 

  • Pinedo M (2012) Scheduling theory: algorithms, and systems, 4th edn. Springer, New York

    Book  Google Scholar 

  • Qi X, Chen T, Tu F (1999) Scheduling the maintenance on a single machine. J Oper Res Soc 50:1071–1078

    Article  MATH  Google Scholar 

  • Qi X (2007) A note on worst-case performance of heuristics for maintenance scheduling problems. Discrete Appl Math 155:416–422

    Article  MATH  MathSciNet  Google Scholar 

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

    Article  Google Scholar 

  • Sheen G-J, Liao L-W (2007) Scheduling machine-dependent jobs to minimize lateness on machines with identical speed under availability constraints. Comput Oper Res 34:2266–2278

    Article  MATH  Google Scholar 

  • Shi X, Xu D (2014) Best possible approximation algorithms for single machine scheduling with increasing linear maintenance durations. Sci World J 2014:1–8

    MathSciNet  Google Scholar 

  • Sun K, Li H (2010) Scheduling problems with multiple maintenance activities and non-preemptive jobs on two identical parallel machines. Int J Prod Econ 124:151–158

    Article  Google Scholar 

  • Xu D, Cheng Z, Yin Y, Li H (2009) Makespan minimization for two parallel machines scheduling with a periodic availability constraint. Comput Oper Res 36:1809–1812

    Article  MATH  MathSciNet  Google Scholar 

  • Xu D, Liu A, Yang D-L (2014) Mathematical programming models for competitive two-agent single-machine scheduling with flexible periodic maintenance activities. Arab J Sci Eng 39:3715–3722

    Article  MathSciNet  Google Scholar 

  • Xu D, Liu M, Yin Y, Hao J (2013) Scheduling tool changes and special jobs on a single machine to minimize makespan. Omega Int J Manag Sci 41:299–304

    Article  Google Scholar 

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

    Article  MATH  MathSciNet  Google Scholar 

  • Xu D, Yang D-L (2013) Makespan minimization for two parallel machines scheduling with a periodic availability constraint: mathematical programming model, average-case analysis, and anomalies. Appl Math Model 37:7561–7567

    Article  MathSciNet  Google Scholar 

  • Xu D, Yin Y (2011) On single-machine scheduling with flexible maintenance activities. Int J Adv Manuf Technol 56:1139–1145

    Article  Google Scholar 

  • Xu D, Yin Y, Li H (2010) Scheduling jobs under increasing linear machine maintenance time. J Sched 13:443–449

    Article  MATH  MathSciNet  Google Scholar 

  • Zorich VA (2004) Mathematical analysis: I. Springer, Berlin

    Google Scholar 

Download references

Acknowledgments

This research was supported in part by the National Natural Science Foundation of China (71201022) and the Natural Science Foundation of Jiangxi Province (20122BAB201010).

Author information

Authors and Affiliations

  1. Department of Mathematics, Tongji University, Shanghai, 200092, People’s Republic of China

    Zhijun Xu

  2. College of Science, East China Institute of Technology, Nanchang, 330013, Jiangxi, People’s Republic of China

    Zhijun Xu & Dehua Xu

Authors
  1. Zhijun Xu
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Dehua Xu
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Dehua Xu.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Xu, Z., Xu, D. Single-machine scheduling with preemptive jobs and workload-dependent maintenance durations. Oper Res Int J 15, 423–436 (2015). https://doi.org/10.1007/s12351-015-0179-8

Download citation

  • Received:

  • Revised:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s12351-015-0179-8

Keywords

Search

Navigation