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]

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

[2]

Ana Rita Nogueira, João Gama, Carlos Abreu Ferreira. Causal discovery in machine learning: Theories and applications. Journal of Dynamics & Games, 2021  doi: 10.3934/jdg.2021008

[3]

Shan-Shan Lin. Due-window assignment scheduling with learning and deterioration effects. Journal of Industrial & Management Optimization, 2021  doi: 10.3934/jimo.2021081

[4]

Ahmad Mousavi, Zheming Gao, Lanshan Han, Alvin Lim. Quadratic surface support vector machine with L1 norm regularization. Journal of Industrial & Management Optimization, 2021  doi: 10.3934/jimo.2021046

[5]

Mehmet Duran Toksari, Emel Kizilkaya Aydogan, Berrin Atalay, Saziye Sari. Some scheduling problems with sum of logarithm processing times based learning effect and exponential past sequence dependent delivery times. Journal of Industrial & Management Optimization, 2021  doi: 10.3934/jimo.2021044

[6]

Bouthaina Abdelhedi, Hatem Zaag. Single point blow-up and final profile for a perturbed nonlinear heat equation with a gradient and a non-local term. Discrete & Continuous Dynamical Systems - S, 2021  doi: 10.3934/dcdss.2021032

[7]

Sishu Shankar Muni, Robert I. McLachlan, David J. W. Simpson. Homoclinic tangencies with infinitely many asymptotically stable single-round periodic solutions. Discrete & Continuous Dynamical Systems, 2021, 41 (8) : 3629-3650. doi: 10.3934/dcds.2021010

[8]

Muberra Allahverdi, Harun Aydilek, Asiye Aydilek, Ali Allahverdi. A better dominance relation and heuristics for Two-Machine No-Wait Flowshops with Maximum Lateness Performance Measure. Journal of Industrial & Management Optimization, 2021, 17 (4) : 1973-1991. doi: 10.3934/jimo.2020054

2019 Impact Factor: 1.366

Metrics

  • PDF downloads (90)
  • HTML views (374)
  • Cited by (1)

Other articles
by authors

[Back to Top]