Batch Scheduling with Proportional-Linear Deterioration and Outsourcing

Abstract EN

We consider the bounded parallel-batch scheduling with proportional-linear deterioration and outsourcing, in which the actual processing time is pj=αj(A+Dt) or pj=αjt.

A job is either accepted and processed in batches on a single machine by manufactures themselves or outsourced to the third party with a certain penalty having to be paid.

The objective is to minimize the maximum completion time of the accepted jobs and the total penalty of the outsourced jobs.

For the pj=αj(A+Dt) model, when all the jobs are released at time zero, we show that the problem is NP-hard and present a pseudo-polynomial time algorithm, respectively.

For the pj=αjt model, when the jobs have distinct m (