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
    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
    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
    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
    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
    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$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.