摘要
We study a scheduling problem with incompatible job families and rejection on a parallel-batching machine,where the objective is to minimize the makespan of all accepted jobs plus the total penalty of all rejected jobs.We provide a polynomial-time algorithm for the case where all jobs have identical release dates and a pseudo-polynomial-time algorithm for the case where the number of distinct release dates is fixed.We also present a 2-approximation algorithm and a polynomial-time approximation scheme for the general problem.
基金
supported in part by National Natural Science Foundation of China(NSFC,Nos.11326191,11401604,11401605 and 11171313)
NSF of Henan Province(No.132300410392)
the Education Department of Henan Province Natural Science Research Program(No.14A110027)。
