We study a single-machine scheduling problem to minimize the maximum late work. Late work of a job is the amount of processing time of this job that is performed after its due date. We show that the problem without flexible maintenance activities can be solved in <InlineEquation ID="IEq1"> <EquationSource Format="TEX">$O(n\log n)$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>O</mi> <mo stretchy="false">(</mo> <mi>n</mi> <mo>log</mo> <mi>n</mi> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation> time for n jobs. The problem with flexible maintenance activities and resumable jobs is solvable in <InlineEquation ID="IEq2"> <EquationSource Format="TEX">$O(n\log n)$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>O</mi> <mo stretchy="false">(</mo> <mi>n</mi> <mo>log</mo> <mi>n</mi> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation> time if <InlineEquation ID="IEq3"> <EquationSource Format="TEX">$k\le n$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>k</mi> <mo>≤</mo> <mi>n</mi> </mrow> </math></EquationSource> </InlineEquation> and in <InlineEquation ID="IEq4"> <EquationSource Format="TEX">$O(k+n\log k)$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>O</mi> <mo stretchy="false">(</mo> <mi>k</mi> <mo>+</mo> <mi>n</mi> <mo>log</mo> <mi>k</mi> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation> time if <InlineEquation ID="IEq5"> <EquationSource Format="TEX">$k>n$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>k</mi> <mo>></mo> <mi>n</mi> </mrow> </math></EquationSource> </InlineEquation>, where k denotes the number of maintenance activities. When the jobs are nonresumable, the problem is unary NP-hard for arbitrary k. We show that the special case with identical processing times is solvable in <InlineEquation ID="IEq6"> <EquationSource Format="TEX">$O(n\log n)$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>O</mi> <mo stretchy="false">(</mo> <mi>n</mi> <mo>log</mo> <mi>n</mi> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation> time if <InlineEquation ID="IEq7"> <EquationSource Format="TEX">$k\le n$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>k</mi> <mo>≤</mo> <mi>n</mi> </mrow> </math></EquationSource> </InlineEquation> and in <InlineEquation ID="IEq8"> <EquationSource Format="TEX">$O(k+n\log n)$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>O</mi> <mo stretchy="false">(</mo> <mi>k</mi> <mo>+</mo> <mi>n</mi> <mo>log</mo> <mi>n</mi> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation> time if <InlineEquation ID="IEq9"> <EquationSource Format="TEX">$k>n$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>k</mi> <mo>></mo> <mi>n</mi> </mrow> </math></EquationSource> </InlineEquation>. Then, we prove the binary NP-hardness of the problem with fixed k by developing a pseudopolynomial time algorithm. Moreover, we show that this problem is inapproximable.

Minimizing the maximum late work for a single-machine scheduling problem with flexible maintenance activities

期刊论文
发表日期：

2025年7月1日

查看全文

Yao-Wen Sang,
Jun-Qiang Wang,
Yumei Huo,
Małgorzata Sterna,
Jacek Błażewicz

摘要

We study a single-machine scheduling problem to minimize the maximum late work. Late work of a job is the amount of processing time of this job that is performed after its due date. We show that the problem without flexible maintenance activities can be solved in $O(n\log n)$ $O (n log n)$ time for n jobs. The problem with flexible maintenance activities and resumable jobs is solvable in $O(n\log n)$ $O (n log n)$ time if $k\le n$ $k \leq n$ and in $O(k+n\log k)$ $O (k + n log k)$ time if $k>n$ $k > n$ , where k denotes the number of maintenance activities. When the jobs are nonresumable, the problem is unary NP-hard for arbitrary k. We show that the special case with identical processing times is solvable in $O(n\log n)$ $O (n log n)$ time if $k\le n$ $k \leq n$ and in $O(k+n\log n)$ $O (k + n log n)$ time if $k>n$ $k > n$ . Then, we prove the binary NP-hardness of the problem with fixed k by developing a pseudopolynomial time algorithm. Moreover, we show that this problem is inapproximable.