An important problem with many applications is routing jobs to parallel processors with dedicated queues to minimize job response times or delays. Often, job sizes are known or well estimated upon arrival, and the router can use this information to minimize delays. If job sizes, as well as routing history, are known, then the router also knows the current states at the servers without message passing.

Somewhat surprisingly, the problem with job-size information available is much harder than the problem without this information, and there are very few theoretical results to provide general guidelines. Counter-examples show that many “intuitively obvious” results are in fact not true.