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 and 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.

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

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

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

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

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

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

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

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

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

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

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

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

[14]

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

[15]

E. Sanlaville and G. Schmidt, Machine scheduling with availability constraints, Acta Informatica, 35 (1998), 795-811. 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-74. 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-93. 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-842. 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-498 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-13. 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, W. H. Freeman and Co., San Francisco, CA, 1979.

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

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

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

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

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

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

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

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

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

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

[14]

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

[15]

E. Sanlaville and G. Schmidt, Machine scheduling with availability constraints, Acta Informatica, 35 (1998), 795-811. 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-74. 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-93. 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-842. 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 and 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 and Management Optimization, 2017, 13 (2) : 713-720. doi: 10.3934/jimo.2016042
[3]

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

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 and Management Optimization, 2016, 12 (4) : 1391-1415. doi: 10.3934/jimo.2016.12.1391
[5]

Cuixia Miao, Yuzhong Zhang. Scheduling with step-deteriorating jobs to minimize the makespan. Journal of Industrial and Management Optimization, 2019, 15 (4) : 1955-1964. doi: 10.3934/jimo.2018131
[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 and Management Optimization, 2021  doi: 10.3934/jimo.2021142
[7]

Ji-Bo Wang, Dan-Yang Lv, Shi-Yun Wang, Chong Jiang. Resource allocation scheduling with deteriorating jobs and position-dependent workloads. Journal of Industrial and Management Optimization, 2022  doi: 10.3934/jimo.2022011
[8]

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

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 and Management Optimization, 2020, 16 (6) : 2943-2969. doi: 10.3934/jimo.2019088
[10]

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

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

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 and Management Optimization, 2017, 13 (4) : 2015-2031. doi: 10.3934/jimo.2017029
[13]

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 and Management Optimization, 2017, 13 (2) : 1025-1039. doi: 10.3934/jimo.2016060
[14]

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

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 and Management Optimization, 2014, 10 (1) : 243-258. doi: 10.3934/jimo.2014.10.243
[16]

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

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 and Management Optimization, 2014, 10 (4) : 1071-1090. doi: 10.3934/jimo.2014.10.1071
[18]

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

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

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

2021 Impact Factor: 1.411

Tools

Metrics

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

Other articles
by authors

[Back to Top]

Copyright © 2022 American Institute of Mathematical Sciences | Privacy Policy