April  2017, 13(2): 587-593. doi: 10.3934/jimo.2016033

An fptas for the weighted number of tardy jobs minimization on a single machine with deteriorating jobs

School of Mathematics and Systems Science, Shenyang Normal University, Shenyang, Liaoning 110034, China

* Corresponding author

Received  September 2015 Revised  December 2015 Published  May 2016

Fund Project: This paper was supported by Science and Research Project Foundation of Liaoning Province Education Department (L2014433)

We consider a single machine scheduling problem in which the processing time of a job is a nondecreasing function of its starting time. The jobs have a common due date. The objective is to minimize the weighted number of tardy jobs. The problem is NP-hard. We present a pseudo-polynomial dynamic programming algorithm and a fully polynomial-time approximation scheme (FPTAS).

Citation: 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
References:
[1]

G. I. B. Alidaee and N. K. Womer, Scheduling with time dependent processing times: Review and extensions, Journal of the Operational Research Society, 50 (1999), 711-720. Google Scholar

[2]

A. Bachman and A. Janiak, Minimizing maximum lateness under linear deterioration, European Journal of Operational Research, 126 (2000), 557-566. doi: 10.1016/S0377-2217(99)00310-0. Google Scholar

[3]

A. BachmanA. Janiak and M. Y. Kovalyov, Minimizing the total weighted completion time of deteriorating jobs, Information Processing Letters, 81 (2002), 81-84. doi: 10.1016/S0020-0190(01)00196-X. Google Scholar

[4]

S. Browne and U. Yechiali, Scheduling deteriorating jobs on a single processor, Operations Research, 38 (1990), 495-498. doi: 10.1287/opre.38.3.495. Google Scholar

[5]

Z.-L. Chen, A note on single-processor scheduling with time-dependent execution times, Operations Research Letters, 17 (1995), 127-129. doi: 10.1016/0167-6377(94)00058-E. Google Scholar

[6]

T. C. E. ChengQ. Ding and B. M. T. Lin, A concise survey of scheduling with time-dependent processing times, European Journal of Operational Research, 152 (2004), 1-13. doi: 10.1016/S0377-2217(02)00909-8. Google Scholar

[7]

S. Gawiejnowicz, Time-Dependent Scheduling, Springer-Verlag Berlin Heidelberg, 2008. Google Scholar

[8]

J. N. D. Gupta and S. K. Gupta, Single facility scheduling with nonlinear processing times, Computers and Industrial Engineering, 14 (1998), 387-393. Google Scholar

[9]

A. Kononov, Scheduling problems with linear increasing processing times, in Operations Research Proceedings 1996 (eds. U. Zimmermann et al.), Berlin-Heidelberg, Springer, (1997), 208–212. Google Scholar

[10]

A. Kononov and S. Gawiejnowicz, NP-hard cases in scheduling deteriorating jobs on dedicated machines, Journal of the Operational Research Society, 52 (2001), 708-717. doi: 10.1057/palgrave.jors.2601117. Google Scholar

[11]

M. Y. Kovalyov and W. Kubiak, A fully polynomial approximation scheme for minimizing makespan of deteriorating jobs, Journal of Heuristics, 3 (1998), 287-297. Google Scholar

[12]

M. Y. Kovalyov and W. Kubiak, A fully polynomial approximation scheme for the weighted earliness-tardiness problem, Operations Research, 47 (1999), 757-761. doi: 10.1287/opre.47.5.757. Google Scholar

[13]

M. Pinedo, Theory, Algorithms, and Systems, Prentice-Hall, Upper Saddle River, 2008. Google Scholar

[14]

G. J. Woeginger, Scheduling with time-dependent execution times, Information Processing Letters, 54 (1995), 155-156. doi: 10.1016/0020-0190(95)00011-Z. Google Scholar

[15]

C. L. ZhaoC.-J. HsuS.-R. ChengY. Q. Yin and C.-C. Wu, Due date assignment and single machine scheduling with deteriorating jobs to minimize the weighted number of tardy jobs, Applied Mathematics and Computation, 248 (2014), 503-510. doi: 10.1016/j.amc.2014.09.095. Google Scholar

show all references

References:
[1]

G. I. B. Alidaee and N. K. Womer, Scheduling with time dependent processing times: Review and extensions, Journal of the Operational Research Society, 50 (1999), 711-720. Google Scholar

[2]

A. Bachman and A. Janiak, Minimizing maximum lateness under linear deterioration, European Journal of Operational Research, 126 (2000), 557-566. doi: 10.1016/S0377-2217(99)00310-0. Google Scholar

[3]

A. BachmanA. Janiak and M. Y. Kovalyov, Minimizing the total weighted completion time of deteriorating jobs, Information Processing Letters, 81 (2002), 81-84. doi: 10.1016/S0020-0190(01)00196-X. Google Scholar

[4]

S. Browne and U. Yechiali, Scheduling deteriorating jobs on a single processor, Operations Research, 38 (1990), 495-498. doi: 10.1287/opre.38.3.495. Google Scholar

[5]

Z.-L. Chen, A note on single-processor scheduling with time-dependent execution times, Operations Research Letters, 17 (1995), 127-129. doi: 10.1016/0167-6377(94)00058-E. Google Scholar

[6]

T. C. E. ChengQ. Ding and B. M. T. Lin, A concise survey of scheduling with time-dependent processing times, European Journal of Operational Research, 152 (2004), 1-13. doi: 10.1016/S0377-2217(02)00909-8. Google Scholar

[7]

S. Gawiejnowicz, Time-Dependent Scheduling, Springer-Verlag Berlin Heidelberg, 2008. Google Scholar

[8]

J. N. D. Gupta and S. K. Gupta, Single facility scheduling with nonlinear processing times, Computers and Industrial Engineering, 14 (1998), 387-393. Google Scholar

[9]

A. Kononov, Scheduling problems with linear increasing processing times, in Operations Research Proceedings 1996 (eds. U. Zimmermann et al.), Berlin-Heidelberg, Springer, (1997), 208–212. Google Scholar

[10]

A. Kononov and S. Gawiejnowicz, NP-hard cases in scheduling deteriorating jobs on dedicated machines, Journal of the Operational Research Society, 52 (2001), 708-717. doi: 10.1057/palgrave.jors.2601117. Google Scholar

[11]

M. Y. Kovalyov and W. Kubiak, A fully polynomial approximation scheme for minimizing makespan of deteriorating jobs, Journal of Heuristics, 3 (1998), 287-297. Google Scholar

[12]

M. Y. Kovalyov and W. Kubiak, A fully polynomial approximation scheme for the weighted earliness-tardiness problem, Operations Research, 47 (1999), 757-761. doi: 10.1287/opre.47.5.757. Google Scholar

[13]

M. Pinedo, Theory, Algorithms, and Systems, Prentice-Hall, Upper Saddle River, 2008. Google Scholar

[14]

G. J. Woeginger, Scheduling with time-dependent execution times, Information Processing Letters, 54 (1995), 155-156. doi: 10.1016/0020-0190(95)00011-Z. Google Scholar

[15]

C. L. ZhaoC.-J. HsuS.-R. ChengY. Q. Yin and C.-C. Wu, Due date assignment and single machine scheduling with deteriorating jobs to minimize the weighted number of tardy jobs, Applied Mathematics and Computation, 248 (2014), 503-510. doi: 10.1016/j.amc.2014.09.095. Google Scholar

[1]

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

[2]

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

[3]

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

[4]

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

[5]

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

[6]

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

[7]

Güvenç Şahin, Ravindra K. Ahuja. Single-machine scheduling with stepwise tardiness costs and release times. Journal of Industrial & Management Optimization, 2011, 7 (4) : 825-848. doi: 10.3934/jimo.2011.7.825

[8]

Hua-Ping Wu, Min Huang, W. H. Ip, Qun-Lin Fan. Algorithms for single-machine scheduling problem with deterioration depending on a novel model. Journal of Industrial & Management Optimization, 2017, 13 (2) : 681-695. doi: 10.3934/jimo.2016040

[9]

Ganggang Li, Xiwen Lu, Peihai Liu. The coordination of single-machine scheduling with availability constraints and delivery. Journal of Industrial & Management Optimization, 2016, 12 (2) : 757-770. doi: 10.3934/jimo.2016.12.757

[10]

Jiayu Shen, Yuanguo Zhu. An uncertain programming model for single machine scheduling problem with batch delivery. Journal of Industrial & Management Optimization, 2019, 15 (2) : 577-593. doi: 10.3934/jimo.2018058

[11]

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

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

Jiping Tao, Zhijun Chao, Yugeng Xi. A semi-online algorithm and its competitive analysis for a single machine scheduling problem with bounded processing times. Journal of Industrial & Management Optimization, 2010, 6 (2) : 269-282. doi: 10.3934/jimo.2010.6.269

[14]

Chuanli Zhao, Yunqiang Yin, T. C. E. Cheng, Chin-Chia Wu. Single-machine scheduling and due date assignment with rejection and position-dependent processing times. Journal of Industrial & Management Optimization, 2014, 10 (3) : 691-700. doi: 10.3934/jimo.2014.10.691

[15]

Yunqiang Yin, T. C. E. Cheng, Jianyou Xu, Shuenn-Ren Cheng, Chin-Chia Wu. Single-machine scheduling with past-sequence-dependent delivery times and a linear deterioration. Journal of Industrial & Management Optimization, 2013, 9 (2) : 323-339. doi: 10.3934/jimo.2013.9.323

[16]

Xingong Zhang. Single machine and flowshop scheduling problems with sum-of-processing time based learning phenomenon. Journal of Industrial & Management Optimization, 2017, 13 (5) : 1-14. doi: 10.3934/jimo.2018148

[17]

Hongwei Li, Yuvraj Gajpal, C. R. Bector. A survey of due-date related single-machine with two-agent scheduling problem. Journal of Industrial & Management Optimization, 2017, 13 (5) : 1-19. doi: 10.3934/jimo.2019005

[18]

Ping Yan, Ji-Bo Wang, Li-Qiang Zhao. Single-machine bi-criterion scheduling with release times and exponentially time-dependent learning effects. Journal of Industrial & Management Optimization, 2019, 15 (3) : 1117-1131. doi: 10.3934/jimo.2018088

[19]

Leiyang Wang, Zhaohui Liu. Heuristics for parallel machine scheduling with batch delivery consideration. Journal of Industrial & Management Optimization, 2014, 10 (1) : 259-273. doi: 10.3934/jimo.2014.10.259

[20]

Xianzhao Zhang, Dachuan Xu, Donglei Du, Cuixia Miao. Approximate algorithms for unrelated machine scheduling to minimize makespan. Journal of Industrial & Management Optimization, 2016, 12 (2) : 771-779. doi: 10.3934/jimo.2016.12.771

2018 Impact Factor: 1.025

Metrics

  • PDF downloads (29)
  • HTML views (277)
  • Cited by (0)

Other articles
by authors

[Back to Top]