Job Scheduling Algorithm in Java

Question

I need to design an efficient algorithm for a scheduling problem and I really don't have a clue.

There's a machine that produces pills in a certain rate. For example, the machine might be capable to produce 1 pill if it is allowed to continuously work for one day, 4 pills, if it is allowed to work for 3 days, 16 pills if it works for 5 days, and so on. If I stop the machine and take out all the pills then the machine will start from day 1 again. All pills that I took out from the machine must be used on the same day.

There is a certain amount of patients come and take pills everyday. The patients must be treated on the same day, untreated patients are ignored. The goal is to decide which days to stop the machine and treat as many patients as possible in n days.

Suppose the number of days n = 5, given example input

int[] machineRate = {1,2,4,8,16};
int[] patients =    {1,2,3,0,2};

In this case, if I stop the machine on day 3, I will have 4 pills. I can treat 3 patients and throw away 1 pill. Then I stop the machine on day 5 again, since it was stopped on day 3, it has been working for 2 days, therefore I have 2 pills to treat 2 patients. In the end 3+2=5, the output = 5 patients.

If I stop the machine on day 2, day 3, day 5. Then the output will be (2 pills for 2 patients on day 2) +(1 pill for 3 patients on day 3) +（2 pills for 2 patients on day 5）. That equals to 5 patients as well.

The machineRate[] and patients[] vary according to input.

What's the algorithm that finds the maximum number of treated patients?

Answer 1

This is a nice dynamic programming problem.

The way to think of dynamic programming is to ask yourself two questions:

1. Is there a trivial version of this problem if I reduce one (or more) of the variables to zero (or similar)?
2. Is there a simple way of calculating the answer to a problem of size n+1 if I know answers to all problems of size n? (Here, "size" is problem-specific, and you need to find the right notion of size that helps with the problem in hand.)

For this problem, what would be a trivial version? Well, suppose the number of days was 1. Then it would be easy: I stop the machine, and treat as many patients as I can. There's no point doing anything else.

Now, if we consider the number of days left as our notion of size, we get an answer to the second question as well. Suppose we know all answers to all problems where there are n days left. Let's write maxTreat(days, running) for the maximum number we could treat if there were days days left, and if the machine had initially been running for running days.

Now there are n+1 days left; and the machine has been running so far for k days. We've got two options: (1) stop the machine; (2) don't stop it. If we stop the machine, we can treat some patients today (we can work out the number based on k), and thereafter we can treat maxTreat(n, 1) patients, because there are then n days left, and by tomorrow the machine will have been running again for just one day. If we don't stop the machine, we can't treat anyone today, but thereafter we'll be able to treat maxTreat(n,k+1) patients, because by tomorrow the machine will have been running for k+1 days.

I will leave you to work out the precise details, but to solve it efficiently, we create a multidimensional array, based on number of days left, and number of days for which the machine has been running so far. We then iterate through the array, solving all the possible problems, starting from the trivial (one day left) and working backwards (two days, then three days, and so on). At each stage, the problem we're solving is either trivial (so we can just write the answer in), or something we can calculate from entries we wrote into the array at the previous step.

The really cool thing about dynamic programming is that we're creating a cache of all the results as we go. So for problems where a recursive approach would otherwise end up needing to calculate the answer to a sub-problem several times, with dynamic programming we never end up solving a sub-problem more than once.

Additional comments now that I've seen your implementation:

For one, I'm not too surprised that it starts to slow down when you hit 10,000 or so. The algorithm is O(n^2), because at each iteration you have to fill the array with up to n entries before you can move to the next level. I'm quite certain that O(n^2) is the best asymptotic complexity you're going to get for this puzzle, though.

If you want to speed it up further, you could look at a top-down approach. Currently you're doing bottom-up dynamic programming: solving the cases of size 0, then of size 1, and so on. But you can also do it the other way round. Essentially this is the same algorithm as if you were writing a horribly inefficient recursive solution that calculates solutions to sub-problems on the fly, except that you cache a result every time you calculate it. So it looks something like this:

1. Set up your two-dimensional array to hold solutions to sub-problems. Pre-fill it with -1 for each case. A value of -1 will indicate that you haven't solved that sub-problem yet.
2. Write a routine that solves maxTreat(days, running) in terms of answers to sub-problems at the next level down. When you want the answers to the sub-problems, look in the array. If there's a -1 in there, you haven't solved that one yet, so you recursively solve it, and then put the answer into the array. If there's anything other than -1, you can just use the value you find there, because you've already calculated it. (You can also use a HashMap instead of the multidimensional array.)

This is better in one way and worse in another. It's worse because you have overheads associated with the recursion, and because you'll eventually run out of stack with the recursive calls. You might need to bump up the stack size with a command-line parameter to the JVM.

But it's better in one key respect: you don't calculate answers to all sub-problems, but only the ones you need to know the answers to. For some problems, that's a massive difference, and for some, it's not. It's hard to get the right intuition, but I think it might make a big difference here. After all, each answer depends on only two sub-problems from the previous row.

The ultimate solution (don't try this until you get the top-down recursive one going first!) is to do it top-down but without recursion. This will avoid the stack space issue. To do this, you create a stack of sub-problems (use an ArrayDeque) that need solving, and you keep taking them off the front of the queue until there are none left. The first thing is to push onto the stack the large problem for which you need a solution. Now, you iteratively pop problems off the stack until it's empty. Pop one off, and call it P. Then:

1. Look in your array or HashMap to see if P has been solved. If so, return the answer.
2. If not, look to see if the sub-problems for P have already been solved. If they have, then you can solve P, and you cache the answer. If the stack's now empty, then you've solved your final problem, and you output the answer for P.
3. If the sub-problems haven't all been solved, then push P back onto the stack. Then push any of P's sub-problems that haven't yet been solved onto the stack as well.

What will happen as you go is that your stack will grow initially as you push the main problem, and its sub-problems, and then its sub-problems, onto the stack. Then you'll start solving the smaller instances and putting the results into the cache, until eventually you have everything you need to solve the main problem.

It doesn't use significantly less memory than the recursive top-down approach, but it does use heap space rather than JVM stack space, and that means it scales up better because the JVM stack is much smaller than the heap.

This is quite difficult, though. At the very least, keep your working solution before you start coding up the more difficult version!