American Institute of Mathematical Sciences

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

Approximation schemes for scheduling a maintenance and linear deteriorating jobs

Wenchang Luo 1, and  Lin Chen 2,

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.
Keywords: Scheduling, complexity, deteriorating job, maintenance., approximation scheme.
Mathematics Subject Classification: Primary: 90B35; Secondary: 90C5.
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.  Google Scholar

[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.  Google Scholar

[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).   Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[12]

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

[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.  Google Scholar

[14]

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

[15]

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

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

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.  Google Scholar

[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.  Google Scholar

[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).   Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[12]

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

[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.  Google Scholar

[14]

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

[15]

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

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[1]

Chih-Chiang Fang. Bayesian decision making in determining optimal leased term and preventive maintenance scheme for leased facilities. Journal of Industrial & Management Optimization, 2020  doi: 10.3934/jimo.2020127
[2]

Zhihua Zhang, Naoki Saito. PHLST with adaptive tiling and its application to antarctic remote sensing image approximation. Inverse Problems & Imaging, 2014, 8 (1) : 321-337. doi: 10.3934/ipi.2014.8.321
[3]

Luke Finlay, Vladimir Gaitsgory, Ivan Lebedev. Linear programming solutions of periodic optimization problems: approximation of the optimal control. Journal of Industrial & Management Optimization, 2007, 3 (2) : 399-413. doi: 10.3934/jimo.2007.3.399
[4]

Xianming Liu, Guangyue Han. A Wong-Zakai approximation of stochastic differential equations driven by a general semimartingale. Discrete & Continuous Dynamical Systems - B, 2021, 26 (5) : 2499-2508. doi: 10.3934/dcdsb.2020192
[5]

Caifang Wang, Tie Zhou. The order of convergence for Landweber Scheme with $\alpha,\beta$-rule. Inverse Problems & Imaging, 2012, 6 (1) : 133-146. doi: 10.3934/ipi.2012.6.133
[6]

Wolf-Jüergen Beyn, Janosch Rieger. The implicit Euler scheme for one-sided Lipschitz differential inclusions. Discrete & Continuous Dynamical Systems - B, 2010, 14 (2) : 409-428. doi: 10.3934/dcdsb.2010.14.409
[7]

Alina Chertock, Alexander Kurganov, Mária Lukáčová-Medvi${\rm{\check{d}}}$ová, Șeyma Nur Özcan. An asymptotic preserving scheme for kinetic chemotaxis models in two space dimensions. Kinetic & Related Models, 2019, 12 (1) : 195-216. doi: 10.3934/krm.2019009
[8]

Tomáš Roubíček. An energy-conserving time-discretisation scheme for poroelastic media with phase-field fracture emitting waves and heat. Discrete & Continuous Dynamical Systems - S, 2017, 10 (4) : 867-893. doi: 10.3934/dcdss.2017044
[9]

Rabiaa Ouahabi, Nasr-Eddine Hamri. Design of new scheme adaptive generalized hybrid projective synchronization for two different chaotic systems with uncertain parameters. Discrete & Continuous Dynamical Systems - B, 2021, 26 (5) : 2361-2370. doi: 10.3934/dcdsb.2020182

2019 Impact Factor: 1.366

Tools

Metrics

  • PDF downloads (54)
  • HTML views (0)
  • Cited by (10)

Other articles
by authors

[Back to Top]

Copyright © 2021 American Institute of Mathematical Sciences