This is very well written example code, well done!
It is also complete, I was able to compile and execute the code with no changes. Very nice.

> Is this the correct way to go about distributing workload across a
> number of threads?

Yes. The only improvement I would suggest in this regard is that I would rather see the number of routees specified in a configuration file than in the code. This would allow you to reconfigure the router in a number of different ways without having to recompile the application. You could also deploy the service across multiple machines just through configuration. Limiting the routees to the number of available processors makes the assumption that the routees are all deployed locally, and this runs counter to the principle of location transparency.

So a configuration file would be good for this example, especially for the router.

> Do I use the Akka API correctly?

Yes.

> Is this the right pattern for handling the routees exceptions?

As far as this example goes, yes, it seems to be perfectly correct. It uses the default behavior of actors being restarted when an exception is thrown, and in this example that seems to be exactly what is needed. In other situations you may have to change the default supervisor strategy and, for example, escalate the exception to the parent for special handling instead of just letting the actor be restarted.

You said you were interested in "any feedback", so I will also add some suggestions on how you might make the code (even) cleaner. Some of this might be personal preference, so feel free to disagree:

- It appears the entire listing is in one file. Maybe you did that just to submit it for review, but it would be easier to digest in separate files, each with their own imports. The way it was split up into `Worker`, `Dispatcher`, etc., would be a good way to split it into separate files as well.
- There are number of unused imports, this is cruft.
- The `TimedActor` trait is not actually used anywhere, so it doesn't add value to the example.
- I would use parentheses after `sender()`, `iterator.next()`, `shutdown()` and `preStart()` since these are *more than just a property of the object*. See *Programming in Scala* 10.3 Defining parameterless methods.
- The curly brackets are not necessary after `case`. I personally prefer to leave them out where they are not necessary.
- The `reduceLeft` call can be simplified:

    From
        
        (1 to 2000000).reduceLeft {
           _ + _
        }
        
    To
        
        (1 to 2000000).sum

- Unnecessary parentheses in a case filter:

          case x if ((0 to 500) contains x) ⇒ false

    can be written as

          case x if (0 to 500) contains x ⇒ false

- Simplify

        !workDone.valuesIterator.exists(_ == None)
        
    to

        !workDone.valuesIterator.contains(None)

- The following code 

          val result = new WorkService doWork (workload)

    might be nicer written as

          val result = new WorkService.doWork(workload)

    or

          val result = new WorkService doWork workload

    (Personally I prefer the former).