We need to take advantage of multiple CPU's and computer nodes, but we cannot afford to break "incremental score calculation" while we do.
The gain of incremental score calculation is often numberOfEntities/2, so in practice, this gain is much higher than any gain parallelism could bring us.
We need to have both: have our cake and eat it too.

It's a matter of parallelizing the moveScope's.

Do not confuse with Drools multi-threading, which is at a lower level and coming with the new PHREAK algorithm (in 6.x). Due to thread syncs, I suspect that OptaPlanner moveScope parallelization will be more efficient than Drools score calculation parallelization, but it will be nice to have both options

Old Description:
Use Future's to spread all possible moves in each step over a number of threads.
This number of threads is equal to the number of cpu's by default, as no IO is done during solving.

Problems:

• each thread will needs it own WorkingMemory and during a step, each working memory will need to be updated
• a bunch of classes will need to be thread safe, or at least visibility save, such as bestsolutionrecaller.
• Barriers will be needed to collect the result of each step
• decks might be a great way to spread out the load