0
$\begingroup$

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.

Improve this question
$\endgroup$
6
  • 1
    $\begingroup$ Usually asking open problems is not really considered appropriate for MO; see the FAQ. That said, you might ask something like "what is the current state of knowledge about this problem?" $\endgroup$
    – Daniel Litt
    Commented Jul 29, 2010 at 14:57
  • $\begingroup$ Should the RHS read $d_{\pi(k)}$ instead of $d_{\pi(i)}$? I also agree with Daniel, it seems inappropriate to ask an open question (especially such a recent one) on MO. $\endgroup$
    – Artem Kaznatcheev
    Commented Aug 27, 2010 at 13:00
  • 1
    $\begingroup$ At the time I write this comment, the question has been edited and now makes no sense whatsoever $\endgroup$
    – Yemon Choi
    Commented Sep 13, 2010 at 15:40
  • 1
    $\begingroup$ I've rolled the question back to it's previous version, which at least made sense. I don't know anything about this question, but it seems perfectly reasonable to ask whether any progress has been made on it. $\endgroup$
    – David E Speyer
    Commented Sep 13, 2010 at 15:51
  • 1
    $\begingroup$ Actually, David, could you further roll it back to the version by Gerry, which had the same content but had grammar corrected and used LaTeX? $\endgroup$
    – JBL
    Commented Sep 13, 2010 at 17:51

1 Answer 1

Reset to default
1
$\begingroup$

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

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .