Moderate Exponential-time Quantum Dynamic Programming Across the Subsets for Scheduling Problems¹¹1This is an extension of the conference paper of Grange et al., 2023a .

The NP-hard single-machine scheduling problem at stake is the minimization of the total weighted completion time with deadline constraints, often referred to as $1|\tilde{d}_{j}|\sum_{j}w_{j}C_{j}$ in the scheduling literature. The input is given, for each job $j\in[n]$, by a weight $w_{j}$, a processing time $p_{j}$ and a deadline $\tilde{d}_{j}$ before which the job must be completed. We define the completion time $C_{j}(\pi)$ of job $j$ as the end time of the job on the machine for the permutation $\pi$. So, if $j$ starts as time $t$ for the permutation $\pi$, then $C_{j}(\pi)=t+p_{j}$. The problem aims at finding the feasible permutation for which the total weighted sum of completion times is minimal. A permutation $\pi$ is feasible if $C_{j}(\pi)\leq\tilde{d}_{j}$ for all job $j$. Thus, the problem can be formulated as follows:

where the set of feasible permutations is $\Pi=\{\pi\in S_{[n]}\,|\,C_{j}(\pi)\leq\tilde{d}_{j}\,,\forall j\in[n]\}\,.$

This problem satisfies two recurrences. For deriving them, we need to introduce the set $T:=\left\llbracket 0,\sum_{j=1}^{n}p_{j}\right\rrbracket$, where we use the notation $\llbracket a,b\rrbracket=\{a,a+1,\ldots,b\}$ for integers $a$ and $b$. For $J\subseteq[n]$ and $t\in T$, we define $\textup{OPT}[J,t]$ as the optimal value of the problem in which only jobs in $J$ are scheduled from time $t$. Thus, solving our nominal problem $1|\tilde{d}_{j}|\sum_{j}w_{j}C_{j}$ amounts to compute $\textup{OPT}[[n],0]$.

The first recurrence comes from the standard Dynamic Programming Across the Subsets (DPAS) described in (1). However, compared to usual DPAS, we introduce an extra parameter $t$ necessary for the solution with our hybrid algorithm as explained later. The idea of this recurrence is to get the optimal value of our problem for jobs in $J$ and starting at time $t$ by finding, over all jobs $j\in J$, the permutation that ends by $j$ with the best cost value. It is possible to do so because no matter what the optimal permutation of the first $(|J|-1)$ jobs is, the cost of setting job $j$ at the end of the permutation is always known. Indeed, the time taken to process all jobs in $J\setminus\{j\}$ is always $\sum_{k\in J\setminus\{j\}}p_{k}$. Thus, the completion time of $j$ is defined by $c_{j}=t+\sum_{k\in J}p_{k}$. It results that the cost of setting $j$ at the end of the permutation is $w_{j}(t+\sum_{k\in J}p_{k})$. It also implies that the deadline constraint for job $j$ is satisfied if $t+\sum_{k\in J}p_{k}\leq\tilde{d}_{j}$. Specifically, for all $J\subseteq[n]$ and for all $t\in T$, we have

initialized by $\textup{OPT}[\emptyset]=0$.

The second recurrence generalizes the previous one. For this recurrence, the principle of computing $\textup{OPT}[J,t]$ is similar to (2) but instead of setting one job at the end of the permutation, we choose $|J|/2$ jobs and set them to be the half last jobs of the permutation. Specifically, for all $J\subseteq[n]$ of even cardinality and $t\in T$, we have

initialized by, $\forall j\in[n]$ and $t\in T$, $\textup{OPT}[\{j\},t]=\left\{\begin{aligned} &w_{j}(p_{j}+t)~{}~{}&\text{if }\tilde{d}_{j}\geq p_{j}+t\\ &+\infty~{}~{}&\text{otherwise}\end{aligned}\right.\,.$

For a given $X\subseteq J$ of size $|J|/2$, recurrence (3) computes the best permutation of jobs in $X$ starting at time $t$, and the best permutation of jobs in $J\setminus X$ starting at time $t+\sum_{k\in X}p_{k}$ as we know that, as before, no matter what is the optimal permutation for jobs in $X$, the time taken to process them all is exactly $\sum_{k\in X}p_{k}$.

The two above recurrences have been illustrated with problem $1|\tilde{d}_{j}|\sum_{j}w_{j}C_{j}$. In the next subsection, we propose a general formulation of these recurrences that will be used to elaborate our algorithm as general as possible to solve a broad class of scheduling problems.

Let us consider the following general scheduling problem:

where $\Pi\subseteq S_{[n]}$ is the set of feasible permutations of $[n]:=\{1,\ldots,n\}$ according to given constraints and $f$ is the objective function. We introduce a related problem $P$ useful for deriving the dynamic programming recursion, for which we specify the instance: for $J\subseteq[n]$ and $t\in\mathbb{Z}$,

as the nominal scheduling problem $\mathcal{P}$ that schedules only jobs in $J$ and starts the schedule at time $t$. Let us note $\textup{OPT}[J,t]$ the optimal value of $P(J,t)$. It results that solving $\mathcal{P}$ amounts to solving $P([n],0)$, and it can be performed by Q-DDPAS if the related problem $P$ satisfies the two recurrences (Add-DPAS) and (Add-D-DPAS) below. Henceforth, we denote by $2^{[n]}$ the set of all subsets of $[n]$, and by $\llbracket a,b\rrbracket$ the set $\{a,a+1,\ldots,b\}$. Let us introduce the first recurrence.

Throughout, we commit a slight abuse of language by letting (Add-DPAS) both refer to the property satisfied by a given optimization problem and to the resulting dynamic programming algorithm. Notice the presence of the additional parameter $t_{0}$ in the above definition, which is typically absent in the scheduling literature. In particular, $t_{0}$ is a constant throughout the whole recursion (Add-DPAS) and does not impact the resulting computational complexity. The use of that extra parameter in $T$ shall be necessary later when applying our hybrid algorithm.

Property 2.1 expresses that finding the optimal value of $P$ for jobs in $J$ and starting at time $t$ is done by finding over all jobs $j\in J$ the permutation that ends by $j$ with the best cost value. Function $g$ represents the cost of $j$ being the last job of the permutation. Notice that isolating the last job of the permutation is a usual technique in scheduling as displayed in (1). In the second recurrence below, we provide a similar scheme, where instead of one job, we isolate half of the jobs in $J$, turning the computation of $g$ to the solution of another problem on a sub-instance with $|J|/2$ jobs.

For a given $X\subseteq J$, the above recursion computes the best permutation of jobs in $X$ starting at time $t$, and the best permutation of jobs in $J\setminus X$ starting at time $\tau_{\text{shift}}$, adding the function $h$ that represents the cost of the concatenation between these two permutations.

Despite the previous remark, the two recurrences differ on the size of the subsets considered along the recursions, leading to different formulations and therefore require more or less sub-problems to be solved optimally in the dynamic programming process. This is formalized in the following proposition. Note that we use the notation $f_{1}(n)=\omega(f_{2}(n))$ if $f_{1}$ dominates asymptotically $f_{2}$.

The proof is given in the Supplementary Materials. Notice that if $n$ is not a power of 2, we can still add fake jobs without changing the following conclusion: solving $\mathcal{P}$ with (Add-DPAS) is faster than with (Add-D-DPAS). However, in the next subsection, we describe a hybrid algorithm Q-DDPAS that improves the complexity of solving $\mathcal{P}$ by combining recurrences (Add-DPAS) and (Add-D-DPAS) with a quantum subroutine.

In this subsection, we describe our hybrid algorithm Q-DDPAS adapted from the work of Ambainis et al., (2019). Notice that it assumes to have a quantum random access memory (QRAM) (Giovannetti et al., , 2008), namely, to have a classical data structure that stores classical information but can answer queries in quantum superposition. We underline that this latter assumption is strong because QRAM is not yet available on current universal quantum hardware. First, let us introduce the Quantum Minimum Finding algorithm of Dürr and Høyer, (1996), which constitutes a fundamental subroutine in our algorithm. This algorithm essentially applies several times Grover Search (Grover, , 1996) and provides a quadratic speedup for the search of a minimum element in an unsorted table.

Next, we describe the algorithm of Ambainis et al., (2019) adapted for our Additive DPAS recurrences which implies extra parameters in $T$. We call it Q-DDPAS and it consists essentially of calling recursively twice Quantum Minimum Finding and computing classically the left terms. Without loss of generality, we assume that 4 divides $n$. This can be achieved by adding at most three fake jobs and, therefore, does not change the algorithm complexity. Q-DDPAS consists of two steps. First, we compute classically by (Add-DPAS) the optimal values of $P$ on sub-instances of $n/4$ jobs and for all starting times $t\in T$. Second, we call recursively two times Quantum Minimum Finding with (Add-D-DPAS) to find optimal values of $P$ on sub-instances of $n/2$ jobs starting at any time $t\in T$, and eventually of $n$ jobs starting at $t=0$ (corresponding to the optimal value of the nominal problem $\mathcal{P}$). Specifically, we describe Q-DDPAS in Algorithm 1.

The detailed proof of the correctness of the algorithm, involving the description of the gate implementation, is detailed in the companion paper Grange et al., (2024), with all the low-level details for implementing the algorithm.

We observe that the complexity of Q-DDPAS can be further reduced by performing a third call to Equation (Add-D-DPAS) as suggested by Ambainis et al., (2019).

Notice that the classical part of Q-DDPAS can be replaced by any classical algorithm $\mathcal{A}$, if $\mathcal{A}$ computes in $\mathcal{O}^{*}(|T|\cdot 1.728^{n})$ all $\textup{OPT}[X,t]$ for $X\subseteq[n]$ of size $n/4$ and $t\in T$. Moreover, if $\mathcal{A}$ happens to reduce the classical part complexity $\mathcal{O}^{*}(|T|\cdot c^{n})$ for $c<1.728$, the complexity of Q-DDPAS can also be reduced in the same spirit as the slight modification of Observation 2.9.

The application of Q-DDPAS for Additive DPAS to the specific problem $1|\tilde{d}_{j}|\sum_{j}w_{j}C_{j}$ introduced in Subsection 2.1 is given in Subsection 4.1, together with other scheduling examples. Before introducing other types of problems tackled by Q-DDPAS in the next section, we provide some insights to underline why the use of the quantum subroutine Quantum Minimum Finding in Q-DDPAS must be carefully combined with classical computation to achieve a quantum speedup.

We begin with the specific problem of minimizing the total weighted number of late jobs with release date constraints, often referred to as $1|r_{j}|\sum w_{j}U_{j}$ in the literature. The input is given by, for each job $j\in[n]$, a weight $w_{j}$, a processing time $p_{j}$, a release date $r_{j}$ that is the time from which the job can be scheduled (and not before), and a due date $d_{j}$ that indicates the time after which the job is late. Thus, a job $j$ is late in permutation $\pi$ if its completion time is larger than $d_{j}$, namely if $C_{j}(\pi)>d_{j}$. We name $U_{j}(\pi)=\mathbb{1}_{C_{j}(\pi)>d_{j}}$ its indicator function of lateness. This problem aims at finding the feasible permutation, namely where each job starts after its release date, for which the total weighted number of late jobs is minimal. Thus, the problem can be formulated as follows:

where the set of feasible solutions is $\Pi=\{\pi\in S_{[n]}\,|\,C_{j}(\pi)\geq r_{j}+p_{j}\}\,.$

This problem does not satisfy the recurrences (Add-DPAS) and (Add-D-DPAS) because the release date constraints do not allow the addition of sub-instances. Let us take the example of (Add-D-DPAS). The starting time of the second half of jobs $J\setminus X$ in (Add-D-DPAS) can be known only if we know the optimal permutation of the first half job, which is in opposition with the dynamic programming principle. Indeed, the release dates enable empty slots in the scheduling on the first half job such that the time to process all these jobs is not always equal to $\sum_{k\in X}p_{k}$ and can be larger.

This observation leads to different recurrences, where the time to process the jobs would be known by dynamic programming. For that, we define an auxiliary problem on which the recurrences apply and we introduce a new set of parameters $E:=\left\llbracket 0,\sum_{j=1}^{n}w_{j}\right\rrbracket$. For $J\subseteq[n]$, $t\in T:=\left\llbracket 0,\sum_{j=1}^{n}p_{j}\right\rrbracket\cup\{+\infty\}$ and $\epsilon\in E$, we note $\textup{OPT}[J,t,\epsilon]$ the minimum makespan, i.e. the completion time of the last job, for jobs in $J$ beginning at time $t$ where the weighted number of late jobs is exactly $\epsilon$. Notice that by convention, $\textup{OPT}[J,t,\epsilon]=+\infty$ if there is no feasible solution, i.e. if $\left\{\pi\in S_{J}:C_{j}(\pi)\geq\max(t,r_{j})+p_{j}\,,\forall j\in J\mbox{ and }\sum_{j\in J}w_{j}U_{j}(\pi)=\epsilon\right\}=\emptyset$. Thus, our initial problem $1|r_{j}|\sum w_{j}U_{j}$ is

The following recurrence that satisfies the auxiliary problem is inspired by the work of Lawler, (1990) for the problem of minimizing the total weighted number of late jobs on a single machine under preemption and release date constraints ($1|r_{j},pmtn|\sum w_{j}U_{j}$). For $J\subseteq[n]$, $t\in T$, $\epsilon\in E$,

In this recurrence, for each $j\in J$, we impose $j$ as the last job of the permutation and distinguish two cases, whether it is late or not. Notice that the starting time of $j$ is known and equal to $\textup{OPT}[J\setminus\{j\},t,.]$ which represents the value for the time parameter. The recurrence is initialized by, for $j\in[n]$, $t\in T$ and $\epsilon\in E$,

This recurrence generalizes into the following dichotomic version for which, instead of setting the last job of the permutation, we set the half-last jobs. For all $J\subseteq[n]$ of even cardinality, $t\in T$ and $\epsilon\in E$,

initialized by the same values of $\textup{OPT}[\{j\},t,\epsilon]$ for $j\in[n]$, $t\in T$ and $\epsilon\in E$. Next, we provide generic recurrences to consider problems for which the composition of sub-instances is possible.

Let us consider a scheduling problem with $n$ jobs

where $\Pi\subseteq S_{[n]}$ is the set of feasible permutations of $[n]:=\{1,\ldots,n\}$ according to given constraints and $f$ is the objective function. Following the example detailed in the previous subsection, we consider an auxiliary problem $\mathcal{P}^{\prime}$ useful for deriving the dynamic programming recursion, for which we specify the instance: for $J\subseteq[n]$ the jobs to be scheduled, $t\in\mathbb{Z}$ the starting time of the schedule and $\epsilon\in\mathbb{Z}$, we define

where $f^{\prime}$, respectively $\Pi^{\prime}$, is the objective function, respectively the feasible set, are different from those of $\mathcal{P}$. We assume that solving $\mathcal{P}$ amounts to finding the smallest $\epsilon\in\mathbb{Z}$ such that the auxiliary problem $\mathcal{P}^{\prime}$ is bounded. Specifically,

To solve the nominal problem $\mathcal{P}$ by classical dynamic programming, problem $\mathcal{P}^{\prime}$ must satisfy recurrence (Comp-DPAS) or recurrence (Comp-D-DPAS) below (as in Remark 2.4, we can state that a problem satisfies one if and only if it satisfies the other one). As we explain later, solving $\mathcal{P}$ with our hybrid algorithm requires problem $P^{\prime}$ to satisfy the two recurrences.

Recurrence (Comp-DPAS) differs from recurrence (Add-DPAS) in two aspects. First, the optimal values of the problem on sub-instances are composed, and not added, because of the nature of the constraints. Second, the search for the minimum value is done not only over all jobs in $J$, but also over all values in $E$. More precisely, for a given $\epsilon_{0}\in E$, the optimal value of $P^{\prime}(J,t,\epsilon_{0})$ is the minimum value of all possible composition of optimal values of the problem on sub-instances with parameters $\epsilon_{1}$ and $\epsilon_{2}$ such that $\epsilon_{1}+\epsilon_{2}=\epsilon_{0}$. We have the following result.

The auxiliary problem $P^{\prime}$ must satisfy the following recurrence (Comp-D-DPAS) in addition to recurrence (Comp-DPAS).

As for the Additive DPAS, we notice that, with a classical dynamic programming algorithm, the time complexity to solve $\mathcal{P}$ with recurrence (Comp-DPAS) is better than with recurrence (Comp-D-DPAS). Next, we show that the hybrid algorithm applied to problems satisfying Additive DPAS recurrences can be easily adapted to tackle problems satisfying Composed DPAS recurrences.

The hybrid algorithm for Composed DPAS derives naturally from Algorithm 1. It amounts to replacing the recurrence (Add-DPAS), respectivelly (Add-D-DPAS), by (Comp-DPAS), respectivelly (Comp-D-DPAS), resulting in Algorithm 2. Eventually, we use Algorithm 2 as a subroutine to solve Equation (6), i.e. to solve the nominal problem $\mathcal{P}$.