# Can dynamic programming find globally optimal solutions for scheduling problems

I want to know if dynamic programming can generally find globaly optimal solutions for scheduling problems? I think this might be difficult as dynamic makes one at a time decisions without calculating a schedule for the whole timespan. For that you need something like a linear/non-linear program as far as I see it.

Let's look at one example from the field of energy. Suppose we have an electric vehicle and a time-variable electricity tarif. Now the goal is to charge the electric vehicle such that the overall charging costs for the next day are minimized while having the battery state of charge at a certain minimum value. Tranditionally, this is optimally solved by defining a MILP problem and solving using a solver (with some MIP gap). The output is a schedule which specifies for each hour of the day the charging power (of course we'd need some information about the availability of the electric vehicle)

Now if you apply dynamic programming to this problem, you make sequential decisions at every hour as far as I understand. This can't normally be globally optimal as you don't consider all timeslots and future values (e.g. availability) together to make your decisions.

So can dynamic programming still in fact find the globally optimal solution for such a time constrained scheduling problem.

• Dynamic programming is an optimization method that consists in solving a problem by recursively decomposing it into multiple subproblems, while storing the results of these subproblems to avoid solving them multiple times Commented Oct 11, 2023 at 12:52
• @PeterBe, In the scheduling literature, there exist dynamic programming in the fully polynomial time approximation class which can solve some specific Np-hard problem optimality. Commented Oct 11, 2023 at 14:09

• If you are using backward recursion, the decision at stage $n$ takes into account costs at stage $n$ and all future stages. You make the decision $x$ that optimizes $c_n(x) + f_{n+1}(x)$ where $c_n(x)$ is the cost at the current stage and $f_{n+1}(x)$ is the optimal cost of all future stages given the state you are put into at stage $n+1$ by deciding $x$ in the current state.