Parameterized Complexity of Scheduling Unit-Time Jobs with Generalized Precedence Constraints

Let ${𝒮}^{\ast }={(C_j^{\ast })}_{j\in J}$ be a schedule with optimal sum of completion times. Assume $C_j^{\ast }>k_p$ for some $j\in J_p$. Let $t^{\ast }\le k_p$ be the earliest time slot where no predecessor is processed. Choose a job $i\in J$ with $C_i^{\ast }=t^{\ast }$. By choice of $t^{\ast }$, $i$ is not a predecessor job. Let $h$ be an earliest predecessor with $C_h^{\ast }>t^{\ast }$. Construct a schedule $𝒮$ from ${𝒮}^{\ast }$ by swapping $i$ and $h$. Clearly, the swap is feasible and does not alter the sum of completion times. Thus $𝒮$ is optimal too, while the earliest time slot $t$ where no predecessor is processed has increased, $t>t^{\ast }$. Repeat until all completion times of predecessor jobs do not exceed $k_p$. $◀$

The algorithm alg-pre for instances of $P|$gen-prec$,p_j=1|\gamma$, $\gamma \in \{C_{\max },{\sum }_j{C}_j,{\sum }_j{w}_j{C}_j\}$, with predecessors $J_p=\{i_1,\mathrm{\dots },i_{k_p}\}\subseteq J$ proceeds as follows: Repeatedly pick a configuration ${(C_{i_{\mathrm{\ell }}})}_{\mathrm{\ell }=1}^{k_p}$ of predecessor completion times from $𝒞:={\{1,\mathrm{\dots },k_p\}}^{k_p}$ if $\gamma \in \{C_{\max },{\sum }_j{C}_j\}$ or from $𝒞:={\{1,\mathrm{\dots },n\}}^{k_p}$ if $\gamma ={\sum }_j{w}_j{C}_j$. If ${(C_{i_{\mathrm{\ell }}})}_{\mathrm{\ell }=1}^{k_p}$ is a feasible schedule for $J_p$, insert all remaining jobs through List Scheduling in order of non-increasing weight and return the schedule with the smallest objective value.

Let ${𝒮}^{\ast }={(C_j^{\ast })}_{j\in J}$ be an optimal schedule, such that $(C_{i_1}^{\ast },\mathrm{\dots },C_{i_{k_p}}^{\ast })\in 𝒞$. (The existence of such ${𝒮}^{\ast }$ follows from Lemma 1). Consider the iteration of alg-pre where $C_j=C_j^{\ast }$ for all $j\in J_p$. Clearly, the algorithm computes a feasible schedule $𝒮={(C_j)}_{j\in J}$. Denote by $k_p^t$ the number of predecessor jobs processed during time slot $t\in \{1,\mathrm{\dots },n\}$.

We prove the optimality of $𝒮={(C_j)}_{j\in J}$ for $\gamma ={\sum }_j{w}_j{C}_j$, from which the statement for the other two objectives follows immediately. Assume the jobs in $J\setminus J_p$ have $1\le q\le n-k_p$ different weights that we denote by $w^1\ge w^2\ge \mathrm{\dots }\ge w^q$. We consider the vector $z(t)=(z_1(t),\mathrm{\dots },z_q(t))\in {\mathbb{N}}^q$ where $z_i(t)$, $i\in \{1,\mathrm{\dots },q\}$, denotes the number of jobs in $J\setminus J_p$ with weight $w^i$ that $𝒮$ processes during time slot $t\in \mathbb{N}$. For ${𝒮}^{\ast }$, we define $z^{\ast }(t)$, $t\in \mathbb{N}$, analogously. If $z(t)=z^{\ast }(t)$ for all $t\in \mathbb{N}$, then ${\sum }_j{w}_j{C}_j={\sum }_j{w}_j{C}_j^{\ast }$ and $𝒮$ is optimal. Otherwise, let $T:=\min \{t\mid z(t)\ne z^{\ast }(t)\}$ be the smallest time slot for which $z(T),z^{\ast }(T)$ are not equal.

Assume first that $z(T)$ is lexicographically smaller than $z^{\ast }(T)$. Let $i\in \{1,\mathrm{\dots },q\}$ be such that $z_s^{\ast }(T)=z_s(T)$ for and $z_i^{\ast }(T)>z_i(T)$. It holds that . Subsequently, there exists a job $j\in J$ with weight $w_j=w^i$, such that $C_j^{\ast }\le T$ but $C_j>T$. Observe that $j$ is not a predecessor, otherwise $C_j=C_j^{\ast }$. Since $C_j^{\ast }\le T$, job $j$ is available at time $T-1$ in ${𝒮}^{\ast }$ and thus also in $𝒮$. Since alg-pre sets $C_j>T$, the following holds: When $j$ is considered, the algorithm has already occupied all machines during time slot $T$, namely with predecessor jobs or jobs with weight at least $w_j=w^i$. This yields a contradiction as

Assume now that $z^{\ast }(T)$ is lexicographically smaller than $z(T)$ and let again $i\in \{1,\mathrm{\dots },q\}$ be such that $z_s^{\ast }(T)=z_s(T)$ für while . By analogous arguments, there exists a job $j\in J\setminus J_p$ with weight $w^i$ such that $C_j\le T$, $C_j^{\ast }>T$ and $j$ is available at time $T-1$ in ${𝒮}^{\ast }$.

The optimal schedule ${𝒮}^{\ast }$ occupies all machines during time slot $T$ with predecessor jobs or jobs of weight at least $w_j=w^i$: Otherwise, swapping $j$ with a job of smaller weight or placing it on an idle machine during time slot $T$ would yield a feasible solution with smaller weighted sum of completion times. As before,

yields a contradiction.

We conclude with a brief runtime analysis: We sort all non-predecessor jobs with respect to weight once ($𝒪(n\log n)$ time). Then the algorithm checks $|𝒞|$ configurations $(t_1,\mathrm{\dots },t_{k_p})\in 𝒞$ of predecessor completion times. For each such configuration, the algorithm inserts $𝒪(n)$ jobs $j\in J\setminus J_p$. For each job $j\in J\setminus J_p$, it checks for $𝒪(n)$ time steps $t$ whether $j$ is available at time $t$. For any such time step $t$, the algorithm searches for an idle machine among $m$ machines. Since, $|𝒞|\in 𝒪(k^k)$ if $\gamma \in \{C_{\max },{\sum }_j{C}_j\}$ and $|𝒞|\in 𝒪(n^k)$ otherwise, the claimed asymptotic runtime follows. $◀$

Consider an optimal schedule ${𝒮}^{\ast }$ with completion times ${\overline{C}}_{\mathrm{\ell }}$, $\mathrm{\ell }\in J$, and assume that ${\overline{C}}_{\max }^s-{\overline{C}}_{\min }^s>k_s-1$ where ${\overline{C}}_{\min }^s=\min \{{\overline{C}}_{\mathrm{\ell }}\mid \mathrm{\ell }\in J_s\}$ is the completion time of an earliest successor and ${\overline{C}}_{\max }^s=\max \{{\overline{C}}_{\mathrm{\ell }}\mid \mathrm{\ell }\in J_s\}$ is the completion time of a latest successor. Let $t^{\ast }$ be the earliest time slot with where no successor is processed. Pick a job $j\in J\setminus J_s$ with $C_j^{\ast }=t^{\ast }$. Let $i$ be a successor with $C_i^{\ast }=t^{\ast }-1$. We construct from ${𝒮}^{\ast }$ another feasible schedule $𝒮$ with completion times $C_{\mathrm{\ell }}$, $\mathrm{\ell }\in J$, by swapping jobs $i$ and $j$. Clearly, $𝒮$ is feasible and optimal and $C_{\max }^s:=\max \{C_{\mathrm{\ell }}\mid \mathrm{\ell }\in J_s\}={\overline{C}}_{\max }^s$. If $t^{\ast }-1={\overline{C}}_{\min }^s$ and $i$ is the only successor with ${\overline{C}}_i=t^{\ast }-1$, then $C_{\min }^s:=\min \{C_{\mathrm{\ell }}\mid \mathrm{\ell }\in J_s\}>{\overline{C}}_{\min }^s$. Else, if $t^{\ast }-1>{\overline{C}}_{\min }^s$ and $i$ is again the only successor with ${\overline{C}}_i=t^{\ast }-1$, then $C_{\min }^s={\overline{C}}_{\min }^s$ but the earliest time slot $t\in (C_{\min }^s,C_{\max }^s)$ without successors in $𝒮$ has decreased, . Otherwise, we also get $C_{\min }^s={\overline{C}}_{\min }^s$ while the overall number of time slots $t\in (C_{\min }^s,C_{\max }^s)$ without successors in $𝒮$ has decreased. By repeating the argument, we obtain an optimal solution where all successors are processed within a time span of length $k_s$. $◀$

Given a set $J_s\subseteq J$ of successors, the algorithm and-alg-succ repeatedly picks a configuration ${(C_j)}_{j\in J_s}$ from

such that $|\{j\in J_s\mid C_j=t\}|\le m$ for all $t\in \{1,\mathrm{\dots },n\}$ and if $i$ is a predecessor of $j$. Then the algorithm inserts the remaining jobs as follows: and-alg-succ iterates over all successors in order of non-decreasing completion times. For each successor $j\in J_s$, the algorithm assigns the earliest possible completion time to each predecessor. If some predecessor cannot be scheduled before $j$, the respective schedule of successors is discarded. In the end, all remaining jobs (which are neither successor nor predecessor) are inserted as early as possible.

By Lemma 3, there exists an optimal schedule ${𝒮}^{\ast }$ with completion times $C_j^{\ast }$, $j\in J$ such that $(C_{i_1}^{\ast },\mathrm{\dots },C_{i_{k_s}}^{\ast })\in 𝒞$. Consider the iteration of and-alg-succ where $C_j=C_j^{\ast }$ for all $j\in J_s$. Since ${𝒮}^{\ast }$ is a feasible schedule with identical successor completion times, there is enough space on the machines prior to each successor $j\in J_s$ for and-alg-succ to schedule all of $j$’s predecessors. Hence, $(C_{i_1}^{\ast },\mathrm{\dots },C_{i_{k_s}}^{\ast })$ is not discarded and and-alg-succ computes a feasible schedule $𝒮$. We proceed by proving that $𝒮$ is in fact optimal. We define $z(t)$ as the number of jobs in $\{j\in J\setminus J_s\mid C_j=t\}$, which $𝒮$ processes during time slot $t\in \mathbb{N}$. For ${𝒮}^{\ast }$, we define $z^{\ast }(t)$, $t\in \mathbb{N}$, analogously. If $z(t)=z^{\ast }(t)$ for all $t\in \mathbb{N}$, then $(C_{\max },{\sum }_j{C}_j)=(C_{\max }^{\ast },{\sum }_j{C}_j^{\ast })$ and $𝒮$ is optimal. Otherwise, let $T:=\min \{t\mid z(t)\ne z^{\ast }(t)\}$ be the smallest time slot for which $z(T),z^{\ast }(T)$ are not equal.

Assume first that . It holds that . Subsequently, there exists a job $j\in J$, such that $C_j^{\ast }\le T$ but $C_j>T$. Observe that $j$ is no successor, otherwise $C_j=C_j^{\ast }$. When and-alg-succ assigns a completion time to $j$, there is an idle machine during time slot $T$ because and and-alg-succ assigns a completion time $C_j\le T$ to $j$, contradiction. If $z(T)>z^{\ast }(T)$, there exists a job $j\in J\setminus J_s$, such that $C_j^{\ast }>T$ but $C_j\le T$. The optimal schedule ${𝒮}^{\ast }$ has an idle machine during time slot $T$ because . Adapting the optimal solution such that $C_j^{\ast }=T$ does not negatively affect neither the optimality of ${𝒮}^{\ast }$ nor its feasibility since $j$ has no predecessors. We repeat this argument until $z(t)=z^{\ast }(t)$ for all $t\in \mathbb{N}$, which proves that $𝒮$ is optimal. We omit a runtime analysis since it is analogous to the proof of Theorem 2. $◀$

Using and-alg-succ, it is easy to see that $P|or/and$-$prec,p_j=1|\gamma$, $\gamma \in \{C_{\max },{\sum }_j{C}_j\}$, lies in $𝒫$ if the number of successors $k_s\le const$ is bounded by some constant $const\ge 0$: Recall that $or/and$-constraints require each precedence constraint ${\psi }_j$, $j\in J$, to be a disjunction of conjunctive clauses. By electing one clause per job, we can solve an instance $I$ of $P|or/and$-$prec,p_j=1|\gamma$ by solving $𝒪({|I|}^{k_s})$ instances of $P|prec,p_j=1|\gamma$ with at most $k_s$ successors. We state this in the following corollary:

For and+or-constraints, we can strengthen this argument to prove that P$|$and+or-$prec,p_j=1|\gamma$, $\gamma \in \{C_{\max },{\sum }_j{C}_j\}$ is FPT. Consider an instance $I=(J,{({\psi }_j)}_{j\in J},m)$ of P$|$and+or-$prec,p_j=1|\gamma$ with $k_s$ successors. Let $J_s=J_s^{and}\dot{\cup }{J}_s^{or}$ be a partition of the set of successors, where a precedence constraint ${\psi }_j$ of a job $j\in J_s$ is a conjunction if $j\in J_s^{and}$ and a disjunction if $j\in J_s^{or}$. We call jobs in $J_s^{and}$ $and$-jobs and jobs in $J_s^{or}$ $or$-jobs. Consider an $or$-job $j\in J_s^{or}$ and let $i\in J$ be a predecessor of $j$. Consider the alternate instance $I^{\prime }=(J,{({\psi }_j^{\prime })}_{j\in J},m)$ that we obtain by fixing $i$ as only predecessor of $j$, that is, ${\psi }_{\mathrm{\ell }}^{\prime }={\psi }_{\mathrm{\ell }}$ if $\mathrm{\ell }\ne j$ and ${\psi }_j^{\prime }=x_i$. Clearly, any optimal schedule ${𝒮}^{\prime }$ for $I^{\prime }$ is feasible for $I$ too. However, whether ${𝒮}^{\prime }$ is optimal for $I$ too, strongly depends on whether $i$ is also a predecessor of other jobs in $J_s\setminus \{j\}$. See Figure 1 for an example. Consider an arbitrary feasible schedule $𝒮$ for $I$. For each $or$-job $j\in J_s^{or}$, we can determine a predecessor job $i_j$ of $j$ such that $i_j$ precedes $j$ in $𝒮$. Observe that we can possibly have $i_j=i_k$ for two different $or$-jobs $j,k\in J_s^{or}$, $j\ne k$, and that each $i_j$ may be a predecessor of multiple $and$-successors. In other words, the choice of ${(i_j)}_{j\in J_s^{or}}$ gives rise to a function $\sigma :J_s^{or}\to 2^{J_s}$ where $k\in \sigma (j)$ precisely if $k$ is an $or$-job and $i_j=i_k$ or if $k$ is an $and$-job with predecessor $i_j$. Our algorithm essentially tests all relevant variations of $\sigma$ and picks an $and$-predecessor $i_j\in J$ for each $or$-job $j\in J_s$ according to $\sigma$, before it applies and-alg-succ to the resulting instance with $and$-constraints.

Observe the following properties of a common predecessor function $\sigma :J_s^{or}\to 2^{J_s}$: First, $j\in \sigma (j)$ for all $j\in J_s^{or}$. If $j,k\in J_s^{or}$ and $k\in \sigma (j)$, then $\sigma (j)=\sigma (k)$. If $\sigma$ is the common predecessor function of $I$ with respect to ${(i_j)}_{j\in J_s^{or}}$, then $i_j$ is a predecessor of every $k\in \sigma (j)$, $j\in J_s^{or}$. Lastly, note that $\sigma$ may have different generating representatives ${(i_j)}_{j\in J_s^{or}}$, ${(i_j^{\prime })}_{j\in J_s^{or}}$, ${(i_j)}_{j\in J_s^{or}}\ne {(i_j^{\prime })}_{j\in J_s^{or}}$. The following lemma proves that for a given common predecessor function, the choice of generating representatives is irrelevant (under certain conditions).

Assume that $L$ is infeasible and let $C=(j_1,\mathrm{\dots },j_r)$ be a cycle in the precedence graph, $j_0:=j_r$. Consider a job $j_{\mathrm{\ell }}$ in the cycle, $\mathrm{\ell }\in \{1,\mathrm{\dots },r\}$. If $j_{\mathrm{\ell }}\in J_s^{and}$ is an $and$-job in $I$, then $j_{\mathrm{\ell }-1}$ is also a predecessor of $j_{\mathrm{\ell }}$ in $L^{\prime }$. If $j_{\mathrm{\ell }}\in J_s^{or}$, then $j_{\mathrm{\ell }-1}=i_j$. Since $j_{\mathrm{\ell }-1}$ is a successor in $L$, it is also a successor in $I$ and thus $j_{\mathrm{\ell }-1}=i_j=i_j^{\prime }$ is also a predecessor of $j_{\mathrm{\ell }}$ in $L^{\prime }$. Therefore, the precedence graph of $L^{\prime }$ contains the same cycle $C$ and $L^{\prime }$ is infeasible.

Assume now that $L$ is feasible, $\sigma ={\sigma }^{\prime }$ and $i_j=i_k^{\prime }$ whenever $i_j^{\prime }=i_k$, $j,k\in J_s^{or}$. Let ${(C_j)}_{j\in J}$ be the completion times of an optimal schedule $𝒮$. We define a schedule ${𝒮}^{\prime }$ with completion times ${(C_j^{\prime })}_{j\in J}$ for $L^{\prime }$. We denote the sets in $\{\sigma (j)\cap J_s^{or}\mid j\in J_s^{or}\}$ by $S_1,\mathrm{\dots },S_r$. Observe that ${(S_{\mathrm{\ell }})}_{\mathrm{\ell }=1}^r$ is a partition of $J_s^{or}$ and that $S_{\mathrm{\ell }}=\sigma (j)\cap J_s^{or}$ precisely if $S_{\mathrm{\ell }}={\sigma }^{\prime }(j)\cap J_s^{or}$, $j\in J_s^{or},\mathrm{\ell }=1,\mathrm{\dots },r$. For each $\mathrm{\ell }=1,\mathrm{\dots },r$, let $i(\mathrm{\ell }),i^{\prime }(\mathrm{\ell })\in J_s^{or}$ be the common predecessor with $i(\mathrm{\ell })=i_k,i^{\prime }(\mathrm{\ell })=i_k^{\prime }$ for all $k\in S_{\mathrm{\ell }}$. We obtain ${𝒮}^{\prime }$ from $𝒮$ by swapping the positions of $i(\mathrm{\ell })$ and $i^{\prime }(\mathrm{\ell })$ for all $\mathrm{\ell }=1,\mathrm{\dots },r$. Observe that this is in fact the same as setting $C_{i_k^{\prime }}^{\prime }=C_{i_k}$ and $C_{i_k}^{\prime }=C_{i_k^{\prime }}$ for $k\in J_s^{or}$. All other jobs $j\in J$ remain as in $𝒮$, i.e. $C_j^{\prime }=C_j$. Note that the schedule ${𝒮}^{\prime }$ is well-defined, since we require $i^{\prime }(\mathrm{\ell })=i(p)$ if $i(\mathrm{\ell })=i^{\prime }(p)$ for $\mathrm{\ell },p=1,\mathrm{\dots },r$. Clearly, $\gamma (𝒮)=\gamma ({𝒮}^{\prime })$. It remains to show that ${𝒮}^{\prime }$ is feasible. To this end, let $k\in J_s$ be a successor job in $I$. Observe that $C_k=C_k^{\prime }$: If $k\ne i_{\mathrm{\ell }},i_{\mathrm{\ell }}^{\prime }$ for all $\mathrm{\ell }\in J_s^{or}$, then $C_k^{\prime }=C_k$ by definition of $C_k$. Otherwise, if $k=i_{\mathrm{\ell }}$ or $k=i_{\mathrm{\ell }}^{\prime }$ for some $\mathrm{\ell }\in J_s^{or}$, then $\mathrm{\ell }\in I_s$ and thus $k=i_{\mathrm{\ell }}=i_{\mathrm{\ell }}^{\prime }$ and $C_k^{\prime }=C_k$. Assume now that $k\in J_s^{and}$ is an $and$-job in $I$ and let $j\in J$ be a predecessor of $k$ in $L^{\prime }$. Clearly, $j$ is also a predecessor of $k$ in $L$ and thus . If $C_j^{\prime }=C_j$, then $j$ precedes $k$ in ${𝒮}^{\prime }$ because . Otherwise, $j=i_{\mathrm{\ell }}$ or $j=i_{\mathrm{\ell }}^{\prime }$ for some $\mathrm{\ell }\in J_s^{or}$ with $i_{\mathrm{\ell }}\ne i_{\mathrm{\ell }}^{\prime }$. Assume first that $j=i_{\mathrm{\ell }}$. Since $k$ is an $and$-job in $I$ with predecessor $i_{\mathrm{\ell }}=j$, it follows that $k\in \sigma (\mathrm{\ell })={\sigma }^{\prime }(\mathrm{\ell })$. By definition of ${\sigma }^{\prime }$, job $i_{\mathrm{\ell }}^{\prime }$ is a predecessor of $k$ in $I$ and $L$ and thus . We can show analogously that if $j=i_{\mathrm{\ell }}^{\prime }$. Finally, let $k\in J_s^{or}$ be a former $or$-job. By definition of $L^{\prime }$, the job $i_k^{\prime }$ is the only predecessor of $k$ in $L^{\prime }$ and $i_k$ is the only predecessor of $k$ in $L$. Subsequently, , which completes the proof. $◀$

We now describe the algorithm and+or-alg-succ for P$|$and+or-$prec,p_j=1|\gamma$, $\gamma \in \{C_{\max },{\sum }_j{C}_j\}$, in more detail. First, and+or-alg-succ picks completion times $C_j$, $j\in J_s$, for the successors in the same way as and-alg-succ. For every $or$-job $j\in J_s^{or}$ with a predecessor $i\in J_s$ with , we set $i_j=i$. Afterwards, and+or-alg-succ iterates over all $or$-jobs $j_1,\mathrm{\dots },j_q\in J_s^{or}$ in order of non-decreasing completion time $C_{j_1}\le \mathrm{\dots }\le C_{j_q}$. If no $i_{j_i}$ has been chosen yet, we pick a subset $S_j\subseteq \{j_i,\mathrm{\dots },j_q\}\cup J_s^{and}$ of successor jobs with $j\in S_j$. Then we pick a job $i\in J$ such that the successors of $i$ in $\{j_i,\mathrm{\dots },j_q\}\cup J_s^{and}$ are precisely the vertices in $S_j$. We set $i_k=i$ for all $k\in S_j\cap J_s^{or}$. (If such a job $i$ does not exist, $S_j$ is an infeasible choice.) Finally, the algorithm and+or-alg-succ proceeds along the same lines as and-alg-succ for the $and$-variation of $I$ w.r.t. ${(i_j)}_{j\in J_s^{or}}$.