Abstract: 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（n²） time algorithm for the first problem. Moreover, for the other two problems, we first show that they are N P-hard, and then present pseudo-polynomial time dynamic programming algorithms and fully polynomial time approximation schemes for them, respectively. 

Key words: Batch scheduling, Compatibility, Rejection, Makespan, Approximation algorithm