20

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!

Reed Debaets
  • 482
  • 1
  • 6
  • 18
  • 1
    Do you think you'll add more constraints to this problem? If so, it looks like a timetabling problem, which is 'normally' solved via contraint programming http://en.wikipedia.org/wiki/Constraint_programming or even linear programming http://en.wikipedia.org/wiki/Linear_programming Take a look at the open source project called unitime.org (constraint programming) and ilog's constraint solver (very expensive, but very fast). – Karussell Jan 29 '10 at 22:13

6 Answers6

25

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:

  • Professor 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 system that can cope with changes, so when one constraint is changed at the last minute you don’t have to change the complete timetable.

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.

Ryan Shripat
  • 5,574
  • 6
  • 49
  • 77
Ian Ringrose
  • 51,220
  • 55
  • 213
  • 317
  • great link! .. thanks. A link like that almost belongs on http://lambda-the-ultimate.org – Reed Debaets Jan 29 '10 at 17:01
  • the market leading university scheduling system is still written in list and there use lambda a lot. – Ian Ringrose Jan 29 '10 at 17:09
  • 1
    ""All of the above is normally ignored in research papers about scheduling systems"" just as a side note: thats not true. At least in the latest research they try to make it more real-life. E.g. see the requirements for the tracks of the international timetabling competition 2007. – Karussell Jan 29 '10 at 22:19
  • @Karussel, I think the datasets in the timetabling competition contained all the constrains, and there was not a requirement to cope with new (and unknown) constrains while not changing the current timetable much. Also as I understand all these "standard" datasets are known to the researchers before they submit their software. – Ian Ringrose Feb 01 '10 at 17:53
  • (there were unknown datasets in this competition) – Karussell Feb 01 '10 at 20:46
  • 1
    Good points. Also, NP-complete problems are perfectly solvable for small N, and a lot of real-world scenarios involve small N. – dsimcha Feb 15 '10 at 20:40
  • 3
    It's curious that dynamic scheduling under uncertainties is something we all implicitly solve more or less successfully in our personal and professional lives--and yet virtually no one in the real-time computing research community recognizes -- much less addresses -- this ubiquitous class of scheduling problem. Outside of real-time computing, of course, the problem is well known and widely addressed. – E. Douglas Jensen Oct 25 '13 at 21:07
5

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.

wheaties
  • 35,646
  • 15
  • 94
  • 131
  • greedy algorithms won't always yield a result when one exists though, correct? For my purposes, if a solution exists that schedules all tasks, I must find it. "close" solutions won't work =/ I'll poke around the interwebz for some dynamic programming scheduling algorithms... thanks! – Reed Debaets Jan 29 '10 at 14:25
  • No problem. However, technically you can only get so close. A good heuristic is better than nothing and sometimes about as far as you can go. Scheduling, which has its roots in optimization, is a very deep field. Start simple and work your way up. – wheaties Jan 29 '10 at 14:33
  • the smallest window first really helps alot with finding a solution ... I need to figure out how to prune my search space though so that "false" returns come faster. – Reed Debaets Jan 29 '10 at 14:36
4

There are often good approximation algorithms for NP-hard/complete optimization problems like scheduling. You might skim the course notes by Ahmed Abu Safia on Approximation Algorithms for scheduling or various papers.

In a sense, all public key cryptography is done with "less hard" problems like factoring partially because NP-hard problems offer up too many easy cases. It's the same NP-completeness that makes them "morally hard" which also gives them too many easy problems, which often fall within some error bound of optimal.

There is a deeper theory of hardness of approximation that discusses the limitations of approximation algorithms though.

Jeff Burdges
  • 4,204
  • 23
  • 46
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.

Karussell
  • 17,085
  • 16
  • 97
  • 197
  • 1
    Some sources in Java are available from my timefinder project: https://timefinder.svn.sourceforge.net/svnroot/timefinder/trunk/timefinder-algo/src/main/java/de/timefinder/algo/graph/ – Karussell Jan 29 '10 at 16:22
  • 1
    startBy and startAfter refer to the window in which the task must start between ... ie task a must start after 2:00 and start by 2:30 giving a 30 minute "window of opportunity". Thanks for the link .. I'll look into it ... now :-D – Reed Debaets Jan 29 '10 at 16:39
  • 1
    At first glance it only appears to take into account the order of tasks, not the constraints on that task... nevertheless ... may not be a bad idea to create possible "ordered" lists and check those solutions for validity before launching into an O(n^n) full sweep. – Reed Debaets Jan 29 '10 at 16:51
  • ah, okay. I though you mean a relationship like eventA startsAfter eventB etc. – Karussell Jan 29 '10 at 22:07
2

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

Grembo
  • 1,223
  • 7
  • 6
1

Consider the scheduling problem that is in the class P:

Input: list of activities which include the start time and finish time.

Sort by finish time.

Select the first N elements of this sorted list to find the maximum amount of activities you can schedule in a given time.

You can add caveats like: all activities must end at 5pm, well in this case as you work through the list, stop once you reach an activity which ends after this time.

Logan Leland
  • 11
  • 2