Improved Algorithms for Single-Machine Serial-Batch Scheduling With Rejection to Minimize Total Completion Time and Total Rejection Cost
针对单机串行批调度问题，提出更高效的精确算法和近似方案，分别将时间复杂度从O(n^5)降至O(n^4)、从O(n^6/ε^2)降至O(n^5/ε)，对批容量受限情形进一步优化。
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 <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">${O}$ </tex-math></inline-formula> ( <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$\textit{n}^{\mathbf {5}}$ </tex-math></inline-formula> ) algorithm for the first variant and an <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">${O}$ </tex-math></inline-formula> ( <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">${n} ^{\mathbf {6}}$/$\boldsymbol {\varepsilon }^{\mathbf {2}}$ </tex-math></inline-formula> ) fully polynomial-time approximation scheme (FPTAS) for the fourth variant. In this paper, we provide an alternative <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">${O}$ </tex-math></inline-formula> ( <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">${n} ^{\mathbf {4}}$ </tex-math></inline-formula> ) algorithm to solve the first variant and an <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">${O}$ </tex-math></inline-formula> ( <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">${n} ^{\mathbf {5}}$/$\boldsymbol {\varepsilon }$ </tex-math></inline-formula> ) 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 <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">${b}~\boldsymbol {>}1$ </tex-math></inline-formula> , the corresponding time complexities of our algorithms for the first and fourth variants reduce to <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">${O}$ </tex-math></inline-formula> ( <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">bn</i> <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$^{\mathbf {3}}$ </tex-math></inline-formula> ) and <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">${O}$ </tex-math></inline-formula> ( <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">bn</i> <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$^{\mathbf {4}}$/$\boldsymbol {\varepsilon }$ </tex-math></inline-formula> ), respectively.