Simulated annealing approach for minimizing the makespan of the general job-shop

A simulated annealing approach is proposed to minimize the makespan of job-shop scheduling. The fundamental idea of this approach is based on the rescheduling activity of the human scheduler. By viewing a Gantt chart of a non-optimal schedule, the human scheduler often finds a better schedule by changing its operation sequence. On the basis of this fact we describe the rescheduling procedure of the human scheduler as a deterministic algorithm, and adopt the simulated annealing method to avoid local minimum states. Computational results show the effectiveness of the proposed approach.