I have a question which I tried to solve and I'm not sure if I'm doing it allright, please let me know if I'm wrong.
let $1,2,3,...,12k$ be input for a list scheduliing mission(it means that there is a mission which take 1 time units,2 time units,3time units.... and the biggest take 12k time units.
how would you order the input so it would take the most time(it is online),and how would you order the input so it would be the best case scenario(less time as possible).
giving the fact that there are 3 operating machines who can work at the same time.
Take to notice: for all input the machines work with same algorithm, they put the mission in the first available machine
My Solution: In order to get the base case(less time as possible): order it from the biggest to the smallest: so the first input is 12, then 11 , then 10, so you will get 1/3 of the total time for each machines(since 12k is dividable by 3). I think that im correct but not sure on how to prove it.
for the worst case I said that it need to be order from the smallest number to the biggest , but also im not sure how to prove it.
please let me know if I'm on the right path and if so what is the problem.
Thanks!
You have jobs of sizes $\{1, 2, ..., 12k\}$ and you want to place them into three equal-rate servers to minimize completion time (then, the next problem is to place to maximize completion time).
Here is a hint on minimizing: If you can divide the load exactly equally on all three servers, then all servers finish at the same time and there is no wasted time. So, if this is possible, it would give a minimum time of $\frac{1}{3}\sum_{i=1}^{12k} i$. So the goal is to partition the integers $\{1, ..., 12k\}$ into 3 groups with the same sum.
Your base case $k=1$ can be solved in different ways. One way is:
$$\{12+11+3, 10+9+7, 8+6+5+4+2+1\}$$ However, this way is not particularly helpful for solving the general case $k>1$. A hint is that you can solve the base case $k=1$ another way, where all groups have 4 jobs each. So
1) Solve the base case $k=1$ in a way where all 3 groups have 4 jobs each.
2) Use this to show that, for the general case $k>0$, the numbers $\{1, ..., 12k\}$ can be put into 3 groups, all having an equal sum.