Nothing Special   »   [go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

Scheduling jobs with general linear deterioration to minimize total weighted number of late jobs

  • Original Paper
  • Published:
Optimization Letters Aims and scope Submit manuscript

Abstract

This paper deals with a single-machine scheduling problem with a general linear deterioration effect. The goal is to determine the job schedule such that the total weighted number of late jobs is minimized. We present three properties, one heuristic algorithm and a lower bound to speed up the search process of the branch-and-bound algorithm. In addition, some complex heuristics (including tabu search and simulated annealing algorithms) are proposed as solutions to this problem. The computational results show that the proposed algorithms are effective and efficient.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1

Similar content being viewed by others

References

  1. Gupta, J.N., Gupta, S.K.: Single facility scheduling with nonlinear processing times. Comput. Ind. Eng. 14(4), 387–393 (1988)

    Article  Google Scholar 

  2. Browne, S., Yechiali, U.: Scheduling deteriorating jobs on a single processor. Oper. Res. 38(3), 495–498 (1990)

    Article  Google Scholar 

  3. Alidaee, B., Womer, N.K.: Scheduling with time dependent processing times: review and extensions. J. Oper. Res. Soc. 50, 711–720 (1999)

    Article  Google Scholar 

  4. Gawiejnowicz, S.: A review of four decades of time-dependent scheduling: main results, new topics, and open problems. J. Sched. 23(1), 3–47 (2020)

    Article  MathSciNet  Google Scholar 

  5. Gawiejnowicz, S.: Models and Algorithms of Time-Dependent Scheduling. Springer, Berlin (2020)

    Book  Google Scholar 

  6. Gupta, S.K., Kunnathur, A.S., Dandapani, K.: Optimal repayment policies for multiple loans. Omega 15, 323–330 (1987)

    Article  Google Scholar 

  7. Mosheiov, G.: Scheduling jobs under simple linear deterioration. Comput. Oper. Res. 21, 653–659 (1994)

    Article  Google Scholar 

  8. Rachaniotis, N.P., Pappis, C.P.: Scheduling fire-fighting tasks using the concept of “deteriorating jobs’’. Can. J. For. Res. 36, 652–658 (2006)

    Article  Google Scholar 

  9. Huang, X., Yin, N., Liu, W.-W., Wang, J.-B.: Common due window assignment scheduling with proportional linear deterioration effects. Asia Pac. J. Oper. Res. 37(1), 1950031 (2020)

    Article  MathSciNet  Google Scholar 

  10. Bachman, A., Cheng, T., Janiak, A.: Scheduling start time dependent jobs to minimize the total weighted completion time. J. Oper. Res. Soc. 53(6), 688–693 (2002)

    Article  Google Scholar 

  11. Hsu, Y.S., Lin, B.M.T.: Minimization of maximum lateness under linear deterioration. Omega 31, 459–469 (2003)

    Article  Google Scholar 

  12. Moslehi, G., Jafari, A.: Minimizing the number of tardy jobs under piecewise-linear deterioration. Comput. Ind. Eng. 59(4), 573–584 (2010)

    Article  Google Scholar 

  13. Wu, C.-C., Wu, W.-H., Wu, W.-H., Hsu, P.-H., Yin, Y., Xu, J.: A single-machine scheduling with a truncated linear deterioration and ready times. Inf. Sci. 256, 109–125 (2014)

    Article  MathSciNet  Google Scholar 

  14. Wang, J.-B., Wang, J.-J.: Single-machine scheduling problems with precedence constraints and simple linear deterioration. Appl. Math. Model. 39(3), 1172–1182 (2015)

    Article  MathSciNet  Google Scholar 

  15. Lee, W.C., Lu, Z.S.: Group scheduling with deteriorating jobs to minimize the total weighted number of late jobs. Appl. Math. Comput. 218, 8750–8757 (2012)

    MathSciNet  Google Scholar 

  16. Wang, J.-B., Wang, J.-J.: Single machine group scheduling with time dependent processing times and ready times. Inf. Sci. 275, 226–231 (2014)

    Article  MathSciNet  Google Scholar 

  17. Liu, F., Yang, J., Lu, Y.-Y.: Solution algorithms for single-machine group scheduling with ready times and deteriorating jobs. Eng. Optim. 51(5), 862–874 (2019)

    Article  MathSciNet  Google Scholar 

  18. Huang, X.: Bicriterion scheduling with group technology and deterioration effect. J. Appl. Math. Comput. 60(1–2), 455–464 (2019)

    Article  MathSciNet  Google Scholar 

  19. Sun, X., Geng, X.-N.: Single-machine scheduling with deteriorating effects and machine maintenance. Int. J. Prod. Res. 57(10), 3186–3199 (2019)

    Article  Google Scholar 

  20. Sun, X., Liu, T., Geng, X.-N., Hu, Y., Xu, J.-X.: Optimization of scheduling problems with deterioration effects and an optional maintenance activity. J. Sched. (2022). https://doi.org/10.1007/s10951-022-00756-4

    Article  Google Scholar 

  21. Jia, X., Lv, D.-Y., Hu, Y., Wang, J.-B., Wang, Z., Wang, E.: Slack due-window assignment scheduling problem with deterioration effects and a deteriorating maintenance activity. Asia Pac. J. Oper. Res. 39(6), 2250005 (2022)

    Article  MathSciNet  Google Scholar 

  22. Oron, D.: Scheduling controllable processing time jobs in a deteriorating environment. J. Oper. Res. Soc. 64, 49–56 (2014)

    Article  Google Scholar 

  23. Wang, J.-B., Liang, X.-X.: Group scheduling with deteriorating jobs and allotted resource under limited resource availability constraint. Eng. Optim. 51(2), 231–246 (2019)

    Article  MathSciNet  Google Scholar 

  24. Sun, L.-H., Ge, C.-C., Zhang, W., Wang, J.-B., Lu, Y.-Y.: Permutation flow shop scheduling with simple linear deterioration. Eng. Optim. 51(8), 1281–1300 (2019)

    Article  MathSciNet  Google Scholar 

  25. Zhang, X., Liu, S.-C., Lin, W.-C., Wu, C.-C.: Parallel-machine scheduling with linear deteriorating jobs and preventive maintenance activities under a potential machine disruption. Comput. Ind. Eng. 145, 106482 (2020)

    Article  Google Scholar 

  26. Kong, M., Liu, X., Pei, J., Zhou, Z., Pardalos, P.M.: Parallel-batching scheduling of deteriorating jobs with non-identical sizes and rejection on a single machine. Optim. Lett. 14, 857–871 (2020)

    Article  MathSciNet  Google Scholar 

  27. Yan, J.-X., Ren, N., Bei, H.-B., Bao, H., Wang, J.-B.: Scheduling with resource allocation, deteriorating effect and group technology to minimize total completion time. Mathematics 10, 2983 (2022)

    Article  Google Scholar 

  28. Teng, F., Luo, S.-W., Lv, D.-Y., Wang, J.-B.: Approaches to solving scheduling with due-window assignment and deterioration effects. Asia Pac. J. Oper. Res. 40(2), 2250022 (2023)

    Article  MathSciNet  Google Scholar 

  29. Pan, L., Sun, X., Wang, J.-B., Zhang, L.-H., Lv, D.-Y.: Due date assignment single-machine scheduling with delivery times, position-dependent weights and deteriorating jobs. J. Comb. Optim. 45, 100 (2023)

    Article  MathSciNet  Google Scholar 

  30. Wang, J.-B., Lv, D.-Y., Wang, S.-Y., Chong, J.: Resource allocation scheduling with deteriorating jobs and position-dependent workloads. J. Ind. Manag. Optim. 19(3), 1658–1669 (2023)

    Article  MathSciNet  Google Scholar 

  31. Jafari, A., Moslehi, G.: Scheduling linear deteriorating jobs to minimize the number of tardy jobs. J. Glob. Optim. 54, 389–404 (2012)

    Article  MathSciNet  Google Scholar 

  32. Bulfin, R.L., M’Hallah, R.: Minimizing the weighted number of tardy jobs on a two-machine flow shop. Comput. Oper. Res. 30(12), 1887–1900 (2003)

    Article  MathSciNet  Google Scholar 

  33. Lawler, E.L., Moore, J.M.: A functional equation and its application to resource allocation and sequencing problems. Manag. Sci. 16, 77–84 (1969)

    Article  Google Scholar 

  34. Karp, R.M.: Reducibility among combinatorial problems. In: Complexity of Computer Computations (Proc. Sympos., IBM Thomas J. Watson Res. Center, Yorktown Heights, N.Y., 1972), pp. 85–103. Plenum, New York (1972)

  35. Glover, F., Laguna, M.: Tabu Search. Kluwer, Norwell (1997)

    Book  Google Scholar 

  36. Kirkpatrick, S., Gelatt, C., Vecchi, M.: Optimization by simulated annealing. Science 220, 671–680 (1983)

    Article  MathSciNet  Google Scholar 

  37. Lai, K., Hsu, P.-H., Ting, P.-H., Wu, C.-C.: A truncated sum of processing-times-based learning model for a two-machine flowshop scheduling problem. Hum. Factors. Ergon. Manuf. Serv. Ind. 24, 152–160 (2014)

    Article  Google Scholar 

  38. Rudek, R.: The single processor total weighted completion time scheduling problem with the sum-of-processing-time based learning model. Inf. Sci. 199, 216–229 (2012)

    Article  MathSciNet  Google Scholar 

  39. Lu, Y.-Y., Li, G., Wu, Y.-B., Ji, P.: Optimal due-date assignment problem with learning effect and resource-dependent processing times. Optim. Lett. 8, 113–127 (2014)

    Article  MathSciNet  Google Scholar 

  40. Wang, J.-B., Liu, F., Wang, J.-J.: Research on m-machine flow shop scheduling with truncated learning effects. Int. Trans. Oper. Res. 26(3), 1135–1151 (2019)

    Article  MathSciNet  Google Scholar 

  41. Zhao, S.: Resource allocation flowshop scheduling with learning effect and slack due window assignment. J. Ind. Manag. Optim. 17(5), 2817–2835 (2021)

    Article  MathSciNet  Google Scholar 

  42. Zhao, S.: Scheduling jobs with general truncated learning effects including proportional setup times. Comput. Appl. Math. 41, 146 (2022)

    Article  MathSciNet  Google Scholar 

  43. Muştu, S., Eren, T.: The single machine scheduling problem with setup times under an extension of the general learning and forgetting effects. Optim. Lett. 15, 1327–1343 (2021)

    Article  MathSciNet  Google Scholar 

  44. Wang, X., Liu, W., Li, L., Zhao, P., Zhang, R.: Resource dependent scheduling with truncated learning effects. Math. Biosci. Eng. 19(6), 5957–5967 (2022)

    Article  MathSciNet  Google Scholar 

  45. Wang, J.-B., Zhang, L.-H., Lv, Z.-G., Lv, D.-Y., Geng, X.-N., Sun, X.: Heuristic and exact algorithms for single-machine scheduling problems with general truncated learning effects. Comput. Appl. Math. 41, 417 (2022)

    Article  MathSciNet  Google Scholar 

  46. Ji, M., Yao, D., Yang, Q., Cheng, T.C.E.: Single-machine common flow allowance scheduling with aging effect, resource allocation, and a rate-modifying activity. Int. Trans. Oper. Res. 22, 997–1015 (2015)

    Article  MathSciNet  Google Scholar 

  47. Zhu, Z., Liu, M., Chu, C., Li, J.: Multitasking scheduling with multiple rate-modifying activities. Int. Trans. Oper. Res. 26(5), 1956–1976 (2019)

    Article  MathSciNet  Google Scholar 

  48. Wu, W., Lv, D.-Y., Wang, J.-B.: Two due-date assignment scheduling with location-dependent weights and a deteriorating maintenance activity. Systems 11, 150 (2023)

    Article  Google Scholar 

Download references

Acknowledgements

Scientific Research Project of University in Anhui Province (Natural Science-2023 Year).

Author information

Authors and Affiliations

  1. Anqing Medical College, Anqing, Anhui, People’s Republic of China

    Yifu Feng

  2. School of Science, Shenyang Aerospace University, Shenyang, 110136, People’s Republic of China

    Xin-Na Geng, Dan-Yang Lv & Ji-Bo Wang

Authors
  1. Yifu Feng
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Xin-Na Geng
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Dan-Yang Lv
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Ji-Bo Wang
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Yifu Feng.

Additional information

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Rights and permissions

Springer Nature or its licensor (e.g. a society or other partner) holds exclusive rights to this article under a publishing agreement with the author(s) or other rightsholder(s); author self-archiving of the accepted manuscript version of this article is solely governed by the terms of such publishing agreement and applicable law.

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Feng, Y., Geng, XN., Lv, DY. et al. Scheduling jobs with general linear deterioration to minimize total weighted number of late jobs. Optim Lett 18, 1217–1235 (2024). https://doi.org/10.1007/s11590-023-02039-z

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s11590-023-02039-z

Keywords

Search

Navigation