# Minimizing the gaps with incremental capacity

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.

• For (i) and (ii), yes, we have to guarante that $C(t)=\sum_{s\leq t}\zeta(s)-\sum_{s\in S}c(s)\geq 0$ for all $t$. I don't get the difference between the last part of (iii) and (iv) but there is a penalty for every contiguous unused block. I will edit the question and give an example to illustrate my meaning. – zdm Jun 26 '20 at 20:44
• yes for every maximal contiguous block. – zdm Jun 26 '20 at 21:36

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$$.

• In the reccurrence relation, did you mean $-c(t)+\sum_{i=s+1}^{t}\zeta(i)$ instead of $-\zeta(t)+\sum_{i=s+1}^{t}c(i)$ – zdm Jul 6 '20 at 2:05
• Yes, got them backwards. Also had an off-by-one error. Edited to fix them both. – Neal Young Jul 6 '20 at 2:56
• Hi. If we have two jobs instead of one and we have $\zeta_1$ and $\zeta_2$ and $c_1$ and $c_2$ for job 1 and job 2 respectively. If the two jobs cannot be scheduled at the same slot, can we still solve the problem using dynamic programming? – zdm Nov 7 '20 at 23:23