Scheduling Zoo

The blog is about 20 days old and as part of the blog entries, I would like to share some OR websites from time to time.  These will be tagged as “Useful OR websites”.elephant

The first one of these entries is… the Scheduling Zoo.  I was looking for the computational complexity of different scheduling problems for my research and came across this website.  The Scheduling Zoo is a searchable bibliography on the complexity of scheduling problems by Peter Brucker and Sigrid Knust and the website is maintained by Christoph Duerr.

At the zoo, you pick your environment (e.g., single machine, job shop, etc.), then, the problem characteristics (e.g., precedence constraints or not) and the objective function (e.g., minimize makespan, minimize the number of late jobs, etc.) then it returns the known complexity results along with the related problems, their complexity and references for each!   Given the elephantine literature on scheduling it is a pretty neat, specialized bibliography search website.  You can find a related website here.

They collect statistics on the searches. Turns out:

* The most popular objective function is to minimize makespan (1936 searches when I looked) followed by a distant second, to minimize the sum of completion times (517 searches).

* The most popular machine environment is single machine scheduling (1362 searches) followed by parallel machine scheduling with identical machines (665)

* And, the two most popular variants are “release times” (1505 searches) and “precedence constraints” (1038).


Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: