最小化加权误工工件数的多代理平行分批排序

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

Parallel-batch Scheduling with Multi-agent Jobs to Minimize the Weighted Number of Tardy Jobs

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.