We address a scheduling problem with job processing time compatibility and rejection on a parallel-batching machine.The processing time of each job is defined by an interval and any number of jobs can be assigned into a batch provided that the processing time intervals of the jobs in the common batch are not disjoint.Three problems are considered: (1) minimize the sum of the makespan of accepted jobs and the total rejection penalty of rejected jobs;(2) minimize the makespan of accepted jobs subject to an upper bound on the total rejection penalty of rejected jobs;(3) minimize the total rejection penalty of rejected jobs subject to an upper bound on the makespan of accepted jobs.We provide an O(n2) time algorithm for the first problem.Moreover,for the other two problems,we first show that they are A/P-hard,and then present pseudo-polynomial time dynamic programming algorithms and fully polynomial time approximation schemes for them,respectively.