单机两代理串行分批排序问题的近似算法

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

运筹学学报（中英文） ›› 2025, Vol. 29 ›› Issue (2): 184-193.doi: 10.15960/j.cnki.issn.1007-6093.2025.02.014

单机两代理串行分批排序问题的近似算法

赵娣¹, 余金¹, 鲁习文¹^,*()

1. 华东理工大学数学学院, 上海 200237

收稿日期:2022-04-14 出版日期:2025-06-15 发布日期:2025-06-12
通讯作者: 鲁习文 E-mail:xwlu@ecust.edu.cn
基金资助:
国家自然科学基金(11871213)

Approximation algorithms for two-agent serial batching scheduling problems

Di ZHAO¹, Jin YU¹, Xiwen LU¹^,*()

1. School of Mathematics, East China University of Science and Technology, Shanghai 200237, China

Received:2022-04-14 Online:2025-06-15 Published:2025-06-12
Contact: Xiwen LU E-mail:xwlu@ecust.edu.cn

摘要/Abstract

摘要：

本文研究了单机上两代理串行分批排序问题, 分批时的每批加工时间有容量限制, 并且每批有一个分批费用, 该费用为常数, 且工件加工不可中断。对两个问题进行了考虑: 一个问题是在其中一个代理的最大完工时间与分批费用之和不超过某一阈值的前提下, 最小化另一个代理的总完工时间与分批费用之和; 另一个问题是在其中一个代理的总完工时间与分批费用之和不超过某一阈值的条件下, 最小化另一个代理的总完工时间与分批费用之和。这两个问题都是NP困难的, 对第一个问题给出了(2, 3/2)-近似算法。对第二个问题, 设计了渐近近似比为(2, 2)的近似算法。

关键词: 代理排序, 近似比, 分批, 渐近近似

Abstract:

In this paper, two-agent serial batching problems are studied on a single machine. Each batch has a capacity constraint on the processing time. And there is batching cost for each batch which is a constant. The preemption of jobs is not allowed. We consider two problems: One problem is to minimize the sum of the total completion time and the batching cost of one agent under the condition that the sum of the makespan and the batching cost of the other agent does not exceed a threshold value. The other is to minimize the sum of the total completion time and the batching cost of one agent under the condition that the sum of the total completion time and the batching cost of the other agent does not exceed a threshold value. Both problems are NP-hard. A (2, 3/2)-approximation algorithm is provided for the first problem and for the second problem, we design a (2, 2)-asymptotic approximation algorithm.

Key words: agent scheduling, approximate ratio, batch, asymptotic approximation

中图分类号:

O221.7

赵娣, 余金, 鲁习文. 单机两代理串行分批排序问题的近似算法[J]. 运筹学学报（中英文）, 2025, 29(2): 184-193.

Di ZHAO, Jin YU, Xiwen LU. Approximation algorithms for two-agent serial batching scheduling problems[J]. Operations Research Transactions, 2025, 29(2): 184-193.

参考文献 22

1	Agnetis A , Mirchandani P B , Pacciarelli D , et al. Scheduling problems with two competing agents[J]. Operations Research, 2004, 52, 229- 242. doi: 10.1287/opre.1030.0092
2	Baker K , Smith J C . A multiple criterion model for machine scheduling[J]. Journal of Scheduling, 2003, 6 (1): 7- 16. doi: 10.1023/A:1022231419049
3	Cheng T C E , Ng C T , Yuan J J . Multi-agent scheduling on a single machine to minimize total weighted number of tardy jobs[J]. Theoretical Computer Science, 2007, 362 (1-3): 273- 281.
4	Cheng T C E , Ng C T , Yuan J J . Multi-agent scheduling on a single machine with max-form criteria[J]. European Journal of Operational Research, 2008, 188 (2): 603- 609. doi: 10.1016/j.ejor.2007.04.040
5	Agnetis A , Gawiejnowicz S , Soukhal A , et al. Multiagent Scheduling: Models and Algorithms[M]. Berlin: Springer, 2014.
6	Lee K , Choi B C , Leung Y T , et al. Approximation algorithms for multi-agent scheduling to minimize total weighted completion time[J]. Information Processing Letters, 2009, 109 (16): 913- 917. doi: 10.1016/j.ipl.2009.04.018
7	万龙. 有关单机两代理排序问题的两个结果[J]. 运筹学学报, 2015, 19 (2): 54- 60. doi: 10.15960/j.cnki.issn.1007-6093.2015.02.006
8	张玉忠. 工件可拒绝排序问题综述[J]. 运筹学学报, 2020, 24 (2): 111- 130. doi: 10.15960/j.cnki.issn.1007-6093.2020.02.009
9	高强, 鲁习文. 带有拒绝的单机和同型机排序问题[J]. 运筹学学报, 2014, 18 (4): 1- 10. doi: 10.3969/j.issn.1007-6093.2014.04.001
10	Zhao K J , Lu X W . Two approximation algorithms for two-agent scheduling on parallel machines to minimize makespan[J]. Journal of Combinatorial Optimization, 2016, 31 (1): 260- 278. doi: 10.1007/s10878-014-9744-y
11	Brucker P , Gladky A , Hoogeveen H , et al. Scheduling a batching machine[J]. Journal of Scheduling, 1998, 1 (1): 31- 54. doi: 10.1002/(SICI)1099-1425(199806)1:1<31::AID-JOS4>3.0.CO;2-R
12	Cheng T C E , Yuan J J , Yang A F . Scheduling a batch-processing machine subject to precedence constraints, release dates and identical processing times[J]. Computers & Operations Research, 2001, 33 (8): 685- 690.
13	He C , Xu C , Lin H . Serial-batching scheduling with two agents to minimize makespan and maximum cost[J]. Journal of Scheduling, 2020, 23 (1): 609- 617.
14	何程, 韩鑫鑫. 同时最优化时间表长与总完工时间的双代理单机序列分批排序问题[J]. 工程数学学报, 2020, 37 (4): 487- 494.
15	Sabouni M , Jolai F . Optimal methods for batch processing problem with makespan and maximum lateness objectives[J]. Applied Mathematical Modelling, 2010, 34 (2): 314- 324. doi: 10.1016/j.apm.2009.04.007
16	Li S S , Yuan J J . Unbounded parallel-batching scheduling with two competitive agents[J]. Journal of Scheduling, 2012, 15 (5): 629- 640. doi: 10.1007/s10951-011-0253-x
17	井彩霞, 吴瑞强, 贾兆红. 并行分批排序综述[J]. 运筹与管理, 2020, 29 (1): 223- 239.
18	Mor B , Mosheiov G . Single machine batch scheduling with two competing agents to minimize total flowtime[J]. European Journal of Operational Research, 2011, 215 (3): 524- 531. doi: 10.1016/j.ejor.2011.06.037
19	Feng Q, Yu Z Y, Shang W P. Pareto optimization of serial-batching scheduling problems on two agents[C]//The 2011 International Conference on Advanced Mechatronic Systems, 2011: 165-168.
20	Graham R L , Lawler E L , Lenstra J K , et al. Optimization and approximation in deterministic sequencing and scheduling: a survey[J]. Annals of Discrete Mathematics, 1979, 5 (1): 287- 326.
21	Simchi-Levi D . New worst-case results for the bin-packing problem[J]. Naval Research Logistics, 1994, 41 (4): 579- 585. doi: 10.1002/1520-6750(199406)41:4<579::AID-NAV3220410409>3.0.CO;2-G
22	Chen R , Yuan J J , Gao Y . The complexity of CO-agent scheduling to minimize the total completion time and total number of tardy jobs[J]. Journal of Scheduling, 2019, 22 (5): 1- 13.

[1]	盖玲, 张威伟, 李闽溟. 设施选址装箱博弈问题的机制设计与分析[J]. 运筹学学报（中英文）, 2025, 29(2): 58-67.
[2]	王冬, 李刚刚, 罗文昌. 工件具有任意尺寸的混合分批平行机排序问题的近似算法[J]. 运筹学学报, 2022, 26(3): 133-142.
[3]	王利博, 李文华, 余丹. 单机上带有可变前瞻区间的分批在线排序问题[J]. 运筹学学报, 2022, 26(1): 134-140.
[4]	刘晓霞, 余山杉, 罗文昌. 工作有到达时间且拒绝工件总个数受限的单机平行分批排序问题的近似算法[J]. 运筹学学报, 2020, 24(1): 131-139.
[5]	李文华, 翟威娜, 柴幸, 高超. 具有两个不相容工件族单位工件的有界分批在线排序问题[J]. 运筹学学报, 2019, 23(4): 105-110.
[6]	彭南南, 张玉忠, 柏庆国, 王成飞. 工件满足一致性的同类机在线分批排序问题[J]. 运筹学学报, 2019, 23(1): 111-118.
[7]	何程, 韩鑫鑫. 同时最小化最大费用和最大完工时间的双代理无界平行分批排序[J]. 运筹学学报, 2018, 22(3): 109-116.
[8]	酒明珠, 高园, 原晋江. 工件可自由下线最小化总完工时间的平行分批排序问题[J]. 运筹学学报, 2018, 22(1): 32-41.
[9]	张玉忠, 张龙. 优化交货期窗口的两阶段供应链排序问题[J]. 运筹学学报, 2016, 20(4): 30-38.
[10]	苗翠霞, 邹娟. 带有退化效应和序列相关运输时间的排序问题[J]. 运筹学学报, 2016, 20(4): 61-68.
[11]	王成飞, 张玉忠. 提前预知信息的在线分批排序问题[J]. 运筹学学报, 2016, 20(1): 84-90.
[12]	李文华, 柴幸, 袁航, 杨素芳. 平行机上带有前瞻区间的不相容工件组在线排序问题[J]. 运筹学学报, 2015, 19(4): 121-126.
[13]	万龙. 有关单机两代理排序问题的两个结果[J]. 运筹学学报, 2015, 19(2): 54-60.
[14]	焦成文, 李文华. 工件按加工长度不增序到达的最小化最大流程在线分批排序[J]. 运筹学学报, 2013, 17(4): 96-102.
[15]	杨素芳, 李文华. 具有前瞻区间的两个工件组单机在线排序问题[J]. 运筹学学报, 2012, 16(2): 115-120.

单机两代理串行分批排序问题的近似算法

Approximation algorithms for two-agent serial batching scheduling problems

RichHTML

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献 22

相关文章 15

编辑推荐

Metrics

本文评价