First of all, here is a scheme that doesn’t work on its own because it ignores the constraints on maximum inflow and outflow rates, so it solves an easier problem.
The tricky bit here seems to be which tank to use when. It looks like tanks with lower values of Ui are better. If you take any sequence that fills a tank with a high value of Ui while there is a tank with a lower value of Ui that has space, then you can get a better sequence by filling the better tank first, and using the extra water when you would use the water you would otherwise put into the worse tank. Similarly, if you are extracting water from a bad tank when there is water in a good tank, you can get a better sequence by extracting the water from the good tank, which gives you the opportunity of filling it when you would otherwise fill the bad tank.
So it looks like when you fill a tank you want to fill the best tank available, and when you empty a tank you want to empty the best tank available. Given this – and assuming there aren’t any restrictions you haven’t mentioned, such as integer amounts of water in transfers – it looks like it is easy to find the best schedule in any given situation. So try this best schedule and if it doesn’t work, nothing will.
The above doesn’t work because I have ignored constraints. I have certainly ignored the inflow and outflow rates, and I am also assuming that you can use more than one tank at each step, which I suspect might not be the case.
There are other schemes that solve simpler problems – you could ignore all the constraints except the outflow rates and fill the tank with the highest outflow rate you can at each stage and provide water from the tank with the lowest outflow rate capable of meeting the demand.
These variants don’t solve your problem, but if there is no solution when you ignore some of the constraints there is no solution to the original problem. This leads to a variant of branch and bound.
1) If a simple greed solution finds a good schedule, then the sequence is obviously solvable.
2) Try solving the easier problems. If any of them are unsolvable, there is no solution for this sequence.
3) Consider all possible choices for the first time step, calling yourself recursively to solve the resulting shorter sequences, starting with water in the tanks. As soon as any of them find a solution you can return with it. If you check all of them and they all say “no solution” then there is no solution.
2
solved Water Storage Scheduling [closed]