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

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

作　　者：原晋江[1] 何程[1,2] 林诒勋[1] 

机构地区：[1]郑州大学数学系,郑州450052 [2]解放军信息工程大学理学院数理系,郑州450052

出　　处：《运筹学学报》2009年第4期1-13,共13页Operations Research Transactions

基　　金：supported by NSFC(10671183);NFSC-RGC(70731160633)

摘　　要：考虑多代理的平行分批排序,不同代理的工件不能放在同一批中加工,目标函数是最小化加权误工工件数.本文考虑两种模型,证明了甚至当所有工件具有单位权时,这两个模型都是强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.

关 键 词：运筹学 多目标排序 平行分批 误工工件数 FPTAS 

分 类 号：O223[理学—运筹学与控制论] TH165[理学—数学]