A simulated annealing algorithm based on bottleneck jobs for the open shop scheduling problem

A simulated annealing algorithm based on bottleneck jobs is presented for the open shop scheduling problem in which the total weighted tardiness must be minimized. Bottleneck jobs have significant impact on the final scheduling performance and therefore need to be considered with higher priority. In order to describe the characteristic information concerning bottleneck jobs, a fuzzy inference system is employed to transform human knowledge into the bottleneck characteristic values which are then used to design an immune operator. Finally, a simulated annealing algorithm combined with the immune mechanism is devised to solve the open shop scheduling problem. In the algorithm, the bottleneck characteristic value for each job in the current solution is evaluated and the vaccination procedure is applied for generating a new solution. Numerical computations for problems of different scales show that the proposed algorithm achieves effective results by accelerating the convergence of the optimization process.