April  2012, 8(2): 271-283. doi: 10.3934/jimo.2012.8.271

Approximation schemes for scheduling a maintenance and linear deteriorating jobs

1. 

Faculty of Science, Ningbo University, Ningbo, 315211, China

2. 

College of Computer Science, Zhejiang University, Hangzhou, 310027, China

Received  October 2010 Revised  July 2011 Published  April 2012

In this paper, we study two problems of scheduling a set of linear deteriorating non-resumable jobs on a single machine with a mandatory maintenance. The maintenance has to be started prior to a given deadline. Not only the jobs but also the maintenance are required to be scheduled. Two goals are investigated. One is to minimize the makespan and the other is to minimize the total completion time. For both objectives, we show that two problems are weakly NP-hard and propose fully polynomial time approximation schemes respectively.
Citation: Wenchang Luo, Lin Chen. Approximation schemes for scheduling a maintenance and linear deteriorating jobs. Journal of Industrial & Management Optimization, 2012, 8 (2) : 271-283. doi: 10.3934/jimo.2012.8.271
References:
[1]

S. Brown and U. Yechiali, Scheduling deteriorating jobs on a single process,, Operations Research, 38 (1990), 495. doi: 10.1287/opre.38.3.495.

[2]

T. C. E. Cheng, Q. Ding and B. M. T. Lin, A concise survey of scheduling with time-dependent processing time,, European Journal of Operation Research, 152 (2004), 1. doi: 10.1016/S0377-2217(02)00909-8.

[3]

M. R. Garey and D. S. Johnson, "Computers and Intractability. A Guide to the Theory of NP-Completeness,", A Series of Books in the Mathematical Sciences, (1979).

[4]

S. Gawiejnowicz, Scheduling deteriorating jobs subject to job or machine availability constraints,, European Journal of Operational Research, 180 (2007), 472. doi: 10.1016/j.ejor.2006.04.021.

[5]

S. Gawiejnowicz and A. Kononov, Complexity and approximability of scheduling resumable proportionally deteriorating jobs,, European Journal of Operational Research, 200 (2010), 305. doi: 10.1016/j.ejor.2008.12.014.

[6]

G. Gens and E. Levner, Fast approximation algorithm for job sequencing with deadlines,, Discrete Applied Mathematics, 3 (1981), 313. doi: 10.1016/0166-218X(81)90008-1.

[7]

R. L. Graham, E. L. Lawler, J. K. Lenstra and A. H. G. Rinnooy Kan, Optimization and approximation in deterministic sequencing and scheduling: A survey,, Annals of Discrete Mathematics, 5 (1979), 287. doi: 10.1016/S0167-5060(08)70356-X.

[8]

M. Ji, Y. He and T. C. E. Cheng, Scheduling linear deteriorating jobs with an availability constraint on a single machine,, Theoretical Computer Science, 362 (2006), 115. doi: 10.1016/j.tcs.2006.06.006.

[9]

M. Ji, Y. He and T. C. E. Cheng, Single-machine scheduling with periodic maintenance to minimize makespan,, Computers & Operations Research, 34 (2007), 1764. doi: 10.1016/j.cor.2005.05.034.

[10]

M. Ji and T. C. E. Cheng, Parallel-machine scheduling with simple linear deterioration to minimize total completion time,, European Journal of Operational Research, 188 (2008), 342. doi: 10.1016/j.ejor.2007.04.050.

[11]

C.-Y. Lee, Machine scheduling with an availability constraint. Optimization applications in scheduling theory,, Journal of Global Optimization, 9 (1996), 395. doi: 10.1007/BF00121681.

[12]

P. Liu and L. Tang, Two-agent scheduling with linear deteriorating jobs on a single machine,, in, 5092 (2008), 642.

[13]

Y. Ma, C. Chu and C. Zuo, A survey of scheduling with deterministic machine availability constraints,, Computers & Industrial Engineering, 58 (2010), 199. doi: 10.1016/j.cie.2009.04.014.

[14]

G. Mosheiov, Scheduling jobs under simple linear deterioration,, Computers & Operations Research, 21 (1994), 653. doi: 10.1016/0305-0548(94)90080-9.

[15]

E. Sanlaville and G. Schmidt, Machine scheduling with availability constraints,, Acta Informatica, 35 (1998), 795. doi: 10.1007/s002360050143.

[16]

G. J. Woeginger, When does a dynamic programming formulation guarantee the existence of a fully polynomial time approximation scheme (FPTAS)?,, INFORMS Journal on Computing, 12 (2000), 57. doi: 10.1287/ijoc.12.1.57.11901.

[17]

C.-C. Wu and W.-C. Lee, Scheduling linear deteriorating jobs to minimize makespan with an availability constraint on a single machine,, Information Processing Letters, 87 (2003), 89. doi: 10.1016/S0020-0190(03)00262-X.

[18]

J. C. P. Yu, H. M. Wee and K. J. Wang, Supply chain partnership for Three-Echelon deteriorating inventory model,, Journal of Industrial and Management Optimization, 4 (2008), 827. doi: 10.3934/jimo.2008.4.827.

show all references

References:
[1]

S. Brown and U. Yechiali, Scheduling deteriorating jobs on a single process,, Operations Research, 38 (1990), 495. doi: 10.1287/opre.38.3.495.

[2]

T. C. E. Cheng, Q. Ding and B. M. T. Lin, A concise survey of scheduling with time-dependent processing time,, European Journal of Operation Research, 152 (2004), 1. doi: 10.1016/S0377-2217(02)00909-8.

[3]

M. R. Garey and D. S. Johnson, "Computers and Intractability. A Guide to the Theory of NP-Completeness,", A Series of Books in the Mathematical Sciences, (1979).

[4]

S. Gawiejnowicz, Scheduling deteriorating jobs subject to job or machine availability constraints,, European Journal of Operational Research, 180 (2007), 472. doi: 10.1016/j.ejor.2006.04.021.

[5]

S. Gawiejnowicz and A. Kononov, Complexity and approximability of scheduling resumable proportionally deteriorating jobs,, European Journal of Operational Research, 200 (2010), 305. doi: 10.1016/j.ejor.2008.12.014.

[6]

G. Gens and E. Levner, Fast approximation algorithm for job sequencing with deadlines,, Discrete Applied Mathematics, 3 (1981), 313. doi: 10.1016/0166-218X(81)90008-1.

[7]

R. L. Graham, E. L. Lawler, J. K. Lenstra and A. H. G. Rinnooy Kan, Optimization and approximation in deterministic sequencing and scheduling: A survey,, Annals of Discrete Mathematics, 5 (1979), 287. doi: 10.1016/S0167-5060(08)70356-X.

[8]

M. Ji, Y. He and T. C. E. Cheng, Scheduling linear deteriorating jobs with an availability constraint on a single machine,, Theoretical Computer Science, 362 (2006), 115. doi: 10.1016/j.tcs.2006.06.006.

[9]

M. Ji, Y. He and T. C. E. Cheng, Single-machine scheduling with periodic maintenance to minimize makespan,, Computers & Operations Research, 34 (2007), 1764. doi: 10.1016/j.cor.2005.05.034.

[10]

M. Ji and T. C. E. Cheng, Parallel-machine scheduling with simple linear deterioration to minimize total completion time,, European Journal of Operational Research, 188 (2008), 342. doi: 10.1016/j.ejor.2007.04.050.

[11]

C.-Y. Lee, Machine scheduling with an availability constraint. Optimization applications in scheduling theory,, Journal of Global Optimization, 9 (1996), 395. doi: 10.1007/BF00121681.

[12]

P. Liu and L. Tang, Two-agent scheduling with linear deteriorating jobs on a single machine,, in, 5092 (2008), 642.

[13]

Y. Ma, C. Chu and C. Zuo, A survey of scheduling with deterministic machine availability constraints,, Computers & Industrial Engineering, 58 (2010), 199. doi: 10.1016/j.cie.2009.04.014.

[14]

G. Mosheiov, Scheduling jobs under simple linear deterioration,, Computers & Operations Research, 21 (1994), 653. doi: 10.1016/0305-0548(94)90080-9.

[15]

E. Sanlaville and G. Schmidt, Machine scheduling with availability constraints,, Acta Informatica, 35 (1998), 795. doi: 10.1007/s002360050143.

[16]

G. J. Woeginger, When does a dynamic programming formulation guarantee the existence of a fully polynomial time approximation scheme (FPTAS)?,, INFORMS Journal on Computing, 12 (2000), 57. doi: 10.1287/ijoc.12.1.57.11901.

[17]

C.-C. Wu and W.-C. Lee, Scheduling linear deteriorating jobs to minimize makespan with an availability constraint on a single machine,, Information Processing Letters, 87 (2003), 89. doi: 10.1016/S0020-0190(03)00262-X.

[18]

J. C. P. Yu, H. M. Wee and K. J. Wang, Supply chain partnership for Three-Echelon deteriorating inventory model,, Journal of Industrial and Management Optimization, 4 (2008), 827. doi: 10.3934/jimo.2008.4.827.

[1]

Imed Kacem, Eugene Levner. An improved approximation scheme for scheduling a maintenance and proportional deteriorating jobs. Journal of Industrial & Management Optimization, 2016, 12 (3) : 811-817. doi: 10.3934/jimo.2016.12.811

[2]

Chunlai Liu, Yanpeng Fan, Chuanli Zhao, Jianjun Wang. Multiple common due-dates assignment and optimal maintenance activity scheduling with linear deteriorating jobs. Journal of Industrial & Management Optimization, 2017, 13 (2) : 713-720. doi: 10.3934/jimo.2016042

[3]

Cuixia Miao, Yuzhong Zhang. Scheduling with step-deteriorating jobs to minimize the makespan. Journal of Industrial & Management Optimization, 2017, 13 (5) : 1-10. doi: 10.3934/jimo.2018131

[4]

M. Ramasubramaniam, M. Mathirajan. A solution framework for scheduling a BPM with non-identical job dimensions. Journal of Industrial & Management Optimization, 2007, 3 (3) : 445-456. doi: 10.3934/jimo.2007.3.445

[5]

Didem Cinar, José António Oliveira, Y. Ilker Topcu, Panos M. Pardalos. A priority-based genetic algorithm for a flexible job shop scheduling problem. Journal of Industrial & Management Optimization, 2016, 12 (4) : 1391-1415. doi: 10.3934/jimo.2016.12.1391

[6]

Y. K. Lin, C. S. Chong. A tabu search algorithm to minimize total weighted tardiness for the job shop scheduling problem. Journal of Industrial & Management Optimization, 2016, 12 (2) : 703-717. doi: 10.3934/jimo.2016.12.703

[7]

Adel Dabah, Ahcene Bendjoudi, Abdelhakim AitZai. An efficient Tabu Search neighborhood based on reconstruction strategy to solve the blocking job shop scheduling problem. Journal of Industrial & Management Optimization, 2017, 13 (4) : 2015-2031. doi: 10.3934/jimo.2017029

[8]

Ji-Bo Wang, Mengqi Liu, Na Yin, Ping Ji. Scheduling jobs with controllable processing time, truncated job-dependent learning and deterioration effects. Journal of Industrial & Management Optimization, 2017, 13 (2) : 1025-1039. doi: 10.3934/jimo.2016060

[9]

Behrad Erfani, Sadoullah Ebrahimnejad, Amirhossein Moosavi. An integrated dynamic facility layout and job shop scheduling problem: A hybrid NSGA-II and local search algorithm. Journal of Industrial & Management Optimization, 2017, 13 (5) : 1-34. doi: 10.3934/jimo.2019030

[10]

Le Thi Hoai An, Tran Duc Quynh, Kondo Hloindo Adjallah. A difference of convex functions algorithm for optimal scheduling and real-time assignment of preventive maintenance jobs on parallel processors. Journal of Industrial & Management Optimization, 2014, 10 (1) : 243-258. doi: 10.3934/jimo.2014.10.243

[11]

Masoud Ebrahimi, Seyyed Mohammad Taghi Fatemi Ghomi, Behrooz Karimi. Application of the preventive maintenance scheduling to increase the equipment reliability: Case study- bag filters in cement factory. Journal of Industrial & Management Optimization, 2017, 13 (5) : 1-17. doi: 10.3934/jimo.2018146

[12]

Peng Guo, Wenming Cheng, Yi Wang. A general variable neighborhood search for single-machine total tardiness scheduling problem with step-deteriorating jobs. Journal of Industrial & Management Optimization, 2014, 10 (4) : 1071-1090. doi: 10.3934/jimo.2014.10.1071

[13]

Azmy S. Ackleh, Kazufumi Ito. An approximation scheme for a nonlinear size-dependent population model. Conference Publications, 1998, 1998 (Special) : 1-6. doi: 10.3934/proc.1998.1998.1

[14]

Michele Coti Zelati. Remarks on the approximation of the Navier-Stokes equations via the implicit Euler scheme. Communications on Pure & Applied Analysis, 2013, 12 (6) : 2829-2838. doi: 10.3934/cpaa.2013.12.2829

[15]

Azmy S. Ackleh, Mark L. Delcambre, Karyn L. Sutton, Don G. Ennis. A structured model for the spread of Mycobacterium marinum: Foundations for a numerical approximation scheme. Mathematical Biosciences & Engineering, 2014, 11 (4) : 679-721. doi: 10.3934/mbe.2014.11.679

[16]

Yongchao Liu, Hailin Sun, Huifu Xu. An approximation scheme for stochastic programs with second order dominance constraints. Numerical Algebra, Control & Optimization, 2016, 6 (4) : 473-490. doi: 10.3934/naco.2016021

[17]

Andrew Yates, Robin Callard. Cell death and the maintenance of immunological memory. Discrete & Continuous Dynamical Systems - B, 2001, 1 (1) : 43-59. doi: 10.3934/dcdsb.2001.1.43

[18]

Stefano Galatolo. Orbit complexity and data compression. Discrete & Continuous Dynamical Systems - A, 2001, 7 (3) : 477-486. doi: 10.3934/dcds.2001.7.477

[19]

Valentin Afraimovich, Lev Glebsky, Rosendo Vazquez. Measures related to metric complexity. Discrete & Continuous Dynamical Systems - A, 2010, 28 (4) : 1299-1309. doi: 10.3934/dcds.2010.28.1299

[20]

Valentin Afraimovich, Maurice Courbage, Lev Glebsky. Directional complexity and entropy for lift mappings. Discrete & Continuous Dynamical Systems - B, 2015, 20 (10) : 3385-3401. doi: 10.3934/dcdsb.2015.20.3385

2017 Impact Factor: 0.994

Metrics

  • PDF downloads (8)
  • HTML views (0)
  • Cited by (8)

Other articles
by authors

[Back to Top]