# List of scheduling problems and their statuses

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)?

• In any scheduling book like "Scheduling: Theory, Algorithms, and Systems," 2016, by Michael L. Pinedo. – Ribz Oct 27 '17 at 18:47
• @Ribz I edited my question since I wasn't clear enough. Your answer does not supply the list :( – Simon Oct 27 '17 at 18:56
• 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. – Ribz Oct 27 '17 at 19:12
• 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. – D.W. Oct 27 '17 at 19:33