I'm trying to create an analytical model for performance of a greedy scheduler in a particular domain. I've created a preliminary model, but I think it's very confusing to others and was wondering if someone could provide feedback.My problem domain follows. A greedy scheduler has the capacity to schedule c tasks and will select the c highest rewarding tasks. Tasks arrive dynamically online from an arrival pattern, A--that is for every time unit within a time horizon X tasks will arrive, where X is an arbitrary random variable. Task details are all drawn from an arbitrary predefined distribution. Task details include, reward, maximum waiting time before being serviced (i.e if a task is not serviced after m time units, the task will fail), and duration. I'll label the respective distributions as R for reward, M for maximum waiting time, and D for duration.I know this problem is very large, so I would like to focus on a much smaller component of this larger problem. Consider a greedy agent with capacity c and no tasks currently scheduled with a task mix of T, where the size of T is larger than c and T's task's rewards are representative of the R reward distribution. My question is what should be the expected reward (or even better the distribution of rewards) for the c selected tasks from T. This is similar to a k-order statistics problem; however, I've been unable to format this problem into a k-order statistics problem due to my basic/limiting understanding of statistics. (I study computer science and only know basic statistical analysis).My approach follows; however, I feel it could be improved. In my approach, I try to calculate the lowest reward of the highest rewarding tasks:If the scheduler can choose c tasks from T and c < |T|, the scheduler will choose the highest rewarding c tasks. Since T's task's rewards are representative of R, The expected reward of a single task will be the expected reward of the upper c / |T| portion of the R distribution.To calculate the expected value of a reward distribution, one takes the integral from x= -infinity to x=+infinity of P(R=x)*xSimilarly, to calculate the expected value of a distribution of the highest c rewards, we take the integral from x = Y to x = +infinity of P(R=x)*x where y is the lowest of the highest rewarding task's rewards.To calculate the upper c/ |T| portion of the R distribution, I let the lowest reward of the highest rewarding task be Y and thus c / |T| = 1 - CDF(Y), where CDF is the cumulative distribution function applied to the reward distribution.c / |T| = 1 - CDF(Y) states that:The proportion of schedulable tasks to total tasks is equal to the proportion of the upper half highest rewarding tasks of the reward distribution.By solving for Y, we get thatY = inverse_CDF(1 - c/|T|)We can then plug the highest rewarding task's reward into our expected value equation earlier and then the expected value of the highest c rewarding tasks are then the integral from x = Y to x = +infinity of P(R=x)*x.Any feedback on how I can improve clarity or improve my analytical equation would be appreciated or if there is a more standard/correct way to describe what I'm doing any suggestions would be appreciated. Also, I'm unsure if this community is the correct community to post this question. If it is not, please provide suggestions as to where I should post this question. I've looked at similar work, and they typically use omniscient scheduling and I'm not too understanding of their syntax/approach.
Analytical Model for Greedy Scheduler
statistics;predictive modeling