Batch scheduling with proportional-linear deterioration and outsourcing (Q1992948)

Summary: We consider the bounded parallel-batch scheduling with proportional-linear deterioration and outsourcing, in which the actual processing time is \(p_j = \alpha_j(A + D t)\) or \(p_j = \alpha_j t\). 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 \(p_j = \alpha_j(A + D t)\) 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 \(p_j = \alpha_j t\) model, when the jobs have distinct \(m (<n)\) release dates, we provide a dynamic programming algorithm, where \(n\) is the number of jobs.