  Budget Minimization is a scheduling problem with precedence constraints,
i.e., a scheduling problem on a partially ordered set of jobs $(N, \unlhd)$. A
job $j \in N$ is available for scheduling, if all jobs $i \in N$ with $i \unlhd
j$ are completed. Further, each job $j \in N$ is assigned real valued costs
$c_{j}$, which can be negative or positive. A schedule is an ordering $j_{1},
\dots, j_{\vert N \vert}$ of all jobs in $N$. The budget of a schedule is the
external investment needed to complete all jobs, i.e., it is $\max_{l \in \{0,
\dots, \vert N \vert \} } \sum_{1 \le k \le l} c_{j_{k}}$. The goal is to find
a schedule with minimum budget. Rafiey et al. (2015) showed that Budget
Minimization is NP-hard following from a reduction from a molecular folding
problem. We extend this result and prove that it is NP-hard to
$\alpha(N)$-approximate the minimum budget even on bipartite partial orders. We
present structural insights that lead to arguably simpler algorithms and
extensions of the results by Rafiey et al. (2015). In particular, we show that
there always exists an optimal solution that partitions the set of jobs and
schedules each subset independently of the other jobs. We use this structural
insight to derive polynomial-time algorithms that solve the problem to
optimality on series-parallel and convex bipartite partial orders.
