# List Scheduling , worst and best case

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!

• For general input I think you are looking at a variant of the bin packing problem. It's hard. en.wikipedia.org/wiki/Bin_packing_problem . For these particular tasks there may be an easy solution and you may have found it - I haven't checked. Someone might. – Ethan Bolker Apr 5 '18 at 12:40
• @EthanBolker hey, it is a different problem, in list scheduling we are looking at the machine which took the longest time... for example if 3 machine get task which take 3,2,1 , then the machine who takes the longest time is 3, if we get for example 1,2,3,4 then the Optimal case will be machine who got 1 and 2, machine who got 3 and machine who got 4, but worst case will be if 1 machine get 1,4 and other got 3,2 so worst wil be 5. hope you understand now.. – user2323232 Apr 5 '18 at 12:44

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.

• PS: The minimum time problem seems to be the interesting one. For the problem of maximizing time, it seems easy to just put all jobs on one server, so ignore the other two servers. Or better yet, place them to none and so the time is $\infty$. – Michael Apr 5 '18 at 14:27
• Take to notice: for all input the machines work with same algorithm, they put the mission in the first available machine, so for the maximum there must be a way to organize it so it will be max... (all in one machine is not possible in that case..) – user2323232 Apr 14 '18 at 9:45