American Institute of Mathematical Sciences

Advanced
July  2016, 12(3): 811-817. doi: 10.3934/jimo.2016.12.811

An improved approximation scheme for scheduling a maintenance and proportional deteriorating jobs

Imed Kacem 1, and  Eugene Levner 2,

1. 

LCOMS EA 7306, Université de Lorraine, 57000 Metz, France
2. 

School of Economics, Ashkelon Academic College, Ashkelon, 78211, Israel

Received  August 2013 Revised  March 2014 Published  September 2015

In this paper, we re-visit the problem of scheduling a set of proportional deteriorating non-resumable jobs on a single machine subject to maintenance. The maintenance has to be started prior to a given deadline. The jobs as well as the maintenance are to be scheduled so that to minimize the total completion time. For this problem we propose a new dynamic programming algorithm and a faster fully polynomial time approximation scheme improving a recent result by Luo and Chen [JIMO (2012), 8:2, 271-283].
Keywords: total completion time, maintenance activities, approximation scheme., deteriorating jobs, Scheduling.
Mathematics Subject Classification: Primary: 90B35; Secondary: 90C5.
Citation: 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
References:
[1]

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

[2]

S. Gawiejnowicz, Time-Dependent Scheduling,, EATC Monograph in Theoretical Computer Science, (2008).   Google Scholar

[3]

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

[4]

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

[5]

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

[6]

H. Kellerer, K. Rustogi and V. A. Strusevich, Approximation schemes for scheduling on a single machine subject to cumulative deterioration and maintenance,, Journal of Scheduling, 16 (2013), 675.  doi: 10.1007/s10951-012-0287-8.  Google Scholar

[7]

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

[8]

W. Luo and L. Chen, Approximation schemes for scheduling a maintenance and linear deteriorating jobs,, Journal of Industrial and Management Optimization, 8 (2012), 271.  doi: 10.3934/jimo.2012.8.271.  Google Scholar

[9]

K. M. Ocetkiewicz, A FPTAS for minimizing total completion time in a single machine time-dependent scheduling problem,, European Journal of Operational Research, 203 (2010), 316.  doi: 10.1016/j.ejor.2009.07.025.  Google Scholar

[10]

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

[11]

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

show all references

References:
[1]

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

[2]

S. Gawiejnowicz, Time-Dependent Scheduling,, EATC Monograph in Theoretical Computer Science, (2008).   Google Scholar

[3]

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

[4]

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

[5]

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

[6]

H. Kellerer, K. Rustogi and V. A. Strusevich, Approximation schemes for scheduling on a single machine subject to cumulative deterioration and maintenance,, Journal of Scheduling, 16 (2013), 675.  doi: 10.1007/s10951-012-0287-8.  Google Scholar

[7]

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

[8]

W. Luo and L. Chen, Approximation schemes for scheduling a maintenance and linear deteriorating jobs,, Journal of Industrial and Management Optimization, 8 (2012), 271.  doi: 10.3934/jimo.2012.8.271.  Google Scholar

[9]

K. M. Ocetkiewicz, A FPTAS for minimizing total completion time in a single machine time-dependent scheduling problem,, European Journal of Operational Research, 203 (2010), 316.  doi: 10.1016/j.ejor.2009.07.025.  Google Scholar

[10]

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

[11]

C.-C. Wu and W.-C. Lee, Scheduling linear deteriorating jobs to minimize makespan with an unavailability constraint on a single machine,, Information Processing Letters, 87 (2003), 89.  doi: 10.1016/S0020-0190(03)00262-X.  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]

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

Xianchao Xiu, Ying Yang, Wanquan Liu, Lingchen Kong, Meijuan Shang. An improved total variation regularized RPCA for moving object detection with dynamic background. Journal of Industrial & Management Optimization, 2020, 16 (4) : 1685-1698. doi: 10.3934/jimo.2019024
[4]

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

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

Marion Darbas, Jérémy Heleine, Stephanie Lohrengel. Numerical resolution by the quasi-reversibility method of a data completion problem for Maxwell's equations. Inverse Problems & Imaging, 2020, 14 (6) : 1107-1133. doi: 10.3934/ipi.2020056
[7]

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

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

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

Cécile Carrère, Grégoire Nadin. Influence of mutations in phenotypically-structured populations in time periodic environment. Discrete & Continuous Dynamical Systems - B, 2020, 25 (9) : 3609-3630. doi: 10.3934/dcdsb.2020075
[11]

Paula A. González-Parra, Sunmi Lee, Leticia Velázquez, Carlos Castillo-Chavez. A note on the use of optimal control on a discrete time model of influenza dynamics. Mathematical Biosciences & Engineering, 2011, 8 (1) : 183-197. doi: 10.3934/mbe.2011.8.183
[12]

Guillermo Reyes, Juan-Luis Vázquez. Long time behavior for the inhomogeneous PME in a medium with slowly decaying density. Communications on Pure & Applied Analysis, 2009, 8 (2) : 493-508. doi: 10.3934/cpaa.2009.8.493
[13]

Wei-Jian Bo, Guo Lin, Shigui Ruan. Traveling wave solutions for time periodic reaction-diffusion systems. Discrete & Continuous Dynamical Systems - A, 2018, 38 (9) : 4329-4351. doi: 10.3934/dcds.2018189
[14]

Kin Ming Hui, Soojung Kim. Asymptotic large time behavior of singular solutions of the fast diffusion equation. Discrete & Continuous Dynamical Systems - A, 2017, 37 (11) : 5943-5977. doi: 10.3934/dcds.2017258
[15]

Xiaomao Deng, Xiao-Chuan Cai, Jun Zou. A parallel space-time domain decomposition method for unsteady source inversion problems. Inverse Problems & Imaging, 2015, 9 (4) : 1069-1091. doi: 10.3934/ipi.2015.9.1069

2019 Impact Factor: 1.366

Tools

Metrics

  • PDF downloads (59)
  • HTML views (0)
  • Cited by (4)

Other articles
by authors

[Back to Top]

Copyright © 2021 American Institute of Mathematical Sciences