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

Previous Article
JIMO Home
This Issue
Next Article
Variable fractional delay filter design with discrete coefficients

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

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

Abstract
Related Papers

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.
[2]	S. Gawiejnowicz, Time-Dependent Scheduling,, EATC Monograph in Theoretical Computer Science, (2008).
[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.
[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.
[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.
[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.
[7]	C.-Y. Lee, Machine scheduling with an availability constraint,, Journal of Global Optimization, 9 (1996), 395. doi: 10.1007/BF00121681.
[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.
[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.
[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.
[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.

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.
[2]	S. Gawiejnowicz, Time-Dependent Scheduling,, EATC Monograph in Theoretical Computer Science, (2008).
[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.
[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.
[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.
[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.
[7]	C.-Y. Lee, Machine scheduling with an availability constraint,, Journal of Global Optimization, 9 (1996), 395. doi: 10.1007/BF00121681.
[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.
[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.
[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.
[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.

[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, 2017, 13 (5) : 1-10. 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]	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
[12]	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
[13]	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
[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, 2017, 13 (5) : 1-17. 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

2017 Impact Factor: 0.994

American Institute of Mathematical Sciences