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]

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

Hongtruong Pham, Xiwen Lu. The inverse parallel machine scheduling problem with minimum total completion time. Journal of Industrial & Management Optimization, 2014, 10 (2) : 613-620. doi: 10.3934/jimo.2014.10.613
[4]

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

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

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

Ran Ma, Jiping Tao. An improved 2.11-competitive algorithm for online scheduling on parallel machines to minimize total weighted completion time. Journal of Industrial & Management Optimization, 2018, 14 (2) : 497-510. doi: 10.3934/jimo.2017057
[8]

Jinjiang Yuan, Weiping Shang. A PTAS for the p-batch scheduling with pj = p to minimize total weighted completion time. Journal of Industrial & Management Optimization, 2005, 1 (3) : 353-358. doi: 10.3934/jimo.2005.1.353
[9]

P. Liu, Xiwen Lu. Online scheduling of two uniform machines to minimize total completion times. Journal of Industrial & Management Optimization, 2009, 5 (1) : 95-102. doi: 10.3934/jimo.2009.5.95
[10]

Muberra Allahverdi, Ali Allahverdi. Minimizing total completion time in a two-machine no-wait flowshop with uncertain and bounded setup times. Journal of Industrial & Management Optimization, 2017, 13 (5) : 1-19. doi: 10.3934/jimo.2019062
[11]

Chuanli Zhao. An fptas for the weighted number of tardy jobs minimization on a single machine with deteriorating jobs. Journal of Industrial & Management Optimization, 2017, 13 (2) : 587-593. doi: 10.3934/jimo.2016033
[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]

Zhichao Geng, Jinjiang Yuan. Scheduling family jobs on an unbounded parallel-batch machine to minimize makespan and maximum flow time. Journal of Industrial & Management Optimization, 2018, 14 (4) : 1479-1500. doi: 10.3934/jimo.2018017
[14]

Wen-Hung Wu, Yunqiang Yin, Wen-Hsiang Wu, Chin-Chia Wu, Peng-Hsiang Hsu. A time-dependent scheduling problem to minimize the sum of the total weighted tardiness among two agents. Journal of Industrial & Management Optimization, 2014, 10 (2) : 591-611. doi: 10.3934/jimo.2014.10.591
[15]

Muminu O. Adamu, Aderemi O. Adewumi. A survey of single machine scheduling to minimize weighted number of tardy jobs. Journal of Industrial & Management Optimization, 2014, 10 (1) : 219-241. doi: 10.3934/jimo.2014.10.219
[16]

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

Chengxin Luo. Single machine batch scheduling problem to minimize makespan with controllable setup and jobs processing times. Numerical Algebra, Control & Optimization, 2015, 5 (1) : 71-77. doi: 10.3934/naco.2015.5.71
[18]

Lu Liu, Zhi-Feng Pang, Yuping Duan. Retinex based on exponent-type total variation scheme. Inverse Problems & Imaging, 2018, 12 (5) : 1199-1217. doi: 10.3934/ipi.2018050
[19]

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

Z.G. Feng, K.L. Teo, Y. Zhao. Branch and bound method for sensor scheduling in discrete time. Journal of Industrial & Management Optimization, 2005, 1 (4) : 499-512. doi: 10.3934/jimo.2005.1.499

2018 Impact Factor: 1.025

Tools

Metrics

  • PDF downloads (17)
  • HTML views (0)
  • Cited by (2)

Other articles
by authors

[Back to Top]

Copyright © 2019 American Institute of Mathematical Sciences