基于松弛工期的总加权误工单机双代理排序问题

doi:10.15960/j.cnki.issn.1007-6093.2025.01.003

运筹学学报（中英文） ›› 2025, Vol. 29 ›› Issue (1): 31-40.doi: 10.15960/j.cnki.issn.1007-6093.2025.01.003

基于松弛工期的总加权误工单机双代理排序问题

崔同欣¹, 夏倩¹, 张新功¹^,*()

1. 重庆师范大学数学科学学院, 重庆 401331

收稿日期:2021-07-13 出版日期:2025-03-15 发布日期:2025-03-08
通讯作者: 张新功 E-mail:zhangxingong@cqnu.edu.cn
基金资助:
国家自然科学基金重大项目(11991022);国家自然科学基金面上项目(11971443);重庆市教委重点项目(KJZD-K202000501);重庆市科委项目(cstc2021jcyj-msxmX0229);重庆市教委研究生教改重点项目(YJG182019);重庆市自然科学基金创新发展联合基金项目(CSTB2023NSCQ-LZX0005)

Single two-agent scheduling problems with slack due date to minimize the total weighted tardiness

Tongxin CUI¹, Qian XIA¹, Xingong ZHANG¹^,*()

1. School of Mathematical Sciences, Chongqing Normal University, Chongqing 401331, China

Received:2021-07-13 Online:2025-03-15 Published:2025-03-08
Contact: Xingong ZHANG E-mail:zhangxingong@cqnu.edu.cn

摘要/Abstract

摘要：

本文研究了松弛工期下与总加权误工相关的单机双代理排序问题, 这里工件的松弛工期等于工件的加工时间加上某个松弛变量。涉及的两个模型分别为: 模型一是在第二个代理的误工工件个数不超过一个给定值的前提下, 使得第一个代理的总权误工最小; 模型二是在第二个代理的总完工时间不超过一个给定值的前提下, 使得第一个代理的总权误工最小。利用动态规划的方法对于两类问题分别给出了最优性质、拟多项式时间算法、以及时间复杂度分析, 并用算例实验来说明了算法的可行性。

关键词: 排序, 双代理, 总权误工, 动态规划算法

Abstract:

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.

Key words: scheduling, two-agent, total weighted tardiness, dynamical programming algorithm

中图分类号:

O223

崔同欣, 夏倩, 张新功. 基于松弛工期的总加权误工单机双代理排序问题[J]. 运筹学学报（中英文）, 2025, 29(1): 31-40.

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.

图/表 4

表1

表2

表3

表4

参考文献 14

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. doi: 10.1287/opre.33.2.363
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. doi: 10.1016/j.ejor.2004.04.013
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. doi: 10.1016/j.ejor.2006.02.014
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. doi: 10.1287/mnsc.16.1.77
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. doi: 10.1057/jors.2015.107
7	Agnetis A , Mirchandani P B , Pacciarelli D , et al. Scheduling problems with two competing agents[J]. Operations Research, 2004, 52 (2): 229- 242. doi: 10.1287/opre.1030.0092
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. doi: 10.1080/00207543.2017.1321804
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. doi: 10.1080/00207543.2017.1400708
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. doi: 10.1002/nav.21936
11	陈秋宏, 张新功. 带有固定区间的单机双代理可中断总误工问题[J]. 运筹学学报, 2019, 23 (1): 61- 71. doi: 10.15960/j.cnki.issn.1007-6093.2019.01.007
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. doi: 10.1007/s10878-020-00600-5
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.

符号	意义
$ y $	表示当前已经加工工件个数之和, $ y=i+j $
$ t $	表示当前已经加工的$ A $代理中的工件和$ B $代理的非误工工件的加工时间之和
$ x $	表示当前已经加工的$ B $代理的非误工的工件个数
$ e $	表示当前已经加工的$ B $代理的误工工件个数

$ J_{j}^{A} $	$ J_{1}^{A} $	$ J_{2}^{A} $	$ J_{3}^{A} $	$ J_{j}^{B} $	$ J_{1}^{B} $	$ J_{2}^{B} $
$ w_{j}^{A} $	1	2	3	$ p_{j}^{B} $	1	2
$ p_{j}^{A} $	3	4	2	$ d_{j}^{B} $	2	5

符号	意义
$ y $	表示当前已经加工工件个数之和, $ y=i+j $
$ t $	表示当前已经加工的$ A $代理和$ B $代理的工件的加工时间之和
$ T_j $	表示当前已经加工的$ A $代理的误工
$ H_i $	表示当前已经加工的$ B $代理工件的完工时间之和

$ J_{j}^{A} $	$ J_{1}^{A} $	$ J_{2}^{A} $	$ J_{3}^{A} $
$ w_{j}^{A} $	1	2	3
$ p_{j}^{A} $	3	4	2

[1]	杜诗翩, 顾满占. 带机器维护的最小化总误工数期望的随机排序问题研究[J]. 运筹学学报（中英文）, 2025, 29(1): 142-158.
[2]	李文杰, 杜智慧, 苏孟龙. 加工时间与运输时间具有一致性的单机NDP约束在线排序问题研究[J]. 运筹学学报（中英文）, 2024, 28(4): 18-28.
[3]	葛晴, 录岭法, 原晋江, 张利齐. 单机上一个与总完工时间及最大完工时间相关的工件可拒绝的ND双代理排序问题[J]. 运筹学学报（中英文）, 2024, 28(4): 66-74.
[4]	焦成文. 具有线性前瞻区间的单机平行批在线排序[J]. 运筹学学报（中英文）, 2024, 28(4): 111-116.
[5]	徐娟年, 马冉, 韩雯雯, 张玉忠. 工件权重带限制的最小化最大加权完工时间的单机在线排序问题[J]. 运筹学学报（中英文）, 2024, 28(2): 71-80.
[6]	高洁, 邹娟, 隋玉康, 张玉忠. 带有退化维护活动和工件可拒绝的非同类机排序问题[J]. 运筹学学报, 2023, 27(3): 137-149.
[7]	龚铭炀, 谈之奕, 严羽洁. 两台同类机排序问题SPT算法的最坏情况比[J]. 运筹学学报, 2022, 26(3): 92-108.
[8]	成夏炎, 何滢, 赵聪聪, 李荣珩. 两台自私型机器上自私工件排序的PoA紧界[J]. 运筹学学报, 2022, 26(3): 109-119.
[9]	王冬, 李刚刚, 罗文昌. 工件具有任意尺寸的混合分批平行机排序问题的近似算法[J]. 运筹学学报, 2022, 26(3): 133-142.
[10]	周萍, 季敏, 蒋义伟. 极大化提前完工总量平行机排序问题的LPT算法[J]. 运筹学学报, 2022, 26(3): 151-156.
[11]	李文杰, 李钰晶, 刘海玲. 工件的释放时间和加工时间具有一致性的单机在线排序问题研究[J]. 运筹学学报, 2022, 26(2): 55-63.
[12]	毕春燕, 万龙, 罗文昌. 工件有到达时间及可拒绝下的同类平行机排序问题的近似算法[J]. 运筹学学报, 2022, 26(2): 73-82.
[13]	王利博, 李文华, 余丹. 单机上带有可变前瞻区间的分批在线排序问题[J]. 运筹学学报, 2022, 26(1): 134-140.
[14]	余山杉, 金苗苗, 罗文昌. 工件延误和可拒绝下的单机重新排序问题的近似方案[J]. 运筹学学报, 2021, 25(2): 104-114.
[15]	姜晓燕, 帅天平. 两台恒速机上的MapReduce排序算法研究[J]. 运筹学学报, 2020, 24(3): 57-66.

基于松弛工期的总加权误工单机双代理排序问题

Single two-agent scheduling problems with slack due date to minimize the total weighted tardiness

RichHTML

PDF

可视化

摘要/Abstract

引用本文

使用本文

图/表 4

参考文献 14

相关文章 15

编辑推荐

Metrics

本文评价