title: Parallel batch scheduling of deteriorating jobs with release dates and rejection.
abstract: We consider the unbounded parallel batch scheduling with deterioration, release dates, and rejection. Each job is either accepted and processed on a single batching 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 present two pseudopolynomial time algorithms and a fully polynomial-time approximation scheme to solve this problem. Furthermore, we provide an optimal O(n log n) time algorithm for the case where jobs have identical release dates.
authors.affiliation: School of Mathematical Sciences, Qufu Normal University, Qufu, Shandong 273165, China ; School of Management Sciences, Qufu Normal University, Rizhao, Shandong 276826, China.
authors.forename: Juan
authors.initials: J
authors.lastname: Zou
authors.affiliation: School of Mathematical Sciences, Qufu Normal University, Qufu, Shandong 273165, China.
authors.forename: Cuixia
authors.initials: C
authors.lastname: Miao
mesh_terms: D000465:Algorithms; D008962:Models, Theoretical