About this website

What is this?

This is a bibliography on some scheduling problems. The contributors are Christoph Dürr, Sigrid Knust, Damien Prot, Óscar C. Vásquez. The first version of this website was online since July 2006, and this version went online in January 2016.

How to contribute?

If you would like to contribute as well, drop us an email. You could either provide us the URL to your annotated bibtex file or we give you access to the Dropbox folder. Essentially there is a single file describing formally the notation and the reductions. And the complexity results are simple bibtex files with results written in the Annote field.

A technical description of the website can be found here.

The bibtex files

The initial bibtex file was provided by Peter Brucker and Sigrid Knust, which used it for this other website on the classification of scheduling problems, which has the nice feature of listing minimal and maximal open problems. Since then more material was added, mainly in order to cover the results mentioned in the following books.

The following bibtex files are used for this web site.

All these files describe 808 results.

The reductions

The following reduction rules are used in order to decide if a problem A is a particular case of a problem B. We adopted a simple mechanism which might not capture all possible reductions between the problems, but which is simple. First the problems names are viewed as vectors, associating values to different fields. The fields correspond the pop up selection boxes from the start page, and are called type, number of machines, precedence relation etc. Then problem B dominates problem A if in every field the value of A dominates the value of B.

Fieldwise dominance is defined by the following relations. Some relations depend on some boolean expression formulated on the presence or absence of some values in B. For example a problem defined on one machine is a particular of a problem B defined on 2 machines, if the specification of B allows to use dummy jobs that block one of the machines.

Conditions on dominance arcs

  1. not processing times and not pmtn
  2. R

type

number of machines

robot

server

number of jobs

precedence relation

time lags

transportation delays

preemption

release time

due date

recirculation

no-wait

no-idle

processing times

job size

machine sets

batching

setup times

Objective function