The question is inspired by this paper. In a distant village, there are $n$ electricity consumers. Consumer $i$ has a power demand of $d_i$ watts. The total electricity supply is $s$ watts. If $s\geq \sum_{i=1}^n d_i$, then all consumers are connected all the time. But if this is not the case, then we would like to find the largest fraction $r\in[0,1]$ such that it is possible to connect all consumers at least $r$ of the time.
Here are some examples for $n=3$ consumers and $s=3$ watts, for different demand vectors:
- $(1,1,1)$: $r=1$. We can connect all consumers in parallel all the time.
- $(2,2,2)$: $r=1/3$. We must connect the consumers in sequence, so the best we can do is connect each consumer one third of the time.
- $(2,2,1)$: $r=1/2$. We can connect the two large consumers in sequence, each of them $1/2$ of the time, and connect the small consumer in parallel to them.
- $(2,1,1)$: $r=2/3$. We can connect the large consumer in time $[0,2/3)$, the second consumer in time $[0,1/3)\cup [2/3,1]$, and the third one in time $[1/3,1]$. Note that in each time the total consumption is at most $3$.
Two somewhat related problems are:
- Bin packing. If the demands can be packed into $k$ bins of size $s$, then $r\geq 1/k$. But it is not tight, as shown by the example $(2,1,1)$ above.
- Parallel task scheduling. This problem involves tasks with "length" and "width". The width is analogous to the demand in our problem, and the length is somewhat related to $r$. But I did not find a variant in which this $r$ should be maximized.
Is anything known about this problem?