This paper investigates a single-machine scheduling problem that integrates cumulative time-dependent learning effects with non-renewable resource allocation, where job processing times are controllable through resource investment. The actual processing time of each job is modeled as a nonlinear function of the allocated resource amount and the cumulative normal processing times of previously processed jobs, thereby reflecting proficiency gains in modern manufacturing environments. The objective is to minimize a weighted aggregate cost consisting of total weighted completion time and total resource consumption. By establishing convexity with respect to the resource variables, we derive an analytical optimal resource allocation policy for any fixed job sequence. This result transforms the original joint continuous-discrete optimization problem into an equivalent combinatorial sequencing problem. To solve the resulting problem, we develop an exact branch-and-bound (B&B) algorithm with a lower-bound scheme based on the monotonicity of the learning term. For larger instances, simulated annealing, tabu search, and genetic algorithms are developed to obtain high-quality feasible solutions within limited computational time. The computational results evaluate the pruning efficiency of the B&B algorithm and the stability of the proposed metaheuristics. The analysis also shows that, under strong learning effects, the classical WSPT rule is no longer universally dominant; in some cases, SPT-type sequences may be preferable. These findings provide useful insights for scheduling decisions in labor-intensive and high-precision manufacturing environments.
Citation: Xinfeng Wu, Lin Lin, Ji-Bo Wang. Total weighted completion time scheduling under resource allocation and time-dependent learning effects[J]. Journal of Industrial and Management Optimization, 2026, 22(7): 3219-3251. doi: 10.3934/jimo.2026118
This paper investigates a single-machine scheduling problem that integrates cumulative time-dependent learning effects with non-renewable resource allocation, where job processing times are controllable through resource investment. The actual processing time of each job is modeled as a nonlinear function of the allocated resource amount and the cumulative normal processing times of previously processed jobs, thereby reflecting proficiency gains in modern manufacturing environments. The objective is to minimize a weighted aggregate cost consisting of total weighted completion time and total resource consumption. By establishing convexity with respect to the resource variables, we derive an analytical optimal resource allocation policy for any fixed job sequence. This result transforms the original joint continuous-discrete optimization problem into an equivalent combinatorial sequencing problem. To solve the resulting problem, we develop an exact branch-and-bound (B&B) algorithm with a lower-bound scheme based on the monotonicity of the learning term. For larger instances, simulated annealing, tabu search, and genetic algorithms are developed to obtain high-quality feasible solutions within limited computational time. The computational results evaluate the pruning efficiency of the B&B algorithm and the stability of the proposed metaheuristics. The analysis also shows that, under strong learning effects, the classical WSPT rule is no longer universally dominant; in some cases, SPT-type sequences may be preferable. These findings provide useful insights for scheduling decisions in labor-intensive and high-precision manufacturing environments.
| [1] | M. L. Pinedo, Scheduling-Theory, Algorithms, and Systems, Vol. 29, Springer, 2012. https://doi.org/10.1007/978-1-4614-2361-4 |
| [2] | D. R. Karger, C. Stein, J. Wein, Scheduling algorithms, Handbook of Algorithms and Theory of Computation, (1999). |
| [3] |
R. G. Vickson, Choosing the job sequence and processing times to minimize total processing plus flow cost on a single machine, Oper. Res., 28 (1980), 1155–1167. https://doi.org/10.1287/opre.28.5.1155 doi: 10.1287/opre.28.5.1155
|
| [4] |
D. Shabtay, G. Steiner, A survey of scheduling with controllable processing times, Discret. Appl. Math., 155 (2007), 1643–1666. https://doi.org/10.1016/j.dam.2007.02.003 doi: 10.1016/j.dam.2007.02.003
|
| [5] |
N. Yin, X. Y. Wang, Single-machine scheduling with controllable processing times and learning effect, Int. J. Adv. Manuf. Technol., 54 (2011), 743–748. https://doi.org/10.1007/s00170-010-2973-z doi: 10.1007/s00170-010-2973-z
|
| [6] |
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://dx.doi.org/10.1142/S0217595923500264 doi: 10.1142/S0217595923500264
|
| [7] |
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
|
| [8] |
M. A. Abdeljaouad, Z. Bahroun, N. E. H. Saadani, R. Sheiko, K. Al-Assaf, A resource-constrained optimization model for parallel machine scheduling with constraint programming, Decis. Anal. J., 15 (2025), 100585. https://doi.org/10.1016/j.dajour.2025.100585 doi: 10.1016/j.dajour.2025.100585
|
| [9] |
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
|
| [10] |
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
|
| [11] |
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
|
| [12] |
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
|
| [13] |
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
|
| [14] |
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
|
| [15] |
S. Kovalev, I. Chalamon, A. Becuwe, Single machine scheduling with resource constraints: Equivalence to two-machine flow-shop scheduling for regular objectives, J. Oper. Res. Soc., 75 (2024), 1343–1346. https://doi.org/10.1080/01605682.2023.2244529 doi: 10.1080/01605682.2023.2244529
|
| [16] |
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
|
| [17] |
D. Shabtay, Coordinating scheduling and resource-allocation decisions in a proportionate flow-shop scheduling environment, Optim. Lett., 20 (2026), 727–745. https://doi.org/10.1007/s11590-025-02274-6 doi: 10.1007/s11590-025-02274-6
|
| [18] |
D. Biskup, Single-machine scheduling with learning considerations, Eur. J. Oper. Res., 115 (1999), 173–178. https://doi.org/10.1016/S0377-2217(98)00246-X doi: 10.1016/S0377-2217(98)00246-X
|
| [19] |
D. Biskup, A state-of-the-art review on scheduling with learning effects, Eur. J. Oper. Res., 188 (2008), 315–329. https://doi.org/10.1016/j.ejor.2007.05.040 doi: 10.1016/j.ejor.2007.05.040
|
| [20] |
C. C. Wu, W. C. Lin, X. Zhang, I. H. Chung, T. H. Yang, K. Lai, Tardiness minimisation for a customer order scheduling problem with sum-of-processing-time-based learning effect, J. Oper. Res. Soc., 70 (2019), 487–501. https://doi.org/10.1080/01605682.2018.1447249 doi: 10.1080/01605682.2018.1447249
|
| [21] |
G. Mosheiov, Scheduling jobs under simple linear deterioration, Comput. Oper. Res., 21 (1994), 653–659. https://doi.org/10.1016/0305-0548(94)90080-9 doi: 10.1016/0305-0548(94)90080-9
|
| [22] |
D. Oron, Single machine scheduling with simple linear deterioration to minimize total absolute deviation of completion times, Comput. Oper. Res., 35 (2008), 2071–2078. https://doi.org/10.1016/j.cor.2006.10.010 doi: 10.1016/j.cor.2006.10.010
|
| [23] |
W. C. Lee, C. C. Wu, Y. H. Chung, Scheduling deteriorating jobs on a single machine with release times, Comput. Ind. Eng., 54 (2008), 441–452. https://doi.org/10.1016/j.cie.2007.08.006 doi: 10.1016/j.cie.2007.08.006
|
| [24] | 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 |
| [25] |
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
|
| [26] |
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
|
| [27] |
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
|
| [28] |
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
|
| [29] | S. Gawiejnowicz, Time-dependent scheduling, Berlin: Springer Science & Business Media, 2008. https://doi.org/10.1007/978-3-540-69446-5 |
| [30] | S. Gawiejnowicz, Models and algorithms of time-dependent scheduling, Vol. 2, Springer, 2020. https://doi.org/10.1007/978-3-662-59362-2 |
| [31] |
S. Gawiejnowicz, A review of four decades of time-dependent scheduling: Main results, new topics, and open problems, J. Sched., 23 (2020), 3–47. https://doi.org/10.1007/s10951-019-00630-w doi: 10.1007/s10951-019-00630-w
|
| [32] |
Y. Yin, T. C. E. Cheng, C. C. Wu, Scheduling with time-dependent processing times, Math. Probl. Eng., 2015 (2015), 704543. http://doi.org/10.1155/2015/367585 doi: 10.1155/2015/367585
|
| [33] |
T. C. E. Cheng, G. Wang, Single machine scheduling with learning effect considerations, Ann. Oper. Res., 98 (2000), 273–290. https://doi.org/10.1023/A:1019216726076 doi: 10.1023/A:1019216726076
|
| [34] |
J. B. Wang, C. T. Ng, T. C. E. Cheng, L. L. Liu, Single-machine scheduling with a time-dependent learning effect, Int. J. Prod. Econ., 111 (2008), 802–811. https://doi.org/10.1016/j.ijpe.2007.03.013 doi: 10.1016/j.ijpe.2007.03.013
|
| [35] |
W. H. Kuo, D. L. Yang, Single-machine group scheduling with a time-dependent learning effect, Comput. Oper. Res., 33 (2006), 2099–2112. https://doi.org/10.1016/j.cor.2004.11.024 doi: 10.1016/j.cor.2004.11.024
|
| [36] |
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
|
| [37] |
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
|
| [38] |
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
|
| [39] | 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. http://doi.org/10.1142/S0217595926500016 |
| [40] | T. Liu, X. Y. Sun, L. H. Zhang, Y. H. Fan, Coordinating single-machine scheduling with the general linear deterioration function and maintenance activity: minimizing the makespan, Eng. Optim., (2026). https://doi.org/10.1080/0305215X.2026.2645254 |
| [41] |
Y. C. Wang, J. B. Wang, Study on convex resource allocation scheduling with a time-dependent learning effect, Mathematics, 11 (2023), 3179. https://doi.org/10.3390/math11143179 doi: 10.3390/math11143179
|
| [42] |
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
|
| [43] |
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
|
| [44] |
N. Ren, D. Y. Lv, J. B. Wang, X. Y. Wang, Solution algorithms for single-machine scheduling with learning effects and exponential past-sequence-dependent delivery times, J. Ind. Manag. Optim., 19 (2023), 8429–8450. https://doi.org/10.3934/jimo.2023045 doi: 10.3934/jimo.2023045
|
| [45] |
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
|
| [46] |
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
|
| [47] |
J. Hartmanis, Computers and intractability: a guide to the theory of NP-completeness, SIAM Rev., 24 (1982), 90. https://doi.org/10.1137/1024022 doi: 10.1137/1024022
|
| [48] |
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
|
| [49] |
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
|
| [50] |
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
|
| [51] |
D. Shabtay, D. Oron, Proportionate flow-shop scheduling with rejection, J. Oper. Res. Soc., 67 (2016), 752–769. https://doi.org/10.1057/jors.2015.95 doi: 10.1057/jors.2015.95
|
| [52] | L. Pan, X. Y. Sun, X. N. Geng, Dynamic programming for proportionate flow-shop scheduling with due-date assignment, Asia-Pacific J. Oper. Res., (2026), 2650002. https://doi.org/10.1142/S0217595926500028 |
| [53] |
R. Jin, W. Tong, Y. Xu, T. Dong, Two-stage flexible flow shop scheduling in GPU systems, J. Oper. Res. Soc., 77 (2026), 793–804. https://doi.org/10.1080/01605682.2025.2504435 doi: 10.1080/01605682.2025.2504435
|
| [54] |
J. Y. Wang, Minimizing the total weighted tardiness of overlapping jobs on parallel machines with a learning effect, J. Oper. Res. Soc., 71 (2020), 910–927. https://doi.org/10.1080/01605682.2019.1590511 doi: 10.1080/01605682.2019.1590511
|
| [55] |
K. Ben Abdellafou, K. Zidi, W. Ghaban, Scheduling intrees with unavailability constraints on two parallel machines, Symmetry, 18 (2026), 103. https://doi.org/10.3390/sym18010103 doi: 10.3390/sym18010103
|
| [56] |
C. Hu, Y. Zhai, S. Lu, X. Liu, Parallel machine group scheduling with time-dependent setup time and combined effects of deterioration and learning, Memet. Comput., 18 (2026), 8. https://doi.org/10.1007/s12293-025-00487-x doi: 10.1007/s12293-025-00487-x
|
Figures(2) / Tables(9)
Xinfeng Wu, Lin Lin, Ji-Bo Wang. Total weighted completion time scheduling under resource allocation and time-dependent learning effects[J]. Journal of Industrial and Management Optimization, 2026, 22(7): 3219-3251. doi: 10.3934/jimo.2026118
DownLoad: