Time is discrete. There are $n$ time-slots and a single job that can be scheduled on one machine of budget $B$. If the job is scheduled at time-slot $t$, then it will consume $c(t)$ units of the budget $B$. If the job is not scheduled for a period of $x(j)$ consecutive time-slots (the $j$th idle period), then a penalty of $p(j)=\lfloor x(j)/2\rfloor$ occurs. The objective is to schedule the job in order to minimize the sum of penalties $p(j)$ (over idle periods $j$). There is one constraint: the budget $B$ of the machine should be respected.
I am trying to find an optimal online algorithm for the online version of this problem, i.e., at time-slot $t$, we only know the budget $B$, the set of $t$ time-slots, and the costs $c(1), c(2), \ldots, c(t)$ for all $i$.
Can you suggest a way to solve this online problem? Do you see any similarities with other online problems in the literature so I may use to start solving my problem?
Note that an offline version of this problem with incremental budget has a dynamic programming (DP) solution as shown here.
After analyzing the DP solution, I found that the optimal value of the problem can be found in an online fashion. In other words, as we construct the DP table $M(t,p)$, we calculate $\min\{ p + \lfloor (n-t)/2\rfloor : t,p\in\{0,\ldots,n\},\, M(t, p) \ne -\infty\}$. At the last slot, we can found the least value and that would be the optimal number of truncated gaps. However, the optimal solution, the actual scheduling of the job in each slot, cannot be found in an online fashion using the DP solution.
