Search Advanced

Journal of Industrial and Management Optimization

2026, Volume 22, Issue 8: 3968-3998. doi: 10.3934/jimo.2026141
Previous Article Next Article
Research article Special Issues

Solution algorithms for minimizing total weighted completion time scheduling with release times and time-dependent deterioration effects

  • 1.
    School of Mechatronics Engineering, Shenyang Aerospace University, Shenyang 110136, P.R. China
  • 2.
    Key Laboratory of Rapid Development & Manufacturing Technology for Aircraft (Shenyang Aerospace University), Ministry of Education, Shenyang 110136, P.R. China
  • 3.
    School of Science, Shenyang Aerospace University, Shenyang 110136, P. R. China
  • Published: 24 July 2026

  • 90B35

  • This article addresses a single-machine scheduling problem with release times and deterioration effects, where the processing time of a job is a non-decreasing function of its start time, and all jobs share the same deterioration rate. The objective was to determine an optimal schedule that minimizes the total weighted completion time. Since the problem is NP-hard, several heuristic algorithms were proposed. Furthermore, several dominance properties were established, along with an upper bound and a lower bound, after which a branch-and-bound (bb) algorithm was developed. Experimental results were presented to compare the performance of the heuristic algorithms with that of the branch-and-bound algorithm.

    Citation: Li-Han Zhang, Xiao-Yuan Wang, Na Yin, Zheng-Guo Lv, Ji-Bo Wang. Solution algorithms for minimizing total weighted completion time scheduling with release times and time-dependent deterioration effects[J]. Journal of Industrial and Management Optimization, 2026, 22(8): 3968-3998. doi: 10.3934/jimo.2026141

    Related Papers:

  • This article addresses a single-machine scheduling problem with release times and deterioration effects, where the processing time of a job is a non-decreasing function of its start time, and all jobs share the same deterioration rate. The objective was to determine an optimal schedule that minimizes the total weighted completion time. Since the problem is NP-hard, several heuristic algorithms were proposed. Furthermore, several dominance properties were established, along with an upper bound and a lower bound, after which a branch-and-bound (bb) algorithm was developed. Experimental results were presented to compare the performance of the heuristic algorithms with that of the branch-and-bound algorithm.



    加载中


    [1] G. Mosheiov, $\wedge$-shaped policies to schedule deteriorating jobs, J. Oper. Res. Soc., 47 (1996), 1184–1191. https://doi.org/10.1057/jors.1996.146 doi: 10.1057/jors.1996.146
    [2] A. Kononov, Single machine scheduling problems with processing times proportional to an arbitrary function, Discret. Analysis Oper. Res. 5 (1998), 17–37 (in Russian). http://old.math.nsc.ru/publishing/DAOR/content/1998/03/17.pdf
    [3] S. Browne, U. Yechiali, Scheduling deteriorating jobs on a single processor. Oper. Res. 38 (1990), 495–498. https://doi.org/10.1287/opre.38.3.495 doi: 10.1287/opre.38.3.495
    [4] S. Gawiejnowicz, Models and algorithms of time-dependent scheduling, Vol. 2, Springer, 2020. https://doi.org/10.1007/978-3-662-59362-2
    [5] T. C. E. Cheng, L. Kang, C. T. Ng, Due-date assignment and single machine scheduling with deteriorating jobs, J. Oper. Res. Soc., 55 (2004), 198–203. https://doi.org/10.1057/palgrave.jors.2601681 doi: 10.1057/palgrave.jors.2601681
    [6] V. A. Strusevich, K. Rustogi, Scheduling with Time-Changing Effects and Rate-Modifying Activities. Springer, Berlin-Heidelberg (2017). https://link.springer.com/book/10.1007/978-3-319-39574-6
    [7] J. Labetoulle, E. L. Lawler, J. K. Lenstra, A. H. G. R. Kan, Preemptive scheduling of uniform machines subject to release dates, In: W. R. Pulleyblank, (ed.) Progress in Combinatorial Optimization, 245–261. Academic Press, New York (1984). https://doi.org/10.1016/B978-0-12-566780-7.50020-9
    [8] J. K. Lenstra, A. H. G. R. Kan, P. Brucker, Complexity of machine scheduling problems, Ann. Discret. Math., 1 (1977), 343–362. https://doi.org/10.1016/S0167-5060(08)70743-X doi: 10.1016/S0167-5060(08)70743-X
    [9] C. X. Miao, Complexity of scheduling with proportional deterioration and release dates, Iran. J. Sci. Tech., Trans. A: Sci., 42 (2018), 1337–1342. https://doi.org/10.1007/s40995-017-0466-8 doi: 10.1007/s40995-017-0466-8
    [10] Z. G. Lv, L. H. Zhang, X. Y. Wang, J. B. Wang, Single machine scheduling proportionally deteriorating jobs with ready times subject to the total weighted completion time minimization, Mathematics 12(2024), 610. https://doi.org/10.3390/math12040610 doi: 10.3390/math12040610
    [11] M. Atsmony, G. Mosheiov, Minimizing total completion time with linear deterioration: A new lower bound, Comput. Ind. Eng., 163 (2022), 107867. https://doi.org/10.1016/j.cie.2021.107867 doi: 10.1016/j.cie.2021.107867
    [12] Q. F. Kong, C. M. Wei, J. B. Wang, Minmax delivery completion time scheduling with delivery times and deteriorating jobs, Comput. Appl. Math., 45 (2026), 276. https://doi.org/10.1007/s40314-026-03684-7 doi: 10.1007/s40314-026-03684-7
    [13] H. He, Y. Hu, W. W. Liu, Scheduling with deteriorating effect and maintenance activities under parallel processors, Eng. Optim., 53 (2021), 2070–2087. https://doi.org/10.1080/0305215X.2020.1844194 doi: 10.1080/0305215X.2020.1844194
    [14] W. Liu, X. Wang, L. Li, P. Zhao, A maintenance activity scheduling with time-and-position dependent deteriorating effects, Math. Biosci. Eng., 19 (2022), 11756–11767. https://doi.org/10.3934/mbe.2022547 doi: 10.3934/mbe.2022547
    [15] X. Sun, X. N. Geng, Single-machine scheduling with deteriorating effects and machine maintenance, Int. J. Prod. Res., 57 (2019), 3186–3199. https://doi.org/10.1080/00207543.2019.1566675 doi: 10.1080/00207543.2019.1566675
    [16] J. Qian, Y. Zhan, The due window assignment problems with deteriorating job and delivery time, Mathematics, 10 (2022), 1672. https://doi.org/10.3390/math10101672 doi: 10.3390/math10101672
    [17] D. Y. Lv, J. Xue, J. B. Wang, Minmax common due-window assignment scheduling with deteriorating jobs, J. Oper. Res. Soc. China, 12 (2024), 681–693. https://doi.org/10.1007/s40305-023-00511-2 doi: 10.1007/s40305-023-00511-2
    [18] L. H. Zhang, X. N. Geng, J. Xue, J. B. Wang, Single machine slack due window assignment and deteriorating jobs, J. Ind. Manag. Optim., 20 (2024), 1593–1614. https://doi.org/10.3934/jimo.2023136 doi: 10.3934/jimo.2023136
    [19] F. Liu, J. Yang, Y. Y. Lu, Solution algorithms for single-machine group scheduling with ready times and deteriorating jobs, Eng. Optim., 51 (2019), 862–874. https://doi.org/10.1080/0305215X.2018.1500562 doi: 10.1080/0305215X.2018.1500562
    [20] N. Yin, M. Gao, Single-machine group scheduling with general linear deterioration and truncated learning effects, Comput. Appl. Math., 43 (2024), 386. https://doi.org/10.1007/s40314-024-02881-6 doi: 10.1007/s40314-024-02881-6
    [21] N. Yin, H. He, Y. Zhao, Y. Chang, N. Wang, Integrating group setup time deterioration effects and job processing time learning effects with group technology in single-machine green scheduling, Axioms, 14 (2025), 480. https://doi.org/10.3390/axioms14070480 doi: 10.3390/axioms14070480
    [22] D. Y. Lv, J. B. Wang, No-idle flow shop scheduling with deteriorating jobs and common due date under dominating machines, Asia-Pacific J. Oper. Res., 41 (2024), 2450003. https://doi.org/10.1142/S0217595924500039 doi: 10.1142/S0217595924500039
    [23] D. Y. Lv, J. B. Wang, Research on two-machine flow shop scheduling problem with release dates and truncated learning effects, Eng. Optim., 57 (2025), 1828–1848. https://doi.org/10.1080/0305215X.2024.2372633 doi: 10.1080/0305215X.2024.2372633
    [24] C. X. Miao, J. Zou, Parallel-machine scheduling with time-dependent and machine availability constraints, Math. Prob. Eng., 2015 (2015), 956158. https://doi.org/10.1155/2015/956158 doi: 10.1155/2015/956158
    [25] D. W. Li, X. W. Lu, Parallel-batch scheduling with deterioration and rejection on a single machine, Appl. Math. J. Chinese Univ., 35 (2020), 141–156. https://doi.org/10.1007/s11766-020-3624-2 doi: 10.1007/s11766-020-3624-2
    [26] D. Y. Bai, H. Xue, L. Wang, C. C. Wu, W. C. Lin, D. H. Abdulkadir, Effective algorithms for single-machine learning-effect scheduling to minimize completion-time-based criteria with release dates, Expert Syst. Appl., 156 (2020), 113445. https://doi.org/10.1016/j.eswa.2020.113445 doi: 10.1016/j.eswa.2020.113445
    [27] J. Qian, H. X. Lin, Y. F. Kong, Y. S. Wang, Tri-criteria single machine scheduling model with release times and learning factor, Appl. Math. Comput. 387 (2020), 124543. https://doi.org/10.1016/j.amc.2019.06.057 doi: 10.1016/j.amc.2019.06.057
    [28] X. Sun, X. N. Geng, F. Liu, Flow shop scheduling with general position weighted learning effects to minimise total weighted completion time, J. Oper. Res. Soc., 72 (2021), 2674–2689. https://doi.org/10.1080/01605682.2020.1806746 doi: 10.1080/01605682.2020.1806746
    [29] L. Y. Wang, Due-window assignment scheduling problems with position-dependent weights, truncated learning effects and past-sequence-dependent setup-times, Symmetry, 18 (2026), 396. https://doi.org/10.3390/sym18030396 doi: 10.3390/sym18030396
    [30] H. R. Song, J. K. Yang, J. B. Wang, Study on multiple due-windows assignment scheduling with learning and deteriorating effects, Asia-Pacific J. Oper. Res., (2026), 2650001. https://doi.org/10.1142/S0217595926500016 doi: 10.1142/S0217595926500016
    [31] Y. Y. Lu, M. H. Li, A unified analysis for single-machine scheduling with resource allocations, learning and deteriorating effects simultaneously, Comput. Appl. Math., 45 (2026), 388. https://doi.org/10.1007/s40314-026-03784-4 doi: 10.1007/s40314-026-03784-4
    [32] J. B. Wang, Y. C. Wang, C. Wan, D. Y. Lv, L. Zhang, Controllable processing time scheduling with total weighted completion time objective and deteriorating jobs, Asia-Pacific J. Oper. Res., 41 (2024), 2350026. http://doi.org/10.1142/S0217595923500264 doi: 10.1142/S0217595923500264
    [33] L. H. Zhang, M. H. Li, L. Lin, Study on controllable processing time and minmax group scheduling with common due-window assignment, Symmetry, 18 (2026), 358. https://doi.org/10.3390/sym18020358 doi: 10.3390/sym18020358
    [34] X. F. Wu, L. Lin, J. B. Wang, Total weighted completion time scheduling cost under resource-allocation and time-dependent learning effects, J. Ind. Manag. Optim., 22 (2026), 3219–3251. https://doi.org/10.3934/jimo.2026118 doi: 10.3934/jimo.2026118
    [35] C. C. Wu, T. H. Yang, X. G. Zhang, C. C. Kang, I. H. Chung, W. C. Lin, Using heuristic and iterative greedy algorithms for the total weighted completion time order scheduling with release times, Swarm Evol. Comput., 44 (2019), 913–926. https://doi.org/10.1016/j.swevo.2018.10.003 doi: 10.1016/j.swevo.2018.10.003
    [36] D. Bai, Y. Li, H. Xue, J. Yang, R. Chen, C. C. Wu, et al., A bi-agent single-processor scheduling to minimize the sum of maximum lateness with release dates, J. Oper. Res. Soc., 77 (2026), 1049–1067. https://doi.org/10.1080/01605682.2025.2516106 doi: 10.1080/01605682.2025.2516106
    [37] R. L. Graham, E. L. Lawler, J. K. Lenstra, A. H. G. Rinnooy Kan, Optimization and approximation in deterministic sequencing and scheduling: a survey, Ann. Discret. Math., 5 (1979), 287–326. https://doi.org/10.1016/s0167-5060(08)70356-x doi: 10.1016/s0167-5060(08)70356-x
    [38] A. Bachman, A. Janiak, M. Y. Kovalyov, Minimizing the total weighted completion time of deteriorating jobs, Inform. Process. Lett. 81 (2002), 81–84. https://doi.org/10.1016/S0020-0190(01)00196-X doi: 10.1016/S0020-0190(01)00196-X
    [39] J. Pei, X. M. Wang, W. J. Fan, P. M. Pardalos, X. B. Liu, Scheduling step-deteriorating jobs on bounded parallel-batching machines to maximise the total net revenue, J. Oper. Res. Soc., 70 (2019), 1830–1847. https://doi.org/10.1080/01605682.2018.1464428 doi: 10.1080/01605682.2018.1464428
    [40] T. C. E. Cheng, S. A. Kravchenko, B. M. T. Lin, Scheduling step-deteriorating jobs to minimize the total completion time. Comput. Ind. Eng., 144 (2020), 106329. https://doi.org/10.1016/j.cie.2020.106329 doi: 10.1016/j.cie.2020.106329
    [41] H. J. Kim, E. S. Kim, J. H. Lee, Scheduling of step-improving jobs with an identical improving rate, J. Oper. Res. Soc., 73 (2022), 1127–1136. https://doi.org/10.1080/01605682.2021.1886616 doi: 10.1080/01605682.2021.1886616
    [42] C. C. Wu, W. C. Lin, A. Azzouz, J. Y. Xu, Y. L. Chiu, Y. W. Tsai, P. Y. Shen, A bicriterion single-machine scheduling problem with step-improving processing times, Comput. Ind. Eng., 171 (2022), 108469. https://doi.org/10.1016/j.cie.2022.108469 doi: 10.1016/j.cie.2022.108469
    [43] C. X. Miao, J. X. Song, Y. Z. Zhang, Single-machine time-dependent scheduling with proportional and delivery times, Asia-Pacific J. Oper. Res., 40 (2023), 2240015. http://doi.org/10.1142/S0217595922400152 doi: 10.1142/S0217595922400152
    [44] R. R. Mao, D. Y. Lv, N. Ren, J. B. Wang, Supply chain scheduling with deteriorating jobs and delivery times, J. Appl. Math. Comput., 70 (2026), 2285–2312. https://doi.org/10.1007/s12190-024-02052-0 doi: 10.1007/s12190-024-02052-0
    [45] Y. Y. Lu, S. Zhang, J. Y. Tao, Earliness-tardiness scheduling with delivery times and deteriorating jobs, Asia-Pacific J. Oper. Res., 42 (2025), 2450009. https://doi.org/10.1142/S021759592450009X doi: 10.1142/S021759592450009X
    [46] M. H. Li, D. Y. Lv, Z. G. Lv, L. H. Zhang, J. B. Wang, A two-agent resource allocation scheduling problem with slack due-date assignment and general deterioration function, Comput. Appl. Math., 43 (2024), 229. https://doi.org/10.1007/s40314-024-02753-z doi: 10.1007/s40314-024-02753-z
    [47] X. Y. Wang, W. G. Liu, Delivery scheduling with variable processing times and due date assignments, Bull. Malays. Math. Sci. Soc., 48 (2025), 76. https://doi.org/10.1007/s40840-025-01856-y doi: 10.1007/s40840-025-01856-y
    [48] Y. Sun, Y. Y. Lu, D. Y. Lv, J. B. Wang, Single-machine setup time scheduling with general linear deterioration subject to makespan and total completion time minimization, J. Oper. Res. Soc., (2025). https://doi.org/10.1080/01605682.2025.2560511
    [49] Z. W. Sun, D. Y. Lv, P. Ji, J. B. Wang, Minimizing total completion time scheduling problem with ready times and linear deterioration functions of processing times, J. Appl. Math. Comput., 72 (2026), 42. https://doi.org/10.1007/s12190-025-02694-8 doi: 10.1007/s12190-025-02694-8
    [50] G. H. Hardy, J. E. Littlewood, G. Polya, Inequalities, Cambridge University Press, 1988. https://doi.org/10.1017/s0025557200143451 doi: 10.1017/s0025557200143451
    [51] X. Y. Wang, W. G. Liu, Single machine group scheduling jobs with resource allocations subject to unrestricted due date assignments, J. Appl. Math. Comput., 70 (2024), 6283–6308. https://doi.org/10.1007/s12190-024-02216-y doi: 10.1007/s12190-024-02216-y
    [52] J. B. Wang, Z. W. Sun, M. Gao, Research on single-machine scheduling with due-window assignment and resource allocation under total resource consumption cost is bounded, J. Appl. Math. Comput., 71 (2025), 7905–7927. https://doi.org/10.1007/s12190-025-02599-6 doi: 10.1007/s12190-025-02599-6
    [53] M. Nawaz, J. E. E. Enscore, I. Ham, A heuristic algorithm for the $m$-machine, $n$-job flow-shop sequencing problem, Omega, 11 (1983), 91–95. https://doi.org/10.1016/0305-0483(83)90088-9 doi: 10.1016/0305-0483(83)90088-9
    [54] K. Chen, X. Y. Shi, D. L. Yao, T. C. E. Cheng, M. Ji, Parallel-machine scheduling with machine unavailability to maximize total early work, J. Oper. Res. Soc., (2025). https://doi.org/10.1080/01605682.2025.2565464
    [55] M. H. Li, D. Y. Lv, L. H. Zhang, J. B. Wang, Permutation flow shop scheduling with makespan objective and truncated learning effects, J. Appl. Math. Comput., 70 (2024), 2907–2939. https://doi.org/10.1007/s12190-024-02080-w doi: 10.1007/s12190-024-02080-w
    [56] J. B. Wang, D. Y. Lv, C. Wan, Proportionate flow shop scheduling with job-dependent due windows and position-dependent weights, Asia-Pacific J. Oper. Res., 42 (2025), 2450011. https://doi.org/10.1142/S0217595924500118 doi: 10.1142/S0217595924500118
    [57] Y. Sun, D. Y. Lv, X. Huang, Properties for due window assignment scheduling on a two-machine no-wait proportionate flow shop with learning effects and resource allocation, J. Oper. Res. Soc., 77 (2026), 599–615. https://doi.org/10.1080/01605682.2025.2492817 doi: 10.1080/01605682.2025.2492817
    [58] A. Azerine, M. Boudhar, D. Rebaine, Minimising the makespan in a two-machine open shop scheduling with competing agents, J. Oper. Res. Soc., (2026). https://doi.org/10.1080/01605682.2026.2651218
    [59] L. F. Lin, J. Y. Wang, Strategic delay in job shop scheduling: non-zero start time optimisation under multi-constraint environments, J. Oper. Res. Soc., (2026). https://doi.org/10.1080/01605682.2026.2682267
    [60] L. R. Abreu, M. S. Nagano, Mixed-integer and constraint programming formulations for distributed open shop scheduling problem with makespan minimization, J. Oper. Res. Soc., (2026). https://doi.org/10.1080/01605682.2026.2682260
    [61] W. Liu, X. Wang, L. Li, W. Dai, Due-window assignment scheduling with job-rejection, truncated learning effects and setup times, J. Ind. Manag. Optim., 20 (2024), 313–324. https://doi.org/10.3934/jimo.2023079 doi: 10.3934/jimo.2023079
    [62] X. N. Geng, X. Sun, J. Wang, L. Pan, Scheduling on proportionate flow shop with job rejection and common due date assignment, Comput. Ind. Eng., 181 (2023), 109317. https://doi.org/10.1016/j.cie.2023.109317 doi: 10.1016/j.cie.2023.109317
    [63] X. N. Geng, X. Sun, J. Wang, B. Mor, Scheduling on proportionate flowshop with total late work and job rejection, Oper. Res., 25 (2025), 82. https://doi.org/10.1007/s12351-025-00951-z doi: 10.1007/s12351-025-00951-z
    [64] Y. Zhang, X. Sun, T. Liu, J. Y. Wang, X. N. Geng, Single-machine scheduling simultaneous consideration of resource allocations and exponential time-dependent learning effects, J. Oper. Res. Soc., 76 (2025), 528–540. https://doi.org/10.1080/01605682.2024.2371527 doi: 10.1080/01605682.2024.2371527
    [65] D. Y. Lv, J. B. Wang, Single-machine group technology scheduling with resource allocation and slack due window assignment including minmax criterion, J. Oper. Res. Soc., 76 (2025), 1696–1712. https://doi.org/10.1080/01605682.2024.2430351 doi: 10.1080/01605682.2024.2430351
    [66] X. Huang, H. He, H. Bei, Y. Zhao, N. Wang, Y. Chang, Group-scheduling with simultaneous learning effects and convex resource allocations, Oper. Res. Perspect., 15 (2025), 100370. https://doi.org/10.1016/j.orp.2025.100370 doi: 10.1016/j.orp.2025.100370
    [67] L. H. Zhang, J. B. Wang, Resource allocation and minmax scheduling under group technology and different due-window assignments, Axioms, 14 (2025), 827. https://doi.org/10.3390/axioms14110827 doi: 10.3390/axioms14110827
    [68] L. H. Zhang, N. Yin, Study on single-machine group scheduling with convex resource allocations and different due-date assignments, Bull. Malays. Math. Sci. Soc., 49 (2026), 33. https://doi.org/10.1007/s40840-025-02031-z doi: 10.1007/s40840-025-02031-z
  • Reader Comments
  • © 2026 the Author(s), licensee AIMS Press. This is an open access article distributed under the terms of the Creative Commons Attribution License (http://creativecommons.org/licenses/by/4.0)
通讯作者: 陈斌, bchen63@163.com
  • 1. 

    沈阳化工大学材料科学与工程学院 沈阳 110142

  1. 本站搜索
  2. 百度学术搜索
  3. 万方数据库搜索
  4. CNKI搜索
Journal of Industrial and Management Optimization
1.4 3.4

Metrics

Article views(492) PDF downloads(26) Cited by(0)

Preview PDF
Download XML
Export Citation
Article outline

Figures and Tables

Figures(3)  /  Tables(16)

Other Articles By Authors

Related pages

Tools

/

DownLoad:  Full-Size Img  PowerPoint
Return
Return

Catalog