0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – zdm Jun 26 at 20:44
  • $\begingroup$ yes for every maximal contiguous block. $\endgroup$ – zdm Jun 26 at 21:36
3
$\begingroup$

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)/2\rfloor) -\zeta(t) + \sum_{i=s+1}^t c(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$.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.