Single machine parallel-batch scheduling with deteriorating jobs

We consider several single machine parallel-batch scheduling problems in which the processing time of a job is a linear function of its starting time. We give a polynomial-time algorithm for minimizing the maximum cost, an O(n5) time algorithm for minimizing the number of tardy jobs, and an O(n2) time algorithm for minimizing the total weighted completion time. Furthermore, we prove that the problem for minimizing the weighted number of tardy jobs is binary NP-hard.