Improved algorithms for single-machine serial-batch scheduling with rejection to minimize total completion time and total rejection cost

Abstract

Recently, Shabtay considered a scheduling problem on a single serial-batching machine with rejection to minimize the dual criteria of total completion time and total rejection cost, where the number of jobs to be included in each batch is not restricted. He studied four variants of the problem: the first is to minimize the sum of the two criteria; the second and third are to minimize one criterion, subject to the other criterion not exceeding a given value; and the last is to find the Pareto-optimal solutions for the bicriterion problem. Shabtay provided an O(n5) algorithm for the first variant and an O(n6/ϵ2) fully polynomial-time approximation scheme (FPTAS) for the fourth variant. In this paper, we provide an alternative O(n4) algorithm to solve the first variant and an O(n5/ϵ) FPTAS for the fourth variant, which are more efficient than those developed by Shabtay from a theoretical perspective. However, when the size of each batch is bounded by a given number b > 1, the corresponding time complexities of our algorithms for the first and fourth variants reduce to O(bn3) and O(bn4/ϵ), respectively.