Counting complexity of a scheduling problem. Let $T={1,…,n}$ be a set of tasks. Each task $i$ has associated a non negative processing time $p_i$ and a deadline $d_i$. A feasible schedule of the tasks consists of a permutation of $n$ elements $\pi$, such that $\sum_{i=1}^k p_{\pi(i)} \le d_{\pi(i)}$ for all $k=1,\ldots,n$.

Does there exist a pseudo-polynomial time algorithm for computing the total number of feasible schedules?

A pseudo-polynomial time algorithm is an algorithm whose running time is bounded by a polynomial on the size of the input, given that the input is written in unary notation (2 = II, 3 = III). (e.g., the size of a number n in unary notation is $O(n)$, and not $O(\log(n)))$.
Edit: It seems that the questioner knew that this was an open problem: https://mathoverflow.net/questions/33796/existence-of-a-pseudo-polynomial-time-algorithm-for-a-counting-problem.  For what it is worth, it took me some time to find the paper, and I think that the time was wasted.



This question is stated as an open problem in [Ber09], where the same problem except that the numbers in the input are written in binary is shown to be #P-complete by a reduction from the counting version of the Subset Sum problem.

References

[Ber09] Gerardo Berbeglia.  The counting complexity of a simple scheduling problem.  Operations Research Letters, 37(5):365–367, Sept. 2009.  http://dx.doi.org/10.1016/j.orl.2009.05.004