论文部分内容阅读
We consider the problem of scheduling n deteriorating jobs with release dates on a single batching machine.Each job is either accepted and processed in batches on the parallel batch machine,or rejected by paying penalties.The processing time of a job is a simple linear increasing function of its starting time.The objective is to minimize the sum of the makespan of the accepted jobs and the total penalty of the rejected jobs.First,we show that the problem is NP-hard in the ordinary sense.Then,we provide two pseudo-polynomial time algorithms and a fully polynomial-time approximation scheme to solve this problem.Furthermore,we provide an optimal O(n logn)time algorithm for the case where jobs have identical realease dates.