Beschreibung:
<jats:title>Abstract</jats:title><jats:p>We consider a variant of the NP-hard problem of assigning jobs to machines to minimize the completion time of the last job. Usually, precedence constraints are given by a partial order on the set of jobs, and each job requires all its predecessors to be completed before it can start. In this paper, we consider a different type of precedence relation that has not been discussed as extensively and is called OR-precedence. In order for a job to start, we require that <jats:italic>at least one</jats:italic> of its predecessors is completed—in contrast to <jats:italic>all</jats:italic> its predecessors. Additionally, we assume that each job has a release date before which it must not start. We prove that a simple List Scheduling algorithm due to Graham (Bell Syst Tech J 45(9):1563–1581, 1966) has an approximation guarantee of 2 and show that obtaining an approximation factor of <jats:inline-formula><jats:alternatives><jats:tex-math>$$4/3 - \varepsilon $$</jats:tex-math><mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML">
<mml:mrow>
<mml:mn>4</mml:mn>
<mml:mo>/</mml:mo>
<mml:mn>3</mml:mn>
<mml:mo>-</mml:mo>
<mml:mi>ε</mml:mi>
</mml:mrow>
</mml:math></jats:alternatives></jats:inline-formula> is NP-hard. Further, we present a polynomial-time algorithm that solves the problem to optimality if preemptions are allowed. The latter result is in contrast to classical precedence constraints where the preemptive variant is already NP-hard. Our algorithm generalizes previous results for unit processing time jobs subject to OR-precedence constraints, but without release dates. The running time of our algorithm is <jats:inline-formula><jats:alternatives><jats:tex-math>$$O(n^2)$$</jats:tex-math><mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML">
<mml:mrow>
<mml:mi>O</mml:mi>
<mml:mo>(</mml:mo>
<mml:msup>
<mml:mi>n</mml:mi>
<mml:mn>2</mml:mn>
</mml:msup>
<mml:mo>)</mml:mo>
</mml:mrow>
</mml:math></jats:alternatives></jats:inline-formula> for arbitrary processing times and it can be reduced to <jats:italic>O</jats:italic>(<jats:italic>n</jats:italic>) for unit processing times, where <jats:italic>n</jats:italic> is the number of jobs. The performance guarantees presented here match the best-known ones for special cases where classical precedence constraints and OR-precedence constraints coincide.
</jats:p>