A constrained topological sort?

Some cases of your problem are solvable by greedy approach. For example $r \ge n$ and $\{\,a_1, a_2, \ldots, a_n\,\} = \{\,1, 2, \ldots, n\,\}$. In this case penalty function tells that the last vertex in our ordering should have the smallest possible value and no matter how all other vertices are placed. Topological order says that it also should have no outgoing arcs. So we should place there a vertex with smallest value among all vertices without outgoing arcs and solve a subproblem. Using heap we can get $O(n \log n + m)$ time for $n$ vertices and $m$ arcs.

In general case the problem seems to be NP-hard. However I failed to prove this fact.