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)) <= d_(pi(i)) for all k=1,…n.
Does there exists 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)).
This is an open question from an article published in 2009 at Operations Research Letters.
Best Answer
If you need to compute all solution for a specific instance, you could generate a an IP formulation of the problem and use a lattice point enumeration code such as http://www.math.ucdavis.edu/~latte/">LattE. This might be a good problem for the operations research QA