Discrete Optimization

Scheduling a Bounded Parallel-Batching Machine with Incompatible Job Families and Rejection

Expand

Online published: 2014-12-30

Abstract

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.

Cite this article

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

Options
Outlines

/