Scheduling a Bounded Parallel-Batching Machine with Incompatible Job Families and Rejection
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 elease dates is fixed. We also present a 2-approximation algorithm and a polynomial-time approximation scheme for the general problem.
Shi-Sheng Li · Ren-Xia Chen . Scheduling a Bounded Parallel-Batching Machine with Incompatible Job Families and Rejection[J]. Journal of the Operations Research Society of China, 2014 , 2(4) : 499 . DOI: 10.1007/s40305-014-0062-y
/
| 〈 |
|
〉 |