Meng, Jintao; Lu, Xiaoxu; Li, Shisheng; Zhou, Yongwei Batch scheduling with job processing time compatibility and rejection on a single machine. (English) Zbl 1474.90161 Chin. Q. J. Math. 35, No. 3, 320-330 (2020). Summary: 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) minimizing the sum of the makespan of accepted jobs and the total rejection penalty of rejected jobs; (2) minimizing the makespan of accepted jobs subject to an upper bound on the total rejection penalty of rejected jobs; (3) minimizing the total rejection penalty of rejected jobs subject to an upper bound on the makespan of accepted jobs. We provide an \(O (n^2)\) time algorithm for the first problem. Moreover, for the other two problems, we first show that they are \(NP\)-hard, and then present pseudo-polynomial time dynamic programming algorithms and fully polynomial time approximation schemes for them, respectively. MSC: 90B35 Deterministic scheduling theory in operations research 90C39 Dynamic programming 90C59 Approximation methods and heuristics in mathematical programming Keywords:batch scheduling; compatibility; rejection; makespan; approximation algorithm PDFBibTeX XMLCite \textit{J. Meng} et al., Chin. Q. J. Math. 35, No. 3, 320--330 (2020; Zbl 1474.90161) Full Text: DOI