文献类型：期刊文献

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

英文题名：Approximation algorithms for two-agent serial batching scheduling problems

作者：赵娣[1];余金[1];鲁习文[1]

机构：[1]华东理工大学数学学院,上海200237

年份：2025

卷号：29

期号：2

起止页码：184

中文期刊名：运筹学学报(中英文)

外文期刊名：Operations Research Transactions

收录：;北大核心:【北大核心2023】；

基金：国家自然科学基金(No.11871213)

语种：中文

中文关键词：代理排序;近似比;分批;渐近近似

外文关键词：agent scheduling;approximate ratio;batch;asymptotic approximation

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