Bounded parallel-batch scheduling on single and multi machines for deteriorating jobs

We consider the bounded parallel-batch scheduling problem in which the processing time of a job is a simple linear function of its starting time. The objective is to minimize the makespan. When the jobs have identical release dates, we present an optimal algorithm for the single-machine problem and an fully polynomial-time approximation scheme for the parallel-machine problem. When the jobs have distinct release dates, we show that the single-machine problem is NP-hard and present an optimal algorithm for one special case.

► Minimizing of makespan parallel-batch scheduling with deteriorating jobs is considered.
► An optimal algorithm is presented for single-machine problem when jobs arrive simultaneously.
► An FPTAS is presented for multi-machine problem when jobs arrive simultaneously.
► We prove NP-hardness for single-machine problem when job arrive dynamic.
► An optimal algorithm is presented for one special case.