中文

Operations Research Transactions >

2025 , Vol. 29 >Issue 2: 184 - 193

DOI: https://doi.org/10.15960/j.cnki.issn.1007-6093.2025.02.014

Research Article

Approximation algorithms for two-agent serial batching scheduling problems

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

Received date: 2022-04-14

  Online published: 2025-06-12

Copyright

, 2025, All rights reserved. Unauthorized reproduction is prohibited.
Fold

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

Cite this article

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

References

1 Agnetis A , Mirchandani P B , Pacciarelli D , et al. Scheduling problems with two competing agents[J]. Operations Research, 2004, 52, 229- 242.
2 Baker K , Smith J C . A multiple criterion model for machine scheduling[J]. Journal of Scheduling, 2003, 6 (1): 7- 16.
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.
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.
7 万龙. 有关单机两代理排序问题的两个结果[J]. 运筹学学报, 2015, 19 (2): 54- 60.
8 张玉忠. 工件可拒绝排序问题综述[J]. 运筹学学报, 2020, 24 (2): 111- 130.
9 高强, 鲁习文. 带有拒绝的单机和同型机排序问题[J]. 运筹学学报, 2014, 18 (4): 1- 10.
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.
11 Brucker P , Gladky A , Hoogeveen H , et al. Scheduling a batching machine[J]. Journal of Scheduling, 1998, 1 (1): 31- 54.
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.
16 Li S S , Yuan J J . Unbounded parallel-batching scheduling with two competitive agents[J]. Journal of Scheduling, 2012, 15 (5): 629- 640.
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.
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.
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.
Options
Outlines

/

〈 〉