Parallel-batch scheduling with deterioration and rejection on a single machine#br#
The single machine parallel-batch scheduling with deteriorating jobs and rejection
is considered in this paper. A job is either rejected, in which a rejection penalty should be paid,
or accepted and processed on the machine. Each job’s processing time is an increasing linear
function of its starting time. The machine can process any number of jobs simultaneously as a
batch. The processing time of a batch is equal to the largest processing time of the jobs in the
batch. The objectives are to minimize the makespan and the total weighted completion time,
respectively, under the condition that the total rejection penalty cannot exceed a given upper
bound Q. We show that both problems are NP-complete and present dynamic programming
algorithms and fully polynomial time approximation schemes (F P T ASs) for the considered
problems.
关键词：
parallel-batch scheduling,
rejection,
deterioration,
F P T AS,
NP-complete
