×

Batch scheduling with job processing time compatibility and rejection on a single machine. (English) Zbl 1474.90161

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
PDFBibTeX XMLCite
Full Text: DOI