Scheduling to minimize the truncated gaps

Question

I have a single job of unit length, a set of $n$ slots, and a budget of $B$ units. If the job is scheduled at slot $t$, then it will consume $c(t)$ units of the budget $B$. If the job is not scheduled for a period of $x$ consecutive slots, then a penalty of $\lfloor x/2\rfloor$ occurs. The objective is to schedule the job in order to minimize the sum of penalties.

For example, for $n=12$, if the job is scheduled at slot 1, at slot 3, at slot 6, and at slot $12$, then the sum of penalties is $\lfloor 1/2\rfloor + \lfloor 2/2\rfloor + \lfloor 5/2\rfloor = 0+1+2=3$.

Is this problem NP-hard?

I am trying to reduce the knapsack problem to it. Transforming the values in the knapsack problem to the penalties is somehow difficult, because once the job is scheduled at $t$, the penalty is initialized.

Answer 1

The problem is polynomial-time solvable. To avoid edge cases it is better to think that the job needs to be scheduled at time $0$ and that $c(0)=0$.

Let $OPT[t,p]$ be the minimum amount of budget that needs to be spent in order to schedule the job in the first $t$ slots with an overall penalty of at most $p$ and with the additional constraint that the job must be scheduled at time $t$.

Let $P(t', t) = \Big\lfloor \frac{t-t'-1}{2} \Big\rfloor$ be the penalty incurred if the job is scheduled at times $t'$ and $t > t'$ and is not scheduled at any time in-between.

Then $OPT[0,p] = 0$ and, for $t>0$: $$ OPT[t,p] = c(t) + \min_{\substack{t'=0,\dots,t-1 \\ P(t',t) \le p}} OPT\left[t', p - P(t',t) \right] $$

The minimum attainable penalty up to time $t$, with the constraint that the job is scheduled at time $t$, is then: $$ \mu(t) = \min \{p \in \{1,\dots,\lfloor t/2 \rfloor\} \mid OPT[t,p] \le B \} $$

And the minimum attainable penalty for your problem is: $$ \min_{t=0,\dots,n} \left\{ \mu(t) + P(t,n+1) \right\}. $$

Notice that there are at most $n \cdot (P(0,n)+1) = O(n^2)$ values $OPT[p,t]$ to compute.