Shuffling as Local Search in Scheduler

In this chapter, we implement the shuffling technique as a simple example of local search in Scheduler.

One of the standard, incomplete search techniques used in the Operations Research scheduling literature is called shuffling. Given a feasible solution to a jobshop scheduling problem, one variation of the shuffle technique randomly (with some probability) removes a subset of the edges on the critical path of the solution. The remaining edges define a partial solution and some standard constructive search technique is then used to try to extend the partial solution to a full solution. This is one iteration of the shuffle technique. Subsequent iterations begin with the solution found in the previous iteration.