【摘要】 考虑多代理的平行分批排序,不同代理的工件不能放在同一批中加工,目标函数是最小化加权误工工件数.本文考虑两种模型,证明了甚至当所有工件具有单位权时,这两个模型都是强NP困难的.但当代理数给定时,这两个问题都可在拟多项式时间解决,并且当工件具有单位权时,可在多项式时间解决.进一步证明当代理数固定时,两个问题都有FPTAS算法.更多还原

【Abstract】 We consider parallel-batch scheduling with multi-agent jobs to minimize the weighted number of tardy jobs in which jobs of different agents cannot be processed in a common batch.Two models are considered.We show that the general versions of these two models are strongly NP-hard even when the jobs have unit weight.But when the number of agents is a fixed integer,the two problems can be solved in pseudo-polynomial time in general and can be solved in polynomial time when the jobs have unit weight. We also show that both models can be solved by fully polynomial-time approximation schemes when the number of agents is a fixed integer.更多还原