CAJ | 학술논문

考虑多代理的平行分批排序,不同代理的工件不能放在同一批中加工,目标函数是最小化加权误工工件数.本文考虑两种模型,证明了甚至当所有工件具有单位权时,这两个模型都是强NP困难的.但当代理数给定时,这两个问题都可在拟多项式时间解决,并且当工件具有单位权时,可在多项式时间解决.进一步证明当代理数固定时,两个问题都有FPTAS算法.
고필다대리적평행분비배서,불동대리적공건불능방재동일비중가공,목표함수시최소화가권오공공건수.본문고필량충모형,증명료심지당소유공건구유단위권시,저량개모형도시강NP곤난적.단당대리수급정시,저량개문제도가재의다항식시간해결,병차당공건구유단위권시,가재다항식시간해결.진일보증명당대리수고정시,량개문제도유FPTAS산법.
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.