0
$\begingroup$

As of 1993, there are 4536 scheduling problems, 3821 were proven to be $NP$-hard, 417 polynomially solvable, and 298 still open.

Where can I find the most up-to-date list of scheduling problems and their statuses (if they are $NP$-hard, polynomially solvable or open)?

| cite | improve this question | |
$\endgroup$
  • $\begingroup$ In any scheduling book like "Scheduling: Theory, Algorithms, and Systems," 2016, by Michael L. Pinedo. $\endgroup$ – Ribz Oct 27 '17 at 18:47
  • $\begingroup$ @Ribz I edited my question since I wasn't clear enough. Your answer does not supply the list :( $\endgroup$ – Simon Oct 27 '17 at 18:56
  • 1
    $\begingroup$ I don't know what kind of scheduling problems you are mentioning in your first sentence. (Where did you get that sentence from?) Though, in the book that I cited, on page 599 of appendix E, there is a list of tables, where the author presents complexity classification of deterministic scheduling problems. $\endgroup$ – Ribz Oct 27 '17 at 19:12
  • $\begingroup$ Why do you think that there are only 4536 scheduling problems? I can invent any problem you want and call it a scheduling problem. I don't think what you are asking is well-defined, and I don't think it's possible to have a complete list of all scheduling problems, as the notion of what counts as a scheduling problem is subjective and has no precise definition. $\endgroup$ – D.W.♦ Oct 27 '17 at 19:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.