An immune mechanism for the open shop scheduling problem with application to genetic algorithm

An immune mechanism 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 reflect the features of both the objective function and the current optimization stage. Then, an immune operator is designed based on these characteristic values and a genetic algorithm combined with the immune mechanism is devised to solve the open shop scheduling problem. Numerical computations for problems of different scales show that the proposed algorithms achieve effective results by accelerating the convergence of the optimization process.