American Institute of Mathematical Sciences

Advanced
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

Chuanli Zhao ,

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

Keywords: Scheduling, single machine, deteriorating jobs, FPTAS.
Mathematics Subject Classification: Primary: 90B35; Secondary: 90C26.
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. Bachman, A. 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. Cheng, Q. 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. Zhao, C.-J. Hsu, S.-R. Cheng, Y. 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. Bachman, A. 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. Cheng, Q. 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. Zhao, C.-J. Hsu, S.-R. Cheng, Y. 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]

Gheorghe Craciun, Jiaxin Jin, Polly Y. Yu. Single-target networks. Discrete & Continuous Dynamical Systems - B, 2021  doi: 10.3934/dcdsb.2021065

2019 Impact Factor: 1.366

Tools

Metrics

  • PDF downloads (86)
  • HTML views (373)
  • Cited by (1)

Other articles
by authors

[Back to Top]

Copyright © 2021 American Institute of Mathematical Sciences