This sounds like what you might expect from a using a random process (genetic algorithms, simulated annealing) to solve the NP-complete problem. The randomness

This sounds like what you might expect from a using a random process (genetic algorithms, simulated annealing) to solve the NP-complete problem. The randomness injects suboptimal routes like this, as well as more optimal ones, but the fitness/cost function has to distill a whole bunch of things into one scalar. In my experience what happens is that the different things you want to value sort of compete with each other. I'm guessing the current state of the system is quite suboptimal, and it might not be able to remove the randomness. It's quite feasible to get within a factor of 2 of the optimal solution (with much less processing power), which sounds great from a CS algorithm analysis standpoint, but a factor of 2 looks like an awful schedule from a human standpoint.