Operations Research Transactions >
2025 , Vol. 29 >Issue 1: 31 - 40
DOI: https://doi.org/10.15960/j.cnki.issn.1007-6093.2025.01.003
Single two-agent scheduling problems with slack due date to minimize the total weighted tardiness
Received date: 2021-07-13
Online published: 2025-03-08
Copyright
This paper studies the scheduling problems with two competing agents on a single machine to minimize the total weighted tardiness under slack due date, where the slack due date of the job is equal to its actual processing time plus a certain slack variable. It includes two models: the first model is to minimize the total weighted tardiness of the first agent under the condition that the total number of tardiness jobs of the second agent does not exceed a given value; the second model is to minimize the total weighted tardiness of the first agent that the total completion time of the second agent does not exceed a given value. The optimal properties are given by dynamic programming. The pseudo-polynomial time algorithm and its time complexity is presented. Finally, two experiment examples are given to illustrate the feasibility of the algorithm.
Tongxin CUI, Qian XIA, Xingong ZHANG . Single two-agent scheduling problems with slack due date to minimize the total weighted tardiness[J]. Operations Research Transactions, 2025 , 29(1) : 31 -40 . DOI: 10.15960/j.cnki.issn.1007-6093.2025.01.003
| 1 | Lawler E L . A/pseudopolynomial0algorithm for sequencing jobs to minimize total tardiness[J]. Annals of Discrete Mathematics, 1977, 1, 331- 342. |
| 2 | Potts C N , Van Wassenhove L N . A branch and bound algorithm for the total weighted tardiness problem[J]. Operations Research, 1985, 33 (2): 363- 377. |
| 3 | Cheng T C E , Ng C T , Yuan J J , et al. Single machine scheduling to minimize total weighted tardiness[J]. European Journal of Operational Research, 2005, 165 (2): 423- 443. |
| 4 | Yuan J J , Cheng T C E , Ng C T . NP-hardness of the single-variable-resource scheduling problem to minimize the total weighted completion time[J]. European Journal of Operational Research, 2007, 178 (2): 631- 633. |
| 5 | Lawler E L , Moore J M . A functional equation and its application to resource allocation and sequencing problems[J]. Management Science, 1969, 16 (1): 77- 84. |
| 6 | Yue Q , Wan G . Single machine SLK/DIF due window assignment problem with job-dependent linear deterioration effects[J]. Journal of the Operational Research Society, 2016, 67 (6): 872- 883. |
| 7 | Agnetis A , Mirchandani P B , Pacciarelli D , et al. Scheduling problems with two competing agents[J]. Operations Research, 2004, 52 (2): 229- 242. |
| 8 | Liu M , Wang S , Zheng F , et al. Algorithms for the joint multitasking scheduling and common due date assignment problem[J]. International Journal of Production Research, 2017, 55 (20): 6052- 6066. |
| 9 | Karhi S , Shabtay D . Single machine scheduling to minimise resource consumption cost with a bound on scheduling plus due date assignment penalties[J]. International Journal of Production Research, 2018, 56 (9): 3080- 3096. |
| 10 | Wang D , Yu Y , Qiu H , et al. Two-agent scheduling with linear resource-dependent processing times[J]. Naval Research Logistics, 2020, 67 (7): 573- 591. |
| 11 | 陈秋宏, 张新功. 带有固定区间的单机双代理可中断总误工问题[J]. 运筹学学报, 2019, 23 (1): 61- 71. |
| 12 | Yang Y J , Yin G Q , Wang C W , et al. Due date assignment and two-agent scheduling under multitasking environment[J]. Journal of Combinatorial Optimization, 2022, 44, 2207- 2223. |
| 13 | Agnetis A, Billaut J-C, Pinedo M, et al. Fifty years of research in scheduling–-theory and applications [J/OL]. (2025-02-07)[2025-02-21]. European Journal of Operational Research. https://www.sciencedirect.com/science/article/pii/S0377221725000773. |
| 14 | Pinedo M L . Scheduling Theory, Algorithms and Systems[M]. New York: Springer, 2016. |
/
| 〈 |
|
〉 |
