Having single operator, which could do work and it's time of availability - for example from
8 am till 9 pm. And operator have limited resource - let's call it energy (
e <= E_MAX.
List of works that need to be done:
[w1, w2, w3, ... ,wN], (operator could complete only subset of works, all incompleted works moving to next period)
Each work require:
[t1, t2, t3, ..., tN] -
t[I] - time required to complete
[e1, e2, e3, ..., eN] -
e[I] - energy comsumed to complete
However some work have fixed schedule
[wK1, ..., wKN], like
w[k1] should be done from
3pm till 4pm. All other work could be completed in any other empty time slot.
And finaly each task have it's reward -
[r1, r2, ..., rN], where
r[i] - reword we get for
w[i], but there is one more problem. Reward it's not a constant, it's some function from energy. so
r1(e|t1) could be different from
e|t[i] - energy at moment i.
The problem is to build schedule which maximaze total reward for the period.
So this seems like optimization combinatorial problem and I'm trying to figure out - what is a common problem behind it. For the first look I thought about
knapsack problem, but I think that fact of some work have fixed schedule make whole story pretty different.
I would appriciate for your ideas - what model it could be or maybe what changes I need to make to convert it to some existing problem.
UPD 1: Assuming there is no breaks in task. All unfinished/uncompleted task just moving to next period. So operator work only with subset of all works and could select any he like - the goal is just get max profit buy the end of the period.