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 job...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)。
文摘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.
