A simulated annealing approach to job shop scheduling using critical block transition operators

The job shop scheduling problem is one of the most difficult NP hard combinatorial optimization problems. This research investigates finding optimal and near optimal schedules using simulated annealing and a schedule permutation procedure. New schedules are generated by permuting operations within existing schedules. Simulated annealing probabilistically chooses one of the new schedules and probabilistically accepts or rejects it, allowing importance sampling search over the job shop schedule space. The initial and (minimum) final temperatures are adaptively determined a priori, and a reintensification strategy that improves the search by resetting the current temperature and state. Experimental results show this simple and flexible method can find near optimal schedules and often outperforms previous SA approaches