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

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

Abstract

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

CLC Number:

O221.7

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

References 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]	Chengwen JIAO. Online scheduling on a single parallel-batch machine with linear lookahead [J]. Operations Research Transactions, 2024, 28(4): 111-116.
[2]	Dong WANG, Ganggang LI, Wenchang LUO. Approximation algorithm for mixed batch scheduling on identical machines for jobs with arbitrary sizes [J]. Operations Research Transactions, 2022, 26(3): 133-142.
[3]	Libo WANG, Wenhua LI, Dan YU. Online scheduling on single batch machine with variable lookahead interval [J]. Operations Research Transactions, 2022, 26(1): 134-140.
[4]	LIU Xiaoxia, YU Shanshan, LUO Wenchang. Approximation algorithms for single machine parallelbatch scheduling with release dates subject to the number of rejected jobs not exceeding a given threshold [J]. Operations Research Transactions, 2020, 24(1): 131-139.
[5]	LI Wenhua, ZHAI Weina, CHAI Xing, GAO Chao. On-line bounded-batching scheduling of unit-length jobs with two families [J]. Operations Research Transactions, 2019, 23(4): 105-110.
[6]	PENG Nannan, ZHANG Yuzhong, BAI Qingguo, WANG Chengfei. Online batch scheduling problem on uniform machines with agreeable processing times [J]. Operations Research Transactions, 2019, 23(1): 111-118.
[7]	HE Cheng, HAN Xinxin. Two-agent scheduling on an unbounded parallel-batching machine to minimize maximum cost and makespan [J]. Operations Research Transactions, 2018, 22(3): 109-116.
[8]	JIU Mingzhu, GAO Yuan, YUAN Jinjiang. The bounded parallel-batching scheduling with drop-line jobs to minimize total completion time [J]. Operations Research Transactions, 2018, 22(1): 32-41.
[9]	YANG Qi, JIANG Zhigang, FENG Enmin, YIN Hongchao, XIU Zhilong. Nonlinear dynamic system of batch fermentation with the function as parameters and identification [J]. Operations Research Transactions, 2017, 21(2): 46-56.
[10]	ZHANG Yuzhong, ZHANG Long. Two-stage supply chain scheduling with an assignable common due window [J]. Operations Research Transactions, 2016, 20(4): 30-38.
[11]	MIAO Cuixia, ZOU Juan. Scheduling with simple deterioration and past-sequence-dependent delivery times [J]. Operations Research Transactions, 2016, 20(4): 61-68.
[12]	WANG Chengfei, ZHANG Yuzhong. Online batch scheduling with known information in advance [J]. Operations Research Transactions, 2016, 20(1): 84-90.
[13]	LI Wenhua, CHAI Xing, YUAN Hang, YANG Sufang. On-line algorithms for incompatible job families on parallel machines scheduling with lookahead [J]. Operations Research Transactions, 2015, 19(4): 121-126.
[14]	WAN Long. Two results for single-machine two-agent scheduling problems [J]. Operations Research Transactions, 2015, 19(2): 54-60.
[15]	JIAO Chengwen, LI Wenhua. Online parallel batching scheduling for nonincreasing-processing-time jobs to minimize the maximum flow-time [J]. Operations Research Transactions, 2013, 17(4): 96-102.

Approximation algorithms for two-agent serial batching scheduling problems

RichHTML

PDF

Knowledge

Abstract

Cite this article

share this article

References 22

Related Articles 15

Recommended Articles

Metrics

Comments