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-498 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-13. 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, W. H. Freeman and Co., San Francisco, CA, 1979.  Google Scholar

[4]

S. Gawiejnowicz, Scheduling deteriorating jobs subject to job or machine availability constraints, European Journal of Operational Research, 180 (2007), 472-478. 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-308. 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-318. 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-326. 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-126. 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-1770. 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-347. 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-416. doi: 10.1007/BF00121681.  Google Scholar

[12]

P. Liu and L. Tang, Two-agent scheduling with linear deteriorating jobs on a single machine, in "Computing and Combinatorics," Lecture Notes in Comput. Sci., 5092, Springer, Berlin, (2008), 642-650.  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-211. 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-659. 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-811. 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-74. 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-93. 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-842. 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-498 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-13. 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, W. H. Freeman and Co., San Francisco, CA, 1979.  Google Scholar

[4]

S. Gawiejnowicz, Scheduling deteriorating jobs subject to job or machine availability constraints, European Journal of Operational Research, 180 (2007), 472-478. 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-308. 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-318. 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-326. 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-126. 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-1770. 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-347. 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-416. doi: 10.1007/BF00121681.  Google Scholar

[12]

P. Liu and L. Tang, Two-agent scheduling with linear deteriorating jobs on a single machine, in "Computing and Combinatorics," Lecture Notes in Comput. Sci., 5092, Springer, Berlin, (2008), 642-650.  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-211. 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-659. 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-811. 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-74. 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-93. 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-842. doi: 10.3934/jimo.2008.4.827.  Google Scholar

[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, 2019, 15 (4) : 1955-1964. 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]

Chaoming Hu, Xiaofei Qian, Shaojun Lu, Xinbao Liu, Panos M Pardalos. Coordinated optimization of production scheduling and maintenance activities with machine reliability deterioration. Journal of Industrial & Management Optimization, 2021  doi: 10.3934/jimo.2021142
[7]

Guo Zhou, Yongquan Zhou, Ruxin Zhao. Hybrid social spider optimization algorithm with differential mutation operator for the job-shop scheduling problem. Journal of Industrial & Management Optimization, 2021, 17 (2) : 533-548. doi: 10.3934/jimo.2019122
[8]

Xuewen Huang, Xiaotong Zhang, Sardar M. N. Islam, Carlos A. Vega-Mejía. An enhanced Genetic Algorithm with an innovative encoding strategy for flexible job-shop scheduling with operation and processing flexibility. Journal of Industrial & Management Optimization, 2020, 16 (6) : 2943-2969. doi: 10.3934/jimo.2019088
[9]

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
[10]

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, 2020, 16 (4) : 1801-1834. doi: 10.3934/jimo.2019030
[11]

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
[12]

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
[13]

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, 2020, 16 (1) : 189-205. doi: 10.3934/jimo.2018146
[14]

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
[15]

Chih-Chiang Fang. Bayesian decision making in determining optimal leased term and preventive maintenance scheme for leased facilities. Journal of Industrial & Management Optimization, 2021, 17 (6) : 3445-3473. doi: 10.3934/jimo.2020127
[16]

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
[17]

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
[18]

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
[19]

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
[20]

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

2020 Impact Factor: 1.801

Tools

Metrics

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

Other articles
by authors

[Back to Top]

Copyright © 2022 American Institute of Mathematical Sciences | Privacy Policy