views:

363

answers:

4

I am looking for introductory and intermediate materials on scheduling algorithms (books, papers, you name it). I am also interested in reference implementations and libraries, any language will do.

The goal is to evenly distribute set of recurring activities over time span. Also a number of constraints must be satisfied: resource availability at given point in time, activity precedence, maximum deviation from desired activity frequency, etc.).

What can you recommend from your experience?

A: 

What kind of scheduling, and with which kind of goal? (Algorithms that schedule for maximum throughput may not be the same as ones scheduling for responsiveness or for ensuring that shorter tasks finish quickly)

jalf
It's about scheduling resources. I updated the question.
Constantin
A: 

Any book on operating systems will do. William Stallings and Andrew Tanembaum are very renowned authors of educational material in this area, and their books have a decent overview of the workings of such algorithms.

However the best thing to do after reading these is to take a look at real code that handles these tasks. The Minix OS, a microkernel operating system written by Tanembaum for teaching, has very clear, easy-to-understand code in this regard. Likewise you can look at the code on the BSDs and Linux OSs that handle scheduling for production-grade code. I would recommend starting with Minix to get a hang of the workings, then moving on to the BSDs, and finally Linux (the BSDs have a reputation for having more organized code than Linux).

Daishiman
Thank you, although i believe i need something different (see updated question). Also, you probably meant "TaneNbaum".
Constantin
+1  A: 

I had a great math course on this material recently. It was called Stochastic Modeling, and we studied the way resources come available and are consumed in discrete systems. It's all backed up by simulation code, so it's not all math. It's also called Queueing Theory, because it relates how items come in and line up waiting for processing. The different ways you can describe 'job arrival' and 'job completion' as time consuming endeavors. (All as random variables with different and well defined distributions).

It's a field called Operations Research.

Putting those "operations research stochastic modeling" into google gives a link to the textbook we used! http://www.amazon.com/Stochastic-Models-Operations-Research-Vol/dp/0486432599

It's very math heavy, it was a graduate level course. The information is invaluable if you are serious about learning this stuff.

Edit: A comment about scheduling I want to add; It's a story a professor of mine once told in a CS class on Information Representation. Dr. Douglas Harris was a mathematician for hire in the 70's, and was tasked with a scheduling algorithm for running processes on a satellite. The trick was that information to and from the satellite was some incredibly low BAUD, like modems from back then. They had a set of jobs of varying complexity the satellite had to perform, and a each one had a deadline that it had to be completed by. His task was to code up how the satellite would decide which job to run next based on their deadlines. Turns out the best method was a naive, "do whatever is due soonest" regardless of job complexity or priority, and he proved it mathematically! The moral is that schedulers don't have to be complicated, they have to be intelligently designed.

Karl
Thanks! It will go into "intermediate" pile.
Constantin
+2  A: 

Broadly, linear programming, graph theory, and constraint satisfaction problems all apply to this problem space. Interestingly, older books in this space haven't lost their relevance; there are improvements to many of the mechanisms used to solve this category of problems, but nothing that really undermines the older stuff.

For problems that come up a lot in scheduling, look at algorithms for job-shop scheduling, bin packing (sometimes), graph coloring, the simplex method, topological sorting.

Decreasing-time and critical path are two common scheduling methods, and they can be juggled against available resources and a priority list.

I'm not particularly savvy, but one of my pet projects involves optimal ordering of a set of steps with parallel tasks with constraints, and those areas are where I've spent the most time studying so far.

JasonTrue
Thanks .
Constantin