Are all scheduling problems NP-Hard?

Question

I know there are some scheduling problems out there that are NP-hard/NP-complete ... however, none of them are stated in such a way to show this situation is also NP.

If you have a set of tasks constrained to a startAfter, startBy, and duration all trying to use a single resource ... can you resolve a schedule or identify that it cannot be resolved without an exhaustive search?

If the answer is "sorry pal, but this is NP-complete" what would be the best heuristic(s?) to use and are there ways to decrease the time it takes to a) resolve a schedule and b) to identify an unresolvable schedule.

I've implemented (in prolog) a basic conflict resolution goal through recursion that implements a "smallest window first" heuristic. This actually finds solutions rather quickly, but is exceptionally slow at finding invalid schedules. Is there a way to overcome this?

Yay for compound questions!

Answer 1

You can use dynamic programming to solve some of these things. Greedy algorithms also come to mind. Scheduling theory is both deep and beautiful but those two I find will solve most of the problems I've faced. Perhaps I've been lucky.

Answer 2

What do you mean with startBy?

With startAfter and if there is only one resource, then a fast solution could be to use topological sorting. The example algorithm runs in linear time, but does not include the error case if the graph contains cycles.

Answer 3

The hardest part of most scheduling problems in real life is getting hold of a reliability and complete set of constraints, if we take the example of creating a university timetable:

• Processor A will not get up in the morning, he is on a lot of committees, but no-one will tell the timetable office about this sort of constraint
• Department 1 needs the timetable by the start of term, however department 2 that uses the same rooms is unwilling to decide on the courses that will be run until after all the students have arrived
• Etc

Then you need a schedule that can cope with changes, so when one constraint is change at the last minute you don’t have to change the complete schedule.

All of the above is normally ignored in research papers about scheduling systems. As to NP completeness of a given scheduling problem, in real life you don’t care as even if it is not NP complete you are unlikely to even be able to define what the “best solution” is, so good enough is good enough.

See http://www.asap.cs.nott.ac.uk/watt/resources/university.html for a list of papers that may help get you started; there are still many PHDs to be had in scheduling software.

Answer 4

Here's one that isn't.

Schedule a set of jobs i= 1,2...n on a single machine which each take time t(i) so that the average waiting time is minimized.

Solution: Sort in increasing order of t(i). O(n log n)

Good list here