Minimizing the gaps with incremental capacity

Question

There are a single job, a machine and a set of $n$ slots. The machine has a capacity that increments by $\zeta(t)$ every slot $t=1,2,\ldots,n$. Initially (before the first slot), the machine has 0 capacity i.e., the available capacity $C(t)$ at slot $t$ is $C(t):=\sum_{s\leq t}\zeta(s)$ (if the job was not scheduled at $t$ or before $t$). If the job is scheduled at slot $t$, then it will consume $c(t)$ units of the available capacity $C(t)$. If the job is not scheduled for a period of $x$ consecutive slots, then a penalty of $\lfloor x/2\rfloor$ occurs.

EDIT

• We have to guarantee that $C(t)=\sum_{s\leq t}\zeta(s)-\sum_{s\in S}c(s)\geq 0$ for all $t$ where $S\subseteq\{1,2,\ldots,t\}$ is the set of slots where the job was scheduled.

• For the penalty: there is a penalty for every contiguous unused block.

Here, is an example to illustrate the problem. Say $n=8$ and the job is scheduled at time $1$, $4$, and $8$. Here, we have a penalty of $\lfloor{2/2}\rfloor=1$ between time $1$ and $4$ since the job is not scheduled for a period of 2 consecutive slots ($2$ and $3$). Also, we have a penalty of $\lfloor{3/2}\rfloor=1$ between time $4$ and $8$ since the job is not scheduled for a period of 3 consecutive slots ($5$, $6$ and $7$). Thus, the objective here is $1+1$.

Given $\zeta(t)$, $c(t)$ for all $t=1,2,\ldots,n$, the objective is to schedule the job during the $n$ slots in order to minimize the sum of penalties while respecting the capacity of machine in all scheduled slots. Is this problem NP-hard?

I tried to reduce the knapsack problem to it but I did not succeed yet. Also, I tried to solve the problem in polynomial-time using dynamic programming but failed also due to the incremental capacity.

Answer 1

Here's a poly-time dynamic-programming algorithm.

Lemma 1. The problem in the post has a poly-time dynamic-programming algorithm.

Proof sketch. Fix an input $(\zeta, c)$ over time slots $\{1,2,\ldots, n\}$.

For each $t, p\in \{0, 1,\ldots, n\}$, define subproblem $M(t, p)$ as follows. Consider the problem restricted to the first $t$ time slots. (That is, the problem over time slots $\{1,2,\ldots, t\}$, with $\zeta$ and $c$ restricted to those time slots.) For this restricted problem, consider just those solutions that have total penalty $p$ and (if $t\ge 1$) do use slot $t$. Define $M(t, p)$ to be the maximum, over all such solutions, of the capacity $C(t)$ achieved by that solution. (Or $-\infty$ if there are no such solutions.)

The desired answer is $\min \{ p + \lfloor (n-t)/2\rfloor : t,p\in\{0,\ldots,n\},\, M(t, p) \ne -\infty\}$.

Then $M(0, 0) = 0$ and $M(0, p) = -\infty$ for $p>0$. For $t>0$, the following recurrence relation holds.

$M(t, p)$ is the maximum, over $s\in\{0,1,\ldots,t-1\}$, of

$$\begin{cases} M(s, p-\lfloor(t-s-1)/2\rfloor) -c(t) + \sum_{i=s+1}^t \zeta(i) & \scriptsize\textit{ (if that quantity is well-defined and non-negative)} \\ -\infty & \scriptsize\textit{ (otherwise). } \end{cases} $$ Here's the intuition. Consider the possible solutions for the first $t$ time slots that use slot $t$ and achieve total penalty $p$. Partition these solutions according to their last slot used, say, slot $s$, before slot $t$. (Or $s=0$ if slot $t$ is the first slot used.) Given $s$, such a solution consists of some solution $S_s$ for slots $1,2,\ldots, s$ (with slot $s$ used if $s>0$), followed by unused slots $s+1,s+2,\ldots, t-1$, followed by the used slot $t$.

The penalty incurred for the size-$(t-s)$ block of unused slots $s+1,\ldots, t-1$ is $\lfloor (t-s)/2\rfloor$. So the cumulative penalty incurred by $S_s$ must be $p$ minus this. The capacity $C(t)$ at time $t$ must be the capacity $C(s)$ achieved by $S_s$ at time $s$ plus the additional capacity added for unused slots $s+1,\ldots, t$, minus $\zeta(t)$ for using slot $t$. So $C(t)$ will be maximized when $C(s)$ is maximized (over all solutions $S_s$ with appropriate penalty). This is why the recurrence relation holds.

There are $O(n^2)$ subproblems, and for each the right-hand side of the recurrence can be evaluated in time $O(n)$ (with appropriate preprocessing), so this yields an $O(n^3)$-time dynamic-programming algorithm. $~~\Box$.