2
$\begingroup$

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 <= 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: time - [t1, t2, t3, ..., tN] - t[I] - time required to complete w[I] energy - [e1, e2, e3, ..., eN] - e[I] - energy comsumed to complete w[I]

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 r1(e|t2), where 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.

$\endgroup$
  • $\begingroup$ Bin packing is relevant too. The scheduled tasks only split days into several bins (in terms of time, but not in terms of energy). That reward isn't constant is even worse. Although, I didn't understand what happens to incomplete work (can I cut up any tasks I want? do I get rewards for partial completion?). If cutting tasks has no penalty, the problem may be as easy as linear programming. $\endgroup$ – Karolis Juodelė Nov 25 '16 at 13:12
  • $\begingroup$ @KarolisJuodelė i updated question body. I agree that interval could be splited to parts and it will allow to simplify problem forgeting about scheduled items. $\endgroup$ – Ph0en1x Nov 25 '16 at 13:44
  • $\begingroup$ 1. I don't understand the reward part. You say the reward depends on the energy, but what do you mean by that? The energy spent on this particular task? The energy spent by all tasks scheduled at the same time? And what is the function? Is it fixed, or is it part of the input? If it's part of the input, how is it specified, and are there any restrictions on what kinds of functions are allowed? 2. You might be able to solve this with integer linear programming (in practice). $\endgroup$ – D.W. Nov 25 '16 at 16:23
  • $\begingroup$ @D.W. You could assume reward function which depend from time task executed and from what task was already completed. Ex: you have a mechanical part and work which change it somehow (ex: component metal grinding. The result of 30 mins of grinding depend from what work was done before, when work executed and motivation/tiredness. Because when work start metal could be cold (if it's first work) or warm (if component already was processed), worker could be motivated bored and tired. And when part was warm and worker fine - result of grinding is 7, but if metal is cold and human tired - result 4. $\endgroup$ – Ph0en1x Nov 25 '16 at 17:25

Your Answer

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

Browse other questions tagged or ask your own question.